Summing To Squares

The the next square, after 16 is 25, followed by 36. 16 + 0 = 16 isn't an option, nor is 16 + 20 = 36 (or any greater square.) Therefore 16 must be on one end or the other of the line next to 9 (as 16 + 9 = 25). At this point, you're done if you're thinking only about the multiple choice options. However, it's easy to continue the line starting from:

$\large \{ 16, 9... \}$

9 + 7 = 16 is the only other possibility for using 9 to make a perfect square.
Then 7 + 2 = 9 is the only other way to use 7.
2 + 14 = 16 is the only other way to use 2.
etc...
14 + 11 = 25
11 + 5 = 16
5 + 4 = 9
4 + 12 = 16
12 + 13 = 25
13+3 = 16
3 + 1 = 4 or 3 + 6 = 9
1 + 8 = 9 or 6 + 10 = 16
8 :( --> must cont. 10 + 15 = 25
then 15 + 1 = 16
and lastly, 1 + 8 = 9

Altogether, the sequence is:

$\large \{16, 9, 7, 2, 14, 11, 5, 4, 12, 13, 3, 6, 10, 15, 1, 8 \}$

To be honest -- it surprised me that this worked out so well. I wonder why/when else this kind of sequence is possible and unique generalizing to using the set of numbers 1- $n$ and making a set of 2 or 3 'allowed targets' that every pair of adjacent numbers must sum to (in this case, the set was $\{9, 16, 25\}$ . Would any other choice for these numbers work or is there a reason why the squares are special?

In any case, great problem!

Observing all possible pairs of the integers from 1 to 16 that add to a perfect square, one finds that 8 only pairs with 1, and 16 only pairs with 9. Therefore 8 and 16 must be on the end of such a sequence because any number in the middle must pair at least two different ways to make a perfect square. This answers the question posed.

For completeness, here are the actual sequences.

There are two sequences possible,

16 9 7 2 14 11 5 4 12 13 3 6 10 15 1 8

and it's reverse

8 1 15 10 6 3 13 12 4 5 11 14 2 7 9 16.

Only 1 can be combined three ways to make a perfect square, the rest, except 8 and 16, have exactly two. By starting with 16 9 all the choices for next number are forced since there is only one other number available to make a perfect square. This makes the sequence above the only possible sequence starting with 16 9. Since that sequence will be forced from the end where16 9 occurs, and 16 9 or 9 16 must be at one end or other, the only option for another sequence is the one found above in reverse order.

The possible sum of two numbers is obviously between 4, 9, 16 and 25. It can't be 36 because the sum of the two largest number is 31. And then I look for the numbers that can be added to the choices to make it a Perfect Square. I noticed that there is only one number that can be added to the numbers 8 and 16 to make it a Perfect Square, 1 for no. 8 and 9 for no. 16. Since there is only one number that can be added to the numbers 8 and 16 they should be placed in the first or last number in these Sequence. And that's why this question is Categorized as Logic.