Library / /114 of 136

, 1997

Combinatorics Difficulty 8.4 Shortlist Prove it Hong Kong

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.)

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.

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.