HMMT 二月 2011 · 冲刺赛 · 第 8 题

英文解析

8. [ 6 ] Find the smallest k such that for any arrangement of 3000 checkers in a 2011 × 2011 checkerboard,
   with at most one checker in each square, there exist k rows and k columns for which every checker iscontained in at least one of these rows or columns.
   Answer: 1006
   If there is a chip in every square along a main diagonal, then we need at least 1006 rows and columnsto 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, soevery row in the first 1006 rows must contain at least 2 chips. But this means that there are at least
   2 × 1006 + 1006 = 3018 chips in total. Contradiction.
   ′ ′ ′ ′ ′