Saturday Puzzle 3
2006 May 20
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
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.
Alas, I have either made a mistake or the answer is in fact larger than 31 — my attempt at doing away with the problem via coding tells me there are no solutions for 31.
So, my initial computational attack was flawed (I forgot that, having created large blocks, I could flip them around), but having corrected it I still get no solutions for 31. There is, however, at least one solution for 32:
5, 31, 18, 7, 29, 20, 16, 9, 27, 22, 14, 2, 23, 26, 10, 15, 1, 8, 28, 21, 4, 32, 17, 19, 30, 6, 3, 13, 12, 24, 25, 11
As you noticed, establishing that n > 30 can be directly deduced. Getting the first solution was tougher. Nice.