HMMT-Feb 2011 guts, Problem 8

Find the smallest $k$ such that for any arrangement of 3000 checkers in a $2011 \times 2011$ checkerboard, with at most one checker in each square, there exist $k$ rows and $k$ columns for which every checker is contained in at least one of these rows or columns.

Solution: If there is a chip in every square along a main diagonal, then we need at least 1006 rows and columns to contain all these chips. We are left to show that 1006 is sufficient. Take the 1006 rows with greatest number of chips. Assume without loss of generality they are the first 1006 rows. If the remaining 1005 rows contain at most 1005 chips, then we can certainly choose 1006 columns that contain these chips. Otherwise, there exists a row that contains at least 2 chips, so every row in the first 1006 rows must contain at least 2 chips. But this means that there are at least $2 \times 1006+1006=3018$ chips in total. Contradiction. $\fbox{1006}$.

Answer: 1006