Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
10  
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
add comment

1 Answer 1

up vote 16 down vote accepted

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} $$

share|improve this answer
    
Thanks, this is a great answer! –  Dean Young Dec 27 '12 at 0:47
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.