Competition problem — Combinatorics

Library / /16 of 53

Combinatorics Difficulty 5.7 AIME, harder Prove it China

We say a positive integer $n$ is "good" if there is a permutation $(a_1, a_2, \dots, a_n)$ of $1, 2, \dots, n$ such that $a_k + k$ is a perfect square for all $1 \le k \le n$ . Determine all the good numbers in the set $\{11, 13, 15, 17, 19\}$ .

Solution

The good numbers are $13$ , $15$ , $17$ and $19$ . However $11$ is not.

Note that for $1 \le k \le 11$ , $4 + k$ is a perfect square if and only if $k = 5$ . Likewise, $11 + k$ is a perfect square if and only if $k = 5$ . Hence $11$ is not good.

Note that $13$ is good because

$k$ : 1 2 3 4 5 6 7 8 9 10 11 12 13,
$a_k$ : 8 2 13 12 11 10 9 1 7 6 5 4 3.

Similarly, $15$ , $17$ and $19$ are good because

$k$ : 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15,
$a_k$ : 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1;

$k$ : 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17,
$a_k$ : 3 7 6 5 4 10 2 17 16 15 14 13 12 11 1 9 8;

$k$ : 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19,
$a_k$ : 8 7 6 5 4 3 2 1 16 15 14 13 12 11 10 9 19 18 17.

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.