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.
Asked
Active
Viewed 1.2k times
1
-
2Have 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 00:21
-
Yes, possible sums are 4 16 and 9 – most venerable sir May 15 '14 at 00:46
-
1@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 02:42
-
1@Blue: I will edit it again. – Jason Chen May 15 '14 at 03:52
4 Answers
6
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.
dmk
- 2,228
3
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.
Anthony Gatlin
- 139
-
-
-
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 01:13
-
Here's the proof that Anthony Gatlin's solution is the only solution: 16 is the only perfect square reachable by adding 9 to any other number in the set 1-15. Thus 9 must be next to 7 and no other number, so therefore 9 must be on the end with 7 next. By similar logic, 2 must be next to 7, 14 must be next to 2, and so on. – Rich006 Jun 23 '19 at 23:54
3
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.
Jack M
- 27,819
- 7
- 63
- 129
2
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.
Blue
- 75,673