Browse · MathNet
PrintSAUDI ARABIAN MATHEMATICAL COMPETITIONS
Saudi Arabia counting and probability
Problem
An square is partitioned into 121 smaller squares, 4 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 we can obtain regardless of the positions of the black squares? It is allowed to cut the rectangle along the grid lines.
Solution
In the first image we have position for 4 black cells, such that the biggest rectangle without black is . Now let's prove that for any configuration there exists a rectangle of area . Assume for some configuration the biggest rectangle is at most . Let's divide the board into 4 squares of size like in second image. Each of them must contain at least one black cell, so the last column and first row have no black cells.
Analogously first column and last row have no black cells. By considering squares -, -, - and - we conclude that -th row and column doesn't contain black cell.
Now assumes that there is a black cell in column . Then each of rectangles -, - contain at least one black cell, so either orange or green rectangle doesn't contain a black cell. That rectangle together with layer - will form a rectangle of area that has no black cell. Contradiction. So column has no black cell. The same for column and rows and . So we get the last image configuration, where in gray cells can not be painted black. Then each white square must contains exactly one black cell.
Assume is black. Then consider - and -. We conclude that black cell is in square -. Same goes for -. Then by looking at the rectangles - and - we conclude that must be black.
From rectangles - and - follows that and are black. Be then - is white and has area . So we conclude that , , , are white. Finally, each of rectangles -, -, -, - must have exactly one black square. But then central square - contains white cells, a contradiction.
Analogously first column and last row have no black cells. By considering squares -, -, - and - we conclude that -th row and column doesn't contain black cell.
Now assumes that there is a black cell in column . Then each of rectangles -, - contain at least one black cell, so either orange or green rectangle doesn't contain a black cell. That rectangle together with layer - will form a rectangle of area that has no black cell. Contradiction. So column has no black cell. The same for column and rows and . So we get the last image configuration, where in gray cells can not be painted black. Then each white square must contains exactly one black cell.
Assume is black. Then consider - and -. We conclude that black cell is in square -. Same goes for -. Then by looking at the rectangles - and - we conclude that must be black.
From rectangles - and - follows that and are black. Be then - is white and has area . So we conclude that , , , are white. Finally, each of rectangles -, -, -, - must have exactly one black square. But then central square - contains white cells, a contradiction.
Final answer
25
Techniques
Coloring schemes, extremal arguments