Maths Olympiad Prep

Library / /6 of 11

, 2025

Combinatorics Difficulty 6.8 National Olympiad Prove it Czech-Polish-Slovak Mathematical Match

The plane was divided by vertical and horizontal lines into unit squares. Determine whether it is possible to write integers into cells of this infinite grid so that:
(i) every cell contains exactly one integer
(ii) every integer appears exactly once
(iii) for every two cells AA and BB sharing exactly one vertex, if they contain integers aa and bb then at least one of the cells sharing a common side with both AA and BB contains an integer between aa and bb.

Solution

Yes, this is possible. Consider the spiral depicted below and write consecutive integers along the spiral:
Figure 1

We claim that this works. Consider any two cells AA and BB sharing exactly one vertex. Consider the 2×22 \times 2 square containing AA and BB. If the 2×22 \times 2 square contains a "corner" of the spiral then for some nn and kk the numbers in that 2×22 \times 2 square are arranged in the following way (up to rotation or reflection):
n+1knn1 \begin{array}{|c|c|} \hline n+1 & k \\ \hline n & n-1 \\ \hline \end{array}
and therefore the conditions are satisfied no matter which opposite cells of the 2×22 \times 2 square AA and BB are. Indeed, if AA and BB contain n1n-1 and n+1n+1, then the good cell is the one containing nn. If AA and BB contain nn and kk and n<kn < k then n<n+1<kn < n+1 < k and the good cell is the one containing n+1n+1. If AA and BB contain nn and kk and n>kn > k then k<n1<nk < n-1 < n and the good cell is the one containing n1n-1.

Otherwise, the numbers are arranged in the following way (again, up to rotation or reflection):
k+1knn+1 \begin{array}{|c|c|} \hline k+1 & k \\ \hline n & n+1 \\ \hline \end{array}

for some n,kn, k, and again, the conditions are satisfied. Indeed, without loss of generality, assume n<kn < k. Then n<n+1<k<k+1n < n+1 < k < k+1. If AA and BB contain nn and kk then the good cell is the one containing n+1n+1. Otherwise, AA and BB contain n+1n+1 and k+1k+1, and the good cell is the one containing kk.

Alternatively, one can notice that condition (iii) from the problem statement means that we can orient each square 2×22 \times 2 according to the increasing numbers as suggested in the picture below:
Figure 2
With this observation, it's relatively easy to check that the spiral construction satisfies this.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.