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

HMMT February 2011 — Guts Round — Problem 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 is contained in at least one of these rows or columns. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . th 14 HARVARD-MIT MATHEMATICS TOURNAMENT, 12 FEBRUARY 2011 — GUTS ROUND ′ ′ ′ ′ ′

解析

[ 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 is contained 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 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 × 1006 + 1006 = 3018 chips in total. Contradiction. ′ ′ ′ ′ ′