Maths Olympiad Prep

Library / /5 of 27

Combinatorics Difficulty 5.3 AIME, harder Prove it Croatia

On the board 8×88 \times 8 tromino-tiles of the shape □\square have to be placed in such a way that each tile covers exactly three cells of the board and the tiles cannot overlap.
What is the least possible number of tromino-tiles that one can place on the board so that no additional tromino-tile can be placed afterwards?

Solution

Let us divide the board into 16 2×22 \times 2 squares as in the picture.
Figure 1
In each of those squares at least two cells have to be covered, otherwise we could place a tromino-tile on three uncovered cells. Hence, at least 32 cells have to be covered, and we need at least 11 tromino-tiles to do that covering.
The following construction shows that 11 tromino-tiles are enough to satisfy conditions of the problem.
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.