Good Neighbors Make Perfect Squares

Draw a graph of 32 vertices, corresponding to each number, and draw an edge between two vertices iff the sum of the numbers on the endpoints is a square. Then we're looking for a Hamiltonian cycle. Now find the Hamiltonian cycle.

Okay, to be honest, I did this by hand and it's terribly, terribly messy. I'm pretty sure we can throw this to some Hamiltonian cycle solver, but I was too lazy to search for it. I found one but I didn't test it.

Here's the rough outline on what I did:

Step 1: Notice that there's an "easy" sequence: $5,31,18,7,29,20,16,9,27,22$ : the neighbors of $31, 18, 29, 16, 27$ are forced, and they chain to each other.

Step 2: Ignore the inner 8 terms in the sequence above, and draw the graph as described above for the remaining 24 terms. Remember that now we're looking for a Hamiltonian path from $5$ to $22$ to complete the cycle.

Step 3: Notice that there are a couple more forced chains:

• $2, 26$ force the sequence $14, 2, 23, 26, 10$ . This also "steals" the edge $13-23$ , so that $13$ is forced to the sequence $3, 13, 12$ .
• $30$ forces the sequence $6, 30, 19$ . This sequence by itself steals the edge $6-19$ , so $19$ is forced to continue to $17$ , making the sequence $6,30,19,17$ .
• $32$ forces the sequence $17, 32, 4$ . Merging with above, this gives $6,30,19,17,32,4$ . This also steals the edge $17-8$ , forcing $1,8,28,21$ .
• Also, a simple force $11,25,24$ .

Step 4: Simplify this behemoth into a "tamer" 13-vertex graph with several forced edges that must belong in the path (namely when those sequences above are contracted into a single edge).

Step 5: Brute force this final task by hand.

Michael Mendrin has given the sequence.

The sum of numbers from 1 to 32 = 528, so therefore it's half of that, or 262. Or something like that, huh?

Here's the string:

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

I don't know how else to do it except by trial and error, starting with the largest numbers, and their neighbors of necessity

$4,32,17$
$5,31,18$
$6,30,19$

....etc.

If I can decide, then I shall leave the chance for others to try by their own. Just take 5 strings at start as follows:

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

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

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

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

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

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

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

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

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

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

Solve the reduced question for answer wanted:

8 1 15

14 2 23

6 3 13

21 4 32

11 5 31

3 6 30

18 7 29

1 8 28

16 9 27

15 10 26

5 11 25

13 12 24

3 13 12

2 14 22

1 15 10

9 16 20

19 17 32

7 18 31

17 19 30

16 20 29

4 21 28

14 22 27

2 23 26

12 24 25

11 25 24

10 26 23

9 27 22

8 28 21

7 29 20

6 30 19

5 31 18

4 32 17

PROGRAM THE 1 TO_32; {This program needs no continual tasks.}

USES CRT;

VAR x: ARRAY[1..32, 1..5] OF BYTE; Path, Slides: ARRAY[1..32] OF BYTE; count, ecount, i, j, p: BYTE; Ok: BOOLEAN; sum: WORD;

BEGIN RANDOMIZE; CLRSCR;

 FOR i:=1 TO 32 DO
     FOR j:=1 TO 5 DO
         x[i,j]:=0;

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

