Arranging numbers from 11 to nn such that the sum of every two adjacent numbers is a perfect power

I’ve known that one can arrange all the numbers from 1 to 15 in a row such that the sum of every two adjacent numbers is a perfect square.


Also, a few days ago, a friend of mine taught me that one can arrange all the numbers from 1 to 305 in a row such that the sum of every two adjacent numbers is a perfect cube.

51,292,220,123,2,6,21,195,148,68,275,237,106,110,233,279,64,152,191,25, 100,243,269,74,142,201,15,12,204,139,77,266,246,97,119,224,288,55,161,

Here, I have a question.

Question : Does there exist at least one positive integer n2 satisfying the following condition for each N2N?

Condition : One can arrange all the numbers from 1 to n in a row such that the sum of every two adjacent numbers is of the form mN for some mN.

Added : I crossposted to MO.


This is not an answer to the question (which I think is well-addressed by Micah’s comment above) but a compendium of miscellaneous observations.

First, Micah’s comment points out that it would be very surprising if there were not a solution for all sufficiently large N, and computer search bears this out: there are solutions for N=1,15,16,17,23, and all numbers between 25 and 50, at which point I stopped checking. As N increases, the number of solutions increases very rapidly; there is 1 solution for N=15, ten solutions for N=25, and 17,175 for N=35. The N=15 case is atypically constrained.

Finding the solution when N=15 is very easy. One can begin by observing that 9 is adjacent only to 7, and 8 only to 1, so the solution, if it exists, must begin with 9 and end with 8. (Or vice-versa, giving the same solutions in reverse, which we henceforth disregard.) But the moves from 9 are forced: 97214115412133 is the only sequence possible. From 3 one can go to 1 or to 6, and since going to 1 evidently doesn’t work (since we know 1 is next-to-last) it must end 36101518 and that is the only solution.

Consider the graph whose nodes are {1,,15} in which has two nodes are connected whenever their sum is a square. A solution to the problem is exactly a hamiltonian path in this graph. When we look at this graph, the uniqueness of the solution is completely obvious:

adjacency graph with hamiltonian path

and even a child can see that there is only a single hamiltonian path. (I know because I checked with my six-year-old daughter, who agrees.) The graphs for N=16 and N=17 are similarly trivial, and a glance at the graph for N=18 or N=19 shows why there is no solution for those values:

graph with N=18 or 19 has no hamiltonian cycle

In N=20,21,22 the lack of solutions is still easy to see, although the troublesome dead end at 16 has been connected to 5 via 20. For N=24 I did not see any obvious reason why there is no solution, but I think a simple argument could probably be made involving the disposition of 11,22, and 23.

I have not done much investigation of the analogous problem where two numbers are connected if their sum is a perfect cube. For N=100 the graph is not even connected. For N=200 it is connected, but has many leaves. Even for N=300 I suspect there is a fairly easy proof that there is no solution, involving the relatively independent cluster of {29,35,90,126,217,253,259} which has only 4 connections to the rest of the graph.

Source : Link , Question Author : mathlove , Answer Author :
5 revs

Leave a Comment