An interesting problem from the wordplay column of the New York Times.
Can you arrange plates numbered 1 to 16, in a circle so the sum of adjacent pairs is always a perfect square?
The quick answer is no, since 16 can only have 9 as its neighbour. But we can obviously adapt and extend the problem as follows:
For what values of n, can you arrange plates numbered from 1 to n, in a line such that the sum of adjacent pairs is always a perfect square?
In this case, 16 is a possible answer and we know that number 16 must be at one of the ends. In fact, there is essentially one solution:
16, 9, 7, 2, 14, 11, 5, 4, 12, 13, 3, 6, 10, 15, 1, 8.
We also note that by fiddling with the ends of the above sequence, n=15 and n=17 are also possible. Certainly, the trivial condition n=1 works.
Is n=15, the smallest non-trivial solution? I think so. We first observe that n=14 cannot work because then 8 can only have one possible neighbour 1, 9 can only have one neighbour 7 and 10 can only have 6. Now if n is less than 14, we see that the chain 2 -7 -9 must appear but there are no possible ways to extend the chain.
So the possible answers are {1, 15, 16, 17}. There must be more. Can we characterize all the possible answers?