Problem:
In an square array of cells, at least one cell is colored pink. Show that you can always divide the square into rectangles along cell borders such that each rectangle contains exactly one pink cell.
Solution
Solution:
We claim that the statement is true for arbitrary rectangles. We proceed by induction on the number of marked cells. Our base case is marked cell, in which case the original rectangle works.
To prove it for marked cells, we split the rectangle into two smaller rectangles, both of which contain at least one marked cell. By induction, we can divide the two smaller rectangles into rectangles with exactly one marked cell. Combining these two sets of rectangles gives a way to divide our original rectangle into rectangles with exactly one marked cell, completing the induction.
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.