REPEAT sum:=0; FOR i:=1 TO 7 DO Slides[i]:=RANDOM(4); FOR i:=8 TO 24 DO Slides[i]:=RANDOM(3); FOR i:=25 TO 32 DO Slides[i]:=RANDOM(2); Slides[2]:=RANDOM(3); Slides[16]:=RANDOM(2); Slides[18]:=RANDOM(2);

 FOR count:=2 TO 32 DO
     Path[count]:=0;

 count:=1;
 Path[count]:=1;
 REPEAT
      i:=1;
      ecount:=1;
      REPEAT
            Path[count+1]:=x[Path[count], i +Slides[Path[count]]];
            IF x[Path[count], i+1]=0 THEN
               INC(ecount);
            Ok:=TRUE;
            FOR j:=1 TO count DO
                IF Path[count+1]=Path[j] THEN
                   Ok:=FALSE;
            INC(i)
      UNTIL Ok;
      INC(count)
 UNTIL Path[count]=0;
 DEC(count);
 IF count=32 THEN
 BEGIN
      sum:=0;
      FOR j:=1 TO count DO
      BEGIN
           sum:=sum+Path[j];
           WRITE(Path[j], ' ')
      END;
      WRITE('[', count, '] S = ', sum);
      READLN
 END;
 FOR j:=1 TO count DO
     WRITE(Path[j], ' ');
 WRITELN('[', count, '] ', ecount);

UNTIL sum=528; WRITE('This sum is ', sum); READLN END.

Many strings updated:

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

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

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

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

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

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

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

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

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

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

1 8 28 21 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 [32]

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

...

Plenty more strings with other starting. There is only sole ring!

The answer is 262.

First list all the possible ways to combine 1-32 to form perfect squares. there are just 46 or 47 in number . i will explain process in short .

step 1 figure out that 16 , 18 , 25 ,26 ,27 , 28 ,29 ,30, 31 , 32 are forced to forced to form a chain as they have only two pairs which sum to perfect squares eg _( 4 , 32 , 17 ) ( 7 , 18 , 31 ) .

step 2 the number which are forced to form a chain and come in more than one primary chains eg 7 as in (7 ,18,31)(20,29,7) which leads in formation of long chains . after forming a chain observe that numbers in interior of chains can't combine with other numbers , which leads to more chains.

step 3 At last we will get following six independent chains and a free number 15 . ()before and after a chain indicates which number should be preceded or followed . _chains :- _ $(22, 11) 14 , 2 , 23 , 26 , 10 (15 , 6 )$ $(11 , 4 ) 5 , 31 , 18 , 7 , 29 , 20 , 16 ,9 , 27 , 22 (14 , 3 )$ $(21, 12 , 5 ) 4 , 32 , 17 , 19 , 30 , 6 (10 , 3 )$ $(24 , 15 , 3 ) 1,8 , 28 , 21(15 , 4 )$ $(12 , 1)24 , 25 , 11(14 , 5)$ $(22 , 6 ,1)3 , 13 ,12 (24 , 4)$ step 4 Start with any of the chains and make tree diagram . denote the chains as $<14 , 10 >, <5 , 22><4 , 6><1 , 21><24, 11><3 , 12>$ and unique $<15 >$ let $<14 , 10 >$ denote chain from 14 to 10 & $<10 , 14 >$ from 10 to 14 .

I started with <14 , 10 > as you see numbers which must follow this chain i.e. 15 & 6 are in different chains . make the tree diagram using this for forward chains and remember a chain can't come twice and the last chain must end with 22 ,11 (as they are required by 14 )to complete the ring . you will arrive at the unique solution . $14 , 2 , 23 , 26 , 10 ,15, 1,8 , 28 , 21 , 4 , 32 , 17 , 19 , 30 , 6 , 3 , 13 ,12 , 24 , 25 , 11, 5 , 31 , 18 , 7 , 29 , 20 , 16 ,9 , 27 , 22$ and a case which doesn't contain 15 and has the other 31 numbers. i will add the tree diagram later. summing the altermates from 1 gives us the answer $\boxed{262}$

while doing the tree diagram you will find that the six chains without the number 15 also form a single chain with 31 circles on the ring as follows $14 , 2 , 23 , 26 , 10 , 6 ,30 , 19 ,17 , 32, 4 , 21 , 28 , 8 ,1 , 3, 3 , 13 ,12 , 24 , 25 , 11 , 5 , 31 , 18 , 7 , 29 , 20 , 16 ,9 , 27 , 22$