Maths Olympiad Prep

Library / /6 of 15

Combinatorics Difficulty 5.7 AIME, harder Prove it Argentina

Cover a grid square 13×1313 \times 13 with 2×22 \times 2 squares and L-shapes of three unit cells so that the number of L-shapes is least possible.

Figure 1

Solution

Let a (2k1)×(2k1)(2k-1) \times (2k-1) square board be covered as in the statement with xx squares 2×22 \times 2 and yy shapes L. Denote by (i,j)(i, j) the cell in row ii, column jj, and color black all cells (i,j)(i, j) with both ii and jj odd. Thus k2k^2 black cells are obtained. Observe that wherever a 2×22 \times 2 square is placed, it covers exactly one black cell; and wherever an L-shape is placed, it covers at most one black cell. To have the whole board covered it is necessary that the total number of figures be at least k2k^2, i.e. x+yk2x+y \ge k^2.

All figures cover 4x+3y4x+3y cells, which equals (2k1)2(2k-1)^2, the total number of cells on the board. On the other hand xk2yx \ge k^2-y implies 4x+3y4(k2y)+3y=4k2y4x+3y \ge 4(k^2-y)+3y = 4k^2-y. Hence 4k2y(2k1)24k^2-y \le (2k-1)^2, yielding y4k1y \ge 4k-1. In summary each admissible covering has at least 4k14k-1 shapes L and at most k24k+1k^2-4k+1 squares 2×22 \times 2.

A 13×1313 \times 13 board corresponds to the case k=7k=7, so the number of L-shapes is at least 471=274 \cdot 7 - 1 = 27; the number of 2×22 \times 2 squares is at most 7247+1=227^2 - 4 \cdot 7 + 1 = 22. The example in the figure shows a covering with 22 squares 2×22 \times 2 and 27 shapes L. Hence the minimum number of L-shapes is 27.

Figure 2

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 reproduced verbatim; metadata (topic, difficulty) added by this project.