Back in An Arrangement of 15 you were asked to place the numbers 1 to 15 in a line so that any two adjacent numbers summed to a square number.

Now, try to arrange the numbers from 1 to 32 in a circle, so any two adjacent numbers again sum a square number.

(In reply to Non-Computer-Aided Solution by np_rt)

np_rt, I used the exact same approach as you did. I just wanted to pick up where you left off and show that Trial and Error is not required to get to the final solution.

"We have the following mini-sequences:

(22,27,9,16,20,29,7,18,31,5)
(4,32,17,19,30,6)
(14,2,23,26,10)
(1,8,28,21)
(11,25,24)
(3,13,12)
(1,15,10) or (10,15,21)"

I will rewrite the first 6 mini-sequences, and on each end of each sequence I’ll put the possible neighbors that end could have:

(3,14)    22,27,9,16,20,29,7,18,31,5 (4,11)
(5,12,21) 4,32,17,19,30,6            (3,10)
(11,22)   14,2,23,26,10              (6,15)
(3,15,24) 1,8,28,21                  (4,15)
(5,14)    11,25,24                   (1,12)
(1,6,22)  3,13,12                    (4,24)

As you said, (1,15,10) and (10,15,21) are the only possibilities for what 15 could be paired with. Either way, 10 MUST be next to 15. This means we can add 15 to the 14…10 sequence. Also, we must remove 10 from being a possible neighbor for 6. And we have:

(3,14)    22,27,9,16,20,29,7,18,31,5 (4,11)
(5,12,21) 4,32,17,19,30,6            (3)
(11,22)   14,2,23,26,10,15           (1,21)
(3,15,24) 1,8,28,21                  (4,15)
(5,14)    11,25,24                   (1,12)
(1,6,22)  3,13,12                    (4,24)

So 3 must be 6’s other neighbor. This means we can add the 3,13,12 string to the 4…6,3 string. This also removes 3 from being a possible neighbor for 22 or 1. And we have:

(14)      22,27,9,16,20,29,7,18,31,5 (4,11)
(5,12,21) 4,32,17,19,30,6,3,13,12    (4,24)
(11,22)   14,2,23,26,10,15           (1,21)
(15,24)   1,8,28,21                  (4,15)
(5,14)    11,25,24                   (1,12)

Well, now look at the 4…12 sequence. Notice that 12’s neighbors could be 4 or 24. But 4 is on the other end of the sequence, so it actually CAN’T be 12’s neighbor. Therefore 24 must be, and we can add the 24,25,11 sequence to the 4…12 sequence. Also, we must remove 24 from being a neighbor for 1, and also remove 12 from being a neighbor for 4. And we have:

(14)     22,27,9,16,20,29,7,18,31,5       (4,11)
(5,21)   4,32,17,19,30,6,3,13,12,24,25,11 (5,14)
(11,22)  14,2,23,26,10,15                 (1,21)
(15)     1,8,28,21                        (4,15)

15 has to be 1’s other neighbor. So we can add the 1…21 sequence to the 14…15 sequence. This removes 15 from being a neighbor for 21. And we have:

(14)     22,27,9,16,20,29,7,18,31,5       (4,11)
(5,21)   4,32,17,19,30,6,3,13,12,24,25,11 (5,14)
(11,22)  14,2,23,26,10,15,1,8,28,21       (4)

From the fact that 14 must be 22’s neighbor and 4 must be 21’s neighbor, we can confirm that the two ends (11 and 5) are legal neighbors, and get the final solution that everyone else found too:

1, 15, 10, 26, 23, 2, 14, 22, 27, 9, 16, 20, 29, 7, 18, 31, 5, 11, 25, 24, 12, 13, 3, 6, 30, 19, 17, 32, 4, 21, 28, 8

See, no trial and error needed =)

Posted by nikki on 2005-01-10 19:42:40