Maths Olympiad Prep

Track / Stage 7 / 289 of 300 #2169 of 2444

Problem 2169

National Olympiad second round; IMO P1/P4
Combinatorics Difficulty 7.9 Prove it Baltic Way Shortlist · 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?

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 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.

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