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.
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
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.
The solution is
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.
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.