# Number puzzle, number arrangement

Arrange all of the digits from the numbers 1 through 15 in such a order that the sum of any adjacent pair is a perfect square. No repeats. I can be staring at those number for days. But I wonder if there is a trick.

-
Have you tried writing the numbers 1 through 15 down in a column and then listing all the possible numbers each can be paired with? – dmk May 15 '14 at 0:21
Yes, possible sums are 4 16 and 9 – user11355 May 15 '14 at 0:46
@JasonChen: By editing the phrase "all digits from numbers $1$ to $15$" into "all numbers from $1$ to $15$", you have changed the nature of the problem. As it turns out, the digit puzzle has no solution ---there are too many $1$s, and not enough $0$s, $3$s, and $8$s to put next to them--- so it's possible (perhaps even likely) that the original problem statement is in error. However, notice that OP's comment to Anthony's answer specifically re-asks about arranging digits, so the original problem statement seems to be precisely what OP intended. – Blue May 15 '14 at 2:42
@Blue: I will edit it again. – Jason Chen May 15 '14 at 3:52

To perhaps simplify the suggestion I made above: Try writing each number from 1 through 15 in a column. Next to each, write all the numbers that are greater than that number and that can be added to that number to form a perfect square. For example:

1: 3, 8, 15

2: 7, 14

And so forth. For some of these numbers, you'll find your options are limited: There are very few other numbers they can be paired with. That will, in turn, restrict where in your string you can put them. With that in mind, draw a series of fifteen blanks and start putting in the numbers that must go in specific positions.

Let me know if you have questions.

-
Love it! I need more methods like this. – user11355 May 15 '14 at 22:50

The solution is

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


You could also reverse the order.

The trick is to first realize that the included numbers cover only 4 possible squares - 4, 9, 16, 25.

From there you simply pair numbers to reach these squares.

-
What if you could only arrange digits? – user11355 May 15 '14 at 0:47
I think a proof of uniqueness is appropriate. – Soke May 15 '14 at 3:52
I saw no way to arrange digits to make it work (as Blue had mentioned.) I assumed that the "digits" was a misprint and the integers from the set containing 1 - 15 was what was actually intended. – Anthony Gatlin May 16 '14 at 1:13

This answer is based on the original problem statement (reiterated in OP's comment to Anthony's answer), which asks about arranging the digits from the numbers $1$ to $15$, so that the sum of any adjacent pair is a perfect square.

Notice that there are eight "$1$"s available, from $1$, $10$, $11$, $12$, $13$, $14$, $15$. So, the list looks like this: $$\dots 1 \dots 1 \dots 1 \dots 1 \dots 1 \dots 1 \dots 1 \dots 1 \dots$$ The leading and trailing "$\dots$"s may be empty, but since $1+1$ is not a perfect square, each pair of "$1$"s must be separated by at least one other digit.

The only digits that can go next to a "$1$" are: "$0$" (of which you have one available, from $10$), "$3$" (of which you have two, from $3$ and $13$), and "$8$" (of which you have one, from $8$). That's only four available candidates, but we have at least seven $1$-separating slots to fill.

The puzzle, as originally stated, has no solution.

-

Write down the numbers between $1$ and $15$. Now connect any two numbers iff their sum is a square. Note that you just have to, for each number, calculate its differences from next few bigger squares and connect it to those differences. For example, for $3$, we compute $4-3$, $9-3$, $16-3$, and any larger squares and the differences won't be between $1$ and $15$, so we can stop here.

Now you're looking for a Hamiltonian path through that graph.

-
I like the Hamiltonian path observation. – Anthony Gatlin May 16 '14 at 1:14