Solution to the Problem: Here are some solutions:
1, 3, 13, 36, 28, 21, 15, 34, 30, 19, 6, 10, 26, 23, 2, 7, 18, 31, 33, 16, 9, 27, 22, 14, 35, 29, 20, 5, 11, 25, 24, 12, 4, 32, 17, 8 - back to 1
1 – 8 – 17 – 32 – 4 – 12 – 24 – 25 – 11 – 5 – 20 – 16 – 9 – 27 – 22 – 14 – 2 – 23 – 26 – 10 – 6 – 19 – 30 – 34 – 15 – 21 – 28 – 36 – 13 – 3 – 33 – 31 – 18 – 7 – 29 – 35 – (back to 1)
1 - 3 - 6 - 19 - 30 - 34 - 2 - 23 - 26 - 10 - 15 - 21 - 4 - 32 - 17 - 8 - 28 - 36 - 13 - 12 - 24 - 25 - 11 - 5 - 20 - 29 - 7 - 18 - 31 - 33 - 16 - 9 - 27 - 22 - 14 - 35 - back to 1
Kamal Lohia suggested a good way to begin solving the problem:
Possible pair-ups:
1: 3, 8, 15, 24, 35
2: 7, 14, 23, 34
3: 1, 6, 13, 22, 33
4: 5, 12, 21, 32
5: 4, 11, 20, 31
6: 3, 10, 19, 30
7: 2, 9, 18, 29
8: 1, 17, 28
9: 7, 16, 27
10: 6, 15, 26
11: 5, 14, 25
12: 4, 13, 24
13: 3, 12, 23, 36
14: 2, 11, 22, 35
15: 1, 10, 21, 34
16: 9, 20, 33
17: 8, 19, 32
18: 7, 31
19: 6, 17, 30
20: 5, 16, 29
21: 4, 15, 28
22: 3, 14, 27
23: 2, 13, 26
24: 1, 12, 25
25: 11, 24
26: 10, 23
27: 9, 22
28: 8, 21, 36
29: 7, 20, 35
30: 6, 19, 34
31: 5, 18, 33
32: 4, 17
33: 3, 16, 31
34: 2, 15, 30
35: 1, 14, 29
36: 13, 28
Now the numbers with only two possible partners must be paired with them only.
So, we have: 7-18-31, 11-25-24, 10-26-23, 9-27-22, 4-32-17 and 13-36-28
This would be a good starting point. These can be seen in six different colours in the image below provided by Colin Bowey.
Colin Bowey gets extra credit for sending in thirty-one unique solutions to the problem:
Click here to download a file in Excel which displays the thirty-one solutions in a circle
Colin really went all out on this problem and here is his explanation. He used Visual Basic in Excel to search for solutions for ranges 1 to N, just to see how the number of solutions grows as N increases.
The code models the problem as a graph in which the integers 1 through N are treated as vertices, and an edge is drawn between two vertices whenever the sum of the corresponding numbers is a perfect square.
The task of arranging the numbers in a circle so that adjacent pairs sum to a square then becomes equivalent to finding Hamiltonian cycles in this square-sum graph.
The solver constructs the graph and performs a depth-first backtracking search to explore possible paths, extending partial sequences only along valid edges and retreating whenever a path cannot be completed.
For the range 1 to 36 there are six numbers in the square-sum graph that have only two possible neighbours. Since every vertex in a Hamiltonian cycle must have exactly two adjacent vertices, these degree-two vertices force those edges to appear in any valid solution, effectively locking them into small chains (see below):
7 — 18 — 31
11 — 25 — 24
10 — 26 — 23
9 — 27 — 22
4 — 32 — 17
13 — 36 — 28
To avoid counting duplicate solutions, symmetry is reduced by fixing the starting value at 1 and eliminating reversed duplicates.
Each Hamiltonian cycle therefore corresponds to a unique circular arrangement in which every neighbouring pair of numbers sums to a perfect square.
The first range for which I found a solution was 1 to 32.
The vertex 18 in the square-sum graph requires both 7 and 31 as neighbours.
Therefore the range must extend at least to 31 before a Hamiltonian cycle can even be possible.
However, when the range is limited to 31 the graph contains many additional degree-two vertices (such as 16, 17, 28, 29 and 30), which introduces many forced segments and makes it extremely difficult (in this case impossible) to form a single cycle.
Only when the range is extended slightly further does the graph gain enough additional connections to allow valid circular arrangements to appear.
From 1 to 32, I generated solutions for each range up to 1 to 44.
One interesting observation is the rapid increase in search time. For example:
N=43 took about 8 minutes 18 seconds
N=44 jumped to over 2 hours
That's the reason I stopped at 44. My guess is that searching 1 to 45 might take a couple of days!
It would be interesting to try to predict both how many solutions exist for N=45 and how long the search might take.
Another curious observation was that:
N=38 has 25 solutions
N=40 has 64 solutions
which are themselves perfect squares.
Now, for some real fun, you can download an Excel file in which you can display any of the solutions for number 1 to 32 up to 1 to 44.
Click here to download a file in Excel in which you can enter any N from 32 to 44.