BMO Short List, 2023

Answer: All integers $n \ge 14$.

We first note that we say the numbers $a$ and $b$ can be ultimately swapped if, after a number of moves, one can obtain the tuple in which only $a$ and $b$ are swapped. We now prove a result.

Claim. If integers $a, b, c \in \{1, 2, \dots, n\}$ are such that the numbers $a, b$ can be ultimately swapped and the numbers $a, c$ can be ultimately swapped, then $b, c$ can be ultimately swapped.

Proof. If we swap $a, b$ then $a, c$ and again $a, b$ it would be the same as swapping just $b, c$.
abc $\rightarrow$ bac $\rightarrow$ bca $\rightarrow$ acb.

Now, consider the graph where vertices correspond to the elements of the set $\{1, 2, \dots, n\}$ and an edge is drawn between two distinct integers whenever their sum is a perfect square. We can swap any numbers when there is an edge between them and by the claim above, any two numbers can be ultimately swapped when there is a path between them. Hence, we can obtain all the possible permutations if and only if this graph is connected.

We observe that any positive integer $x \notin \{1, 2, 4\}$ is connected to a positive integer smaller than $x$. This can be easily seen if $x \le 8$. Suppose $x \ge 9$ and take $n$ such that $n^2 \le x < (n+1)^2$. Then $x$ is connected $(n+1)^2 - x$ and $(n+1)^2 - x \le 2n+1 < n^2 \le x$ holds as $n \ge 3$.

Hence, there are at most 3 connected components in this graph for any $n$. For $n = 12$, we have $\{1, 3, 6, 8, 10\}$, $\{2, 7, 9\}$ and $\{4, 5, 11, 12\}$ as the connected components and the graph is still disconnected. 13 is connected to both 3 and 12, hence it reduces the number of components to 2; finally 14 is connected to 2 and 11 thus when $n \ge 14$, there is a unique connected component.