Competition problem — Combinatorics

Library / /16 of 28

Combinatorics Difficulty 7.8 National Olympiad, round 2 Prove it Hong Kong

Decide if there is a permutation $a_1, a_2, \dots, a_{6666}$ of the numbers $1, 2, \dots, 6666$ with the property that the sum $k + a_k$ is a perfect square for all $k = 1, 2, \dots, 6666$ .

Solution

Yes. Consider the permutation
$3, 2, 1, 12, 11, \dots, 4, 23, 22, \dots, 13, 57, 56, \dots, 24, 6666, 6665, \dots, 58.$
More precisely, we define
$a_k = \begin{cases} 2^2 - k & \text{if } 1 \le k \le 3, \\ 4^2 - k & \text{if } 4 \le k \le 12, \\ 6^2 - k & \text{if } 13 \le k \le 23, \\ 9^2 - k & \text{if } 24 \le k \le 57, \\ 82^2 - k & \text{if } 58 \le k \le 6666. \end{cases}$
The result follows readily.

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.