Maths Olympiad Prep

Library / /4 of 31

Combinatorics Difficulty 7.9 National olympiad, round 2 Prove it Baltic Way

One of the cells of 20×2020 \times 20 torus contains a buried treasure. Today, in order to find the treasure we select several rectangles 1×41 \times 4 or 4×14 \times 1 on this torus and ask the sapper to investigate them by a mine detector. The results of all investigations will be known tomorrow, for each rectangle the sapper will tell us if the treasure is in this rectangle. What is the minimal number of rectangles we should select in order to find the cell that contains the treasure?

Solution

Answer: 160.
In our torus each cell is determined by coordinates (i,j)(i, j), 1i,j201 \le i, j \le 20, the two cells being neighbours if one of their coordinates is the same, and the others differ by ±1mod20\pm 1 \bmod 20.

Example. Select the following 160 rectangles
(a1,b);(a2,b);(a3,b);(a4,b)(mod20),where 5(a+b),and(a,b1);(a,b2);(a,b3);(a,b4)(mod20),where 5(a+b1). (a-1,b); (a-2,b); (a-3,b); (a-4,b) \pmod{20}, \quad \text{where } 5 \mid (a+b), \quad \text{and} \\ (a,b-1); (a,b-2); (a,b-3); (a,b-4) \pmod{20}, \quad \text{where } 5 \mid (a+b-1).
If the sapper says that the treasure belongs to only one of the rectangles, then the cell is uniquely determined, because each rectangle contains the unique cell not covered by the other rectangles. If the sapper says that the treasure belongs to two of rectangles then the treasure is in their intersection cell.

Estimation. Suppose that we select 159 rectangles only. It is clear that the torus is fully covered by the rectangles except at most one cell. Therefore at least 39921594=162399 \cdot 2 - 159 \cdot 4 = 162 is covered by only one rectangle, and hence two of these cells belong to the same rectangle. If the rectangle contains the treasure we can not distinguish on which of these cells it is hidden.

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.