67
$\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$
10
  • 2
    $\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, 2015 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, 2015 at 15:11
  • 23
    $\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, 2015 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, 2015 at 17:56
  • 2
    $\begingroup$ @Micah I think you should post that comment as an answer; it is very much to the point. $\endgroup$
    – MJD
    Mar 1, 2015 at 18:05

1 Answer 1

16
$\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-4-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 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.

$\endgroup$
5
  • $\begingroup$ "For 𝑁=100 the graph is not even connected. " How could this be true? Let N be large enough so that 2, 3, 4 is connected to 1 (N>=14 suffices). N Given N >= n > 4, let q^2 so that n < q^2 < 2n. Then q^2-n < n: apply induction $\endgroup$
    – fritz
    Oct 3, 2020 at 1:10
  • $\begingroup$ That paragraph discusses the graphs where $a$ and $b$ are connected if $a+b$ is a cube. $\endgroup$
    – MJD
    Oct 3, 2020 at 2:42
  • $\begingroup$ Not at all! After your comment I realized that my last paragraph was very unclear, so I rewrote it to be more explicit. Thanks for helping me improve my answer. $\endgroup$
    – MJD
    Oct 3, 2020 at 10:44
  • 1
    $\begingroup$ A proof of no solution for N=24: Suppose there is a Hamiltonian path. The only leaf is 18, so that must be an endpoint of the path. Analyzing the path through 7 and 14, we can find that either 2, 9, 11, or 22 must be the other endpoint. All other vertices of degree 2 must be internal to the path. We can thus identify a subpath: 4,21,15,10,6,19,17,8,1,24,12. 4 and 12 thus cannot be neighbors, so 12 must neighbor 13. 13's other neighbor must be 23. Thus none of 6, 1, and 13 can neighbor 3. Thus 3's only possible neighbor is 22. But 3 is not an endpoint, so this is a contradiction. $\endgroup$
    – isaacg
    Feb 14, 2023 at 20:39
  • $\begingroup$ Very nice, thank you! $\endgroup$
    – MJD
    Feb 14, 2023 at 23:43

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .