Find the smallest such that for any arrangement of 3000 checkers in a checkerboard, with at most one checker in each square, there exist rows and 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 chips in total. Contradiction.
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.