Track / Stage 8 / 80 of 180 #2260 of 2444

Problem 2260

IMO Shortlist mid-range; USAMO P2/P5

Combinatorics Difficulty 8.4 Prove it IMO Hk TST · Hong Kong · 1997

A $11 \times 11$ grid is to be covered completely without overlapping by some $2 \times 2$ squares and $L$ -shapes each composed of three unit cells. Determine the smallest number of $L$ -shapes used. (Each shape must cover some grids entirely and cannot be placed outside the $11 \times 11$ grid. The $L$ -shapes may be reflected or rotated when placed on the grid.)

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

At least 23 $L$ -shapes are needed.
Suppose $x$ squares and $y$ $L$ -shapes are used. Then the total number of cells is $4x + 3y$ , which should be equal to $11^2 = 121$ .

We colour the cells as shown. Then every square and every $L$ -shape covers at most one blackened cell. As there are 36 blackened cells, we have $x + y \ge 36$ .

Therefore, $y = 4(x + y) - (4x + 3y) \geq 4(36) - 121 = 23$ . The figure on the right gives one example using 23 L-shapes.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.