CombinatoricsDifficulty 7.1National Olympiad, round 2Prove itUnited States
Problem:
Suppose that n squares of an infinite square grid are colored grey, and the rest are colored white. At each step, a new grid of squares is obtained based on the previous one, as follows. For each location in the grid, examine that square, the square immediately above, and the square immediately to the right. If there are two or three grey squares among these three, then in the next grid, color that location grey; otherwise, color it white. Prove that after at most n steps all the squares in the grid will be white.
Below is an example with n=4. The first grid shows the initial configuration, and the second grid shows the configuration after one step.
Solution
Solution:
(Sketch) Use strong induction. Consider the smallest rectangle R that contains all the black squares. Suppose this rectangle contains r squares. Assume any rectangle that contains k<r squares will convert to all white squares after k steps. Since R is the smallest rectangle, its left-most column and its bottom row must contain some black squares. So the rectangle with the left-most column of R removed and the rectangle with the bottom row removed must both have less than r black squares. So both of those rectangles must be converted to all white after r−1 steps. (We are using the fact that squares below and to the left of a rectangle cannot affect the evolution of the squares within that rectangle.) So, after r−1 steps, R would have been converted to all white squares except for possibly the lower left corner square. But even if that square is black, the rth conversion will convert that square into white 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.
