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.
$\begingroup$
$\endgroup$
4
asked May 15, 2014 at 0:13
-
2$\begingroup$ 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? $\endgroup$– dmkCommented May 15, 2014 at 0:21
-
$\begingroup$ Yes, possible sums are 4 16 and 9 $\endgroup$– most venerable sirCommented May 15, 2014 at 0:46
-
1$\begingroup$ @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. $\endgroup$– BlueCommented May 15, 2014 at 2:42
-
1$\begingroup$ @Blue: I will edit it again. $\endgroup$– Jason ChenCommented May 15, 2014 at 3:52
Add a comment
|
4 Answers
$\begingroup$
$\endgroup$
1
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.
-
$\begingroup$ Love it! I need more methods like this. $\endgroup$ Commented May 15, 2014 at 22:50
$\begingroup$
$\endgroup$
4
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.
-
$\begingroup$ What if you could only arrange digits? $\endgroup$ Commented May 15, 2014 at 0:47
-
$\begingroup$ I think a proof of uniqueness is appropriate. $\endgroup$– MT_Commented May 15, 2014 at 3:52
-
$\begingroup$ 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. $\endgroup$ Commented May 16, 2014 at 1:13
-
$\begingroup$ 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. $\endgroup$– Rich006Commented Jun 23, 2019 at 23:54
$\begingroup$
$\endgroup$
1
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.
-
$\begingroup$ I like the Hamiltonian path observation. $\endgroup$ Commented May 16, 2014 at 1:14
$\begingroup$
$\endgroup$
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.
