A square is divided into small squares, of which are painted black, the rest being white. We cut a fully white rectangle (possibly, a square) out of the big square. What is the maximal area of the rectangle that we can attain regardless of the positions of the black squares? It is only allowed to cut the rectangle along the grid lines.
Solution
Cut the square into smaller blocks. Since there are only eight black squares, at least one of the blocks doesn't contain any of them. Therefore a white square of area can always be found.
Next, we show that sometimes it is impossible to find a larger rectangle. Fig. 2 is an example. Here, one can cut out either a square or a rectangle, but not any rectangle of larger area.
Fig. 2
Looking for a route rather than an archive? The track puts 2,000
problems in a working order, from AMC 10 level to the IMO shortlist.