Maths Olympiad Prep

Track / Stage 5 / 368 of 400 #1448 of 2444

Problem 1448

AIME late
Combinatorics Difficulty 5.9 Prove it Estonian Mathematical Olympiad · Estonia

Pieces of cardboard of dimensions 1×41 \times 4 are placed on a 10×1010 \times 10 grid in such a way that each piece covers exactly 4 adjacent unit squares (either horizontally or vertically) and no two pieces touch each other side-to-side, edge-to-edge, or corner-to-corner. Find the largest possible number of cardboard pieces.

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.

Next problem →

Official solutions — 2

Solution 1

Let the pieces of cardboard be placed on the grid as required. Since each piece covers exactly 4 unit squares and no two pieces touch, there is at least a 1-unit wide space between every two pieces. Therefore, if we draw a half-unit wide "no-go zone" around each piece, the areas covered by the pieces and their no-go zones will have dimensions of 2×52 \times 5 and will not overlap. Since these areas extend over the edges of the grid by at most half a unit, all these areas can fit within a 11×1111 \times 11 square. Therefore, no more than 111125=12\lfloor \frac{11 \cdot 11}{2 \cdot 5} \rfloor = 12 pieces can be placed on the grid.
This limit case is achievable, as shown in Fig. 37.

Figure 1
Fig. 37

Solution 2

Divide the 10×1010 \times 10 grid into squares of dimensions 2×22 \times 2 (Fig. 38).

Note that at most 2 unit squares can be covered in any 2×22 \times 2 square because otherwise at least two different pieces must be used which would then touch each other. Since there are 25 squares of 2×22 \times 2, the pieces can cover at most 252=5025 \cdot 2 = 50 unit squares, and thus there can be at most (50/2)=12\lfloor (50/2) \rfloor = 12 pieces. The fact that 12 pieces are possible is shown in Fig. 37.

Figure 2
Fig. 38

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