Browse · MathNet
Print55rd Ukrainian National Mathematical Olympiad - Third Round
Ukraine geometry
Problem
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
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
Final answer
9
Techniques
Combinatorial GeometryOptimization in geometryPigeonhole principleColoring schemes, extremal arguments