Maths Olympiad Prep

Library / /57 of 397

Combinatorics Difficulty 5.1 AIME, harder Prove it Taiwan

A "defective grid" is a figure formed by three unit squares (with side length 1): or any figure obtained from this figure by rotation and reflection.

a. Under the condition that any two "defective grids" do not overlap each other, can 3×6713 \times 671 "defective grids" be used to completely cover a 3×20133 \times 2013 large square grid?

b. Under the condition that any two "defective grids" do not overlap each other, can 5×6715 \times 671 "defective grids" be used to completely cover a 5×20135 \times 2013 large square grid?

Figure 1

Solution

a. No.
Figure 2
In the 3×20133 \times 2013 large square grid, mark the cells (1,2k+1)(1,2k+1) and (3,2k+1)(3,2k+1), for k=0,1,2,...,2006k=0,1,2,...,2006, with an "*", as shown in the figure above. Each "defective grid" can cover at most one "*", so at least 2014 "defective grids" are needed to completely cover these "*"s. Therefore 3×671(=2013)3 \times 671(= 2013) "defective grids" cannot completely cover the 3×20133 \times 2013 large square grid.

b. Yes.
Figure 3
A 2×62 \times 6 and a 3×63 \times 6 large square grid can also be completely covered by "defective grids". From this we know that a 5×65 \times 6 large square grid can be completely covered by "defective grids". Also, a 5×95 \times 9 large square grid can be completely covered by 15 "defective grids"; the figure above shows one possible method. Therefore a 5×(6k+9)5 \times (6k+9) large square grid (where kk is any non-negative integer) can always be completely covered by "defective grids". Hence the 5×2013=5×(6⋅334+9)5 \times 2013 = 5 \times (6 \cdot 334 + 9) large square grid can be completely covered by "defective grids".

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 translated into English from zh; metadata (topic, difficulty) added by this project.