Maths Olympiad Prep

Library / /39 of 101

Combinatorics Difficulty 5.9 AIME, harder Prove it 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.

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

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 and solution reproduced as published; topic and difficulty added by this site.