HMMT 十一月 2015 · THM 赛 · 第 5 题

英文解析

5. Consider a 5 × 5 grid of squares. Vladimir colors some of these squares red, such that the centers ofany four red squares do not form an axis-parallel rectangle (i.e. a rectangle whose sides are parallel tothose of the squares). What is the maximum number of squares he could have colored red?
   Proposed by: Sam Korsky
   Answer: 12
   We claim that the answer is 12. We first show that if 13 squares are colored red, then some four forman axis-parallel rectangle. Note that we can swap both columns and rows without affecting whetherfour squares form a rectangle, so we may assume without loss of generality that the top row has themost red squares colored; suppose it has k squares colored. We may further suppose that, without lossof generality, these k red squares are the first k squares in the top row from the left.
   Consider the k × 5 rectangle formed by the first k columns. In this rectangle, no more than 1 squareper row can be red (excluding the top one), so there are a maximum of k +4 squares colored red. In theremaining (5 − k ) × 5 rectangle, at most 4(5 − k ) squares are colored red (as the top row of this rectanglehas no red squares), so there are a maximum of ( k + 4) + 4(5 − k ) = 24 − 3 k squares colored red in the
   5 × 5 grid. By assumption, at least 13 squares are colored red, so we have 13 ≤ 24 − 3 k ⇐⇒ k ≤ 3.
   Hence there are at most 3 red squares in any row. As there are at least 13 squares colored red, thisimplies that at least 3 rows have 3 red squares colored. Consider the 3 × 5 rectangle formed by thesethree rows. Suppose without loss of generality that the leftmost three squares in the top row arecolored red, which forces the rightmost three squares in the second row to be colored red. But then,
   by the Pigeonhole Principle, some 2 of the 3 leftmost squares or some 2 of the 3 rightmost squares inthe bottom row will be colored red, leading to an axis-parallel rectangle – a contradiction.
   Hence there are most 12 squares colored red. It remains to show that there exists some coloring whereexactly 12 squares are colored red, one example of which is illustrated below:
   R R R R
   R R
   R R
   R R
   R R
   The maximum number of red squares, therefore, is 12 .