53
$\begingroup$

I've known that one can arrange all the numbers from $1$ to $\color{red}{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 $\color{red}{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 $n\ge 2$ satisfying the following condition for each $N\ge 2\in\mathbb N$?

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 $m^N$ for some $m\in\mathbb N$.

Added : I crossposted to MO.

$\endgroup$
  • 1
    $\begingroup$ I wonder if we could also add a boundary condition - so that sum of the first and the last number is a perfect power. $\endgroup$ – Wojowu Feb 28 '15 at 12:07
  • 1
    $\begingroup$ @Elaqqad: One can have $n=16$ and $n=17$ trivially because you can add $16$ at the end and add $17$ in front of $8$. $\endgroup$ – mathlove Feb 28 '15 at 15:11
  • 17
    $\begingroup$ For fixed $n$ and $N$, this is equivalent to asking whether some graph on $n$ vertices with $O(n^{1+1/N})$ edges has a Hamiltonian path. This is substantially above the threshold for a random graph to have a Hamiltonian path (which happens when the expected number of edges is $O(n \log n)$ or so), so the answer is probably "yes" unless there's some interesting structure in this specific graph that interferes with your chances. $\endgroup$ – Micah Feb 28 '15 at 16:42
  • 1
    $\begingroup$ The smallest cyclic solution (where the sum of the first and last numbers is also a square) has $N=32: 1, 8, 28, 21, 4, 32, 17, 19, 30, 6, 3, 13, 12, 24, 25, 11, 5, 31, 18, 7, 29, 20, 16, 9, 27, 22, 14, 2, 23, 26, 10, 15$ for example. There are 32 of these. $\endgroup$ – MJD Mar 1 '15 at 17:56
  • 1
    $\begingroup$ @Micah I think you should post that comment as an answer; it is very much to the point. $\endgroup$ – MJD Mar 1 '15 at 18:05
11
$\begingroup$

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: $9-7-2-14-11-5-5-12-13-3$ 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 $3-6-10-15-1-8$ and that is the only solution.

Consider the graph whose nodes are $\{1,\ldots, 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 much investigated cubes much. 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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.