Maths Olympiad Prep

Library / /5 of 36

Combinatorics Difficulty 5.4 AIME, harder Prove it Saudi Arabia

Given a square board of 8×88 \times 8 and one colors exactly 77 squares of the board. Prove that for every way of coloring, there always exists a sub-square size 2×22 \times 2 of the board on which exactly one square is colored.

Solution

We number rows numbered from 11 to 88 (from top to bottom), and columns numbered from 11 to 88 (from left to right). Suppose by contradiction that each 2×22 \times 2 square board does not contain exactly one colored square.

Obviously there must also be an empty column, let's say it is the ii column with 1i81 \le i \le 8. Let's consider the left column (if any) of this ii column, that is, the (i1)(i-1)-th column. If on that (i1)(i-1)-th column, there is a colored square. Let's consider the corresponding 2×22 \times 2 square containing 22 squares on ii-th column (which are two uncolored squares) and also containing the ×\times cell. Thus, the remaining cell in (i1)(i-1)-th column must also be colored because otherwise the 2×22 \times 2 table contains exactly 11 colored cell, which contradicts the assumption.

Continuing like that, consider the squares containing 22 cells in column ii and containing a colored cell in column i1i-1, then by similar reasoning, the remaining cell is also colored. This shows that the entire column i1i-1 must be colored, that is, there are 88 colored cells, which is absurd. From there, we can deduce that column i1i-1 is an empty column. The same reasoning goes for column i+1i+1. From there, we can continue to expand to columns i2,i3,,1i-2, i-3, \dots, 1 and columns i+2,i+3,,8i+2, i+3, \dots, 8, which are also empty columns. Therefore, the entire table is not colored, which is also absurd. This proves the given assertion. \square

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.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.