# Group of permutations

Which $S_n$ have an element $\sigma$ such that $\sigma (i) + i$ is always a perfect square?

-
Why do you want to know this? It's a rather weird question, no? – Mariano Suárez-Alvarez Dec 26 '12 at 7:36
Nice answer though! – Geoff Robinson Dec 26 '12 at 22:47
A math competition I was in recently had this question on it. The other questions were all more interesting than this, so I thought I must be missing something. Turns out it is just a weird question and nothing else. – Dean Young Dec 27 '12 at 0:44

It seems to be true for $n=3,5,8,9,10$ and then all integers $n$ from $12$ to at least $100$.

EDIT: Yes, this is true. Let $k^2$ be a square greater than $n$ but less than $2n$. Take $\sigma(j) = k^2 - j$ for $j$ from $k^2 - n$ to $n$. Thus $(\sigma(k^2-n), \ldots, \sigma(n))$ are a permutation of $(k^2-n, \ldots, n)$. This reduces the problem for $n$ to the problem for $k^2 - n - 1$.
Now for all integers $n \ge 27$ there is such a $k$ with $k^2 - n - 1 \ge 12$ (because $\sqrt{2n} - \sqrt{n+13} \ge 1$), so once we find such a permutation for all $n$ from $12$ to $26$ we know that there is one for all $n \ge 27$.

Here are suitable permutations for all $n$ up to $26$ for which such permutations exist:

\eqalign{ 3 & [3, 2, 1] \cr 5 & [3, 2, 1, 5, 4] \cr 8 & [8, 7, 6, 5, 4, 3, 2, 1] \cr 9 & [8, 2, 6, 5, 4, 3, 9, 1, 7] \cr 10 & [3, 2, 1, 5, 4, 10, 9, 8, 7, 6] \cr 12 & [3, 2, 1, 12, 11, 10, 9, 8, 7, 6, 5, 4] \cr 13 & [8, 2, 13, 12, 11, 10, 9, 1, 7, 6, 5, 4, 3] \cr 14 & [3, 2, 1, 5, 4, 10, 9, 8, 7, 6, 14, 13, 12, 11] \cr 15 & [8, 2, 6, 5, 4, 3, 9, 1, 7, 15, 14, 13, 12, 11, 10] \cr 16 & [15, 7, 1, 5, 4, 3, 2, 8, 16, 6, 14, 13, 12, 11, 10, 9] \cr 17 & [15, 7, 1, 5, 4, 3, 2, 17, 16, 6, 14, 13, 12, 11, 10, 9, 8] \cr 18 & [15, 14, 13, 12, 11, 10, 18, 17, 16, 6, 5, 4, 3, 2, 1, 9, 8, 7] \cr 19 & [3, 2, 1, 5, 4, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6] \cr 20 & [15, 14, 13, 12, 20, 19, 2, 1, 7, 6, 5, 4, 3, 11, 10, 9, 8, 18, 17, 16] \cr 21 & [15, 14, 1, 12, 20, 10, 2, 8, 7, 6, 5, 13, 3, 11, 21, 9, 19, 18, 17, 16, 4] \cr 22 & [3, 2, 22, 21, 4, 19, 9, 1, 7, 6, 5, 13, 12, 11, 10, 20, 8, 18, 17, 16, 15, 14] \cr 23 & [15, 23, 22, 21, 20, 19, 18, 1, 16, 6, 14, 13, 12, 11, 10, 9, 8, 7, 17, 5, 4, 3, 2] \cr 24 & [8, 2, 22, 5, 4, 10, 9, 1, 7, 6, 14, 24, 23, 11, 21, 20, 19, 18, 17, 16, 15, 3, 13, 12] \cr 25 & [8, 23, 22, 21, 4, 3, 9, 1, 7, 6, 5, 24, 12, 2, 10, 20, 19, 18, 17, 16, 15, 14, 13, 25, 11] \cr 26 & [15, 14, 22, 21, 20, 19, 18, 17, 16, 26, 25, 24, 23, 2, 1, 9, 8, 7, 6, 5, 4, 3, 13, 12, 11, 10] \cr }

EDIT: For completeness, to show that there are no solutions for $n=2,4,6,7,11$, in each of those cases we find a set $A$ such that the set $B = \{b: 1 \le b \le n,\ a + b \text{ is a square for some }a \in A\}$ has cardinality less than that of $A$.

$$\begin{array}{c l l} n & A & B\cr 2 & \{1\} & \emptyset \cr 4 & \{4\} & \emptyset \cr 6 & \{1,6\} & \{3\} \cr 7 & \{1,6\} & \{3\} \cr 11 & \{4,11\} & \{5\} \cr \end{array}$$

-
Thanks, this is a great answer! – Dean Young Dec 27 '12 at 0:47