Maths Olympiad Prep

Library / /141 of 155

Combinatorics Difficulty 7.1 National olympiad, round 2 Prove it Saudi Arabia

An 11×1111 \times 11 square is partitioned into 121 smaller 1×11 \times 1 squares, 4 of which are painted black, the rest being white. We cut a fully white rectangle (possibly a square) out of the big 11×1111 \times 11 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 2525. Now let's prove that for any configuration there exists a rectangle of area 2525. Assume for some configuration the biggest rectangle is at most 2424. Let's divide the board into 4 squares of size 55 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 a1a1-e5e5, a7a7-e11e11, g1g1-k5k5 and g7g7-k11k11 we conclude that 66-th row and ff column doesn't contain black cell.

Now assumes that there is a black cell in column bb. Then each of rectangles c1c1-k3k3, c9c9-k11k11 contain at least one black cell, so either orange or green rectangle doesn't contain a black cell. That rectangle together with layer c6c6-k6k6 will form a rectangle of area 2727 that has no black cell. Contradiction. So column bb has no black cell. The same for column ll and rows 22 and 1010. So we get the last image configuration, where in gray cells can not be painted black. Then each white square 3×33 \times 3 must contains exactly one black cell.

Assume c9c9 is black. Then consider d7d7-h11h11 and a6a6-k8k8. We conclude that black cell is in square g7g7-h8h8. Same goes for d4d4-e5e5. Then by looking at the rectangles i1i1-k11k11 and a1a1-k3k3 we conclude that i3i3 must be black.

Figure 1

From rectangles a1a1-d8d8 and a1a1-h4h4 follows that d4d4 and h8h8 are black. Be then e1e1-g11g11 is white and has area 3333. So we conclude that c3c3, c9c9, i3i3, i9i9 are white. Finally, each of rectangles c4c4-c8c8, d9d9-h9h9, d3d3-h3h3, i4i4-i8i8 must have exactly one black square. But then central square d4d4-h8h8 contains 2525 white cells, a contradiction.

Figure 2

Figure 3

\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 and solution reproduced as published; topic and difficulty added by this site.