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.

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

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.

256,87,129,214,298,45,171,172,44,299,213,130,86,257,255,
88,128,215,297,46,170,173,43,300,212,131,85,258,254,89,127,216,296,
47,169,174,42,301,211,132,84,259,253,90,126,217,295,48,168,175,41,302,
210,133,83,260,252,91,125,218,294,49,167,176,40,303,209,134,82,261,251,
92,33,183,160,56,287,225,118,98,245,267,76,140,203,13,14,202,141,75,268,
244,99,26,190,153,63,280,232,111,105,238,274,69,147,196,20,7,1,124,219,
293,50,166,177,39,304,208,135,81,262,250,93,32,184,159,57,286,226,117,8,
19,197,146,70,273,239,104,112,231,281,62,154,189,27,37,179,164,52,291,221,
122,3,5,22,194,149,67,276,236,107,109,234,278,65,151,192,24,101,242,270,
73,143,200,16,11,205,138,78,265,247,96,120,223,289,54,162,181,35,29,187,
156,60,283,229,114,102,241,271,72,144,199,17,108,235,277,66,150,193,23,
4,121,222,290,53,163,180,36,28,188,155,61,282,230,113,103,240,272,71,145,
198,18,9,116,227,285,58,158,185,31,94,249,263,80,136,207,305,38,178,165,
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,
182,34,30,186,157,59,284,228,115,10,206,137,79,264,248,95

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.

Answer

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.

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

Leave a Comment