Today is a three-puzzle Saturday.  Answers will be up, posted by readers or by me, by next Friday.  #3 is the most challenging.  Here's a little background:

Sometimes I teach math teachers. One of those math teachers shared this puzzle with me yesterday (warning, I have not yet attempted to solve it).  He was quite proud, one of his 7th graders encountered it in a local mathematics competition and solved it, helping her do very well (she may have won).

Find the smallest number n such that the numbers 1, 2, 3, … , n -1, n can be arranged in a circle, and the sum of every pair of adjacent numbers is a perfect square.

for example:

 6 3 1 5 8 4 2 7

has some good sums:

• 6 + 3 = 9,
• 3 + 1 = 4,
• 1 + 8 = 9,
• but 8 + 7 = 15, no good,
• 7 + 2 = 9,
• 2 + 4 = 6, no good,
• 4 + 5 = 9,
• and 5 + 6 = 11, no good,

but all the sums need to be good

May 23, 2006 pm31 11:22 pm 11:22 pm

I can argue that it’s at least 31, but I don’t have an example yet. 2 obviously doesn’t work. If we have a 3, it needs two possible squares to get to, so we have to go all the way up to 6. Then 6 also needs two possible neighbors, and that obliges us to include 10. Now 10 needs another neighbor, so we have to go up to 15. I initially thought I was done at this point (since 15 has two possible neighbors, 1 and 10), but it turns out that 8 still only has one potential neighbor (since the other square that we can get to is 16 = 8 + 8 which doesn’t help), so we have to go to 17. 17 now needs a second neighbor, so we have to go up to 19. But now 18 has the same problem that 8 did — it’s half a perfect square — and we don’t get to another possible neighbor for it until we get up to 31.

Now, several sections can be seen to be forced fairly quickly:
5, 31, 18, 7, 29, 20, 16, 9, 27, 22 must be a chain as must
6, 30, 19, 17, 8, 28, 21, and also 11, 25, 24 and 10, 26, 23. Obviously, there are still some pieces to be put together.