La organización de los números a partir de 1 $$ $$ n, tal que la suma de cada dos números adyacentes es un poder perfecto

Question

He sabido que uno puede organizar todos los números de 1 $de$ a $\color{red}{15}$ en una fila de modo que la suma de cada dos números adyacentes es un cuadrado perfecto.

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

También, hace un par de días, un amigo mío me enseñó que uno puede organizar todos los números desde el 1 $de$ a $\color{red}{305}$ en una fila de modo que la suma de cada dos números adyacentes es un cubo perfecto.

$$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$$

Aquí, tengo una pregunta.

Pregunta : ¿existe al menos un entero positivo $n\ge 2$ satisfacer la siguiente condición por cada $N\ge 2\in\mathbb N$?

Condición : Uno puede organizar todos los números desde $1$ $n$ en una fila de modo que la suma de cada dos números adyacentes es de la forma $m^N$ $m\in\mathbb N$.

Añadido : yo crossposted a MO.

Answer 1

Esto no es una respuesta a la pregunta (que creo que es bien dirigido por Miqueas el comentario de arriba), sino un compendio de diversas observaciones.

En primer lugar, Micah comentario señala que sería muy sorprendente si no había una solución para todos lo suficientemente grande $N$, y el equipo de búsqueda de los osos de esto: que hay soluciones para $N=1,15,16,17, 23,$ y todos los números entre $25 $ y $50 dólares, momento en el que dejé de comprobación. Como $$ N aumenta, el número de soluciones aumenta muy rápidamente; no es 1 solución para $N=15$, diez soluciones para $N=25$, y $17,175$ para $N=35$. El $N=15$ el caso es atípicamente limitada.

Encontrar la solución cuando $N=15$ es muy fácil. Se puede comenzar por la observación de que $9$ es adyacente sólo $7$, y $8$ sólo $1$, por lo que la solución, si existe, se debe comenzar con $9$ y al final con $8$. (O vice-versa, dando a las mismas soluciones a la inversa, que nosotros de ahora en adelante desprecio.) Pero los movimientos de los $9$ se ven obligados: $9-7-2-14-11-5-5-12-13-3$ es la única secuencia posible. Desde $3$ uno puede ir a $1$ o a $6$, y ya va a $1$, evidentemente, no funciona (ya sabemos que $1$ es la siguiente a la última) se debe poner fin a $3-6-10-15-1-8$ y que es la única solución.

Considere el grafo cuyos nodos son $\{1,\ldots, 15\}$ en el que tiene dos nodos están conectados siempre que su suma es un cuadrado. Una solución para el problema es exactamente un camino hamiltoniano en este gráfico. Cuando nos fijamos en este gráfico, la singularidad de la solución es completamente obvio:

y hasta un niño puede ver que sólo hay un único camino hamiltoniano. (Lo sé porque lo he comprobado con mis seis años de edad, hija, que está de acuerdo.) Los gráficos para $N=16$ y $N=17$ son igualmente trivial, y un vistazo a la gráfica para $N=18$ o $N=19$ muestra por qué no hay ninguna solución para los valores:

En $N=20, 21, 22$ la falta de soluciones es fácil de ver, aunque la problemática callejón sin salida en 16 ha sido conectado a 5, a través de 20. Para $N=24$ no veía ninguna razón obvia por la que no hay solución, pero creo que un simple argumento probablemente podría ser hecho implican la disposición de $11, 22, $ y $23$.

No he investigado mucho cubos mucho. Para $N=$ 100 el gráfico no está conectada. Para $N=200$ que está conectado, pero tiene muchas hojas. Incluso para $N=300$ sospecho que hay una manera bastante fácil prueba de que no hay solución, que implica la relativamente independiente de clúster de $\{29, 35, 90, 126, 217, 253, 259\}$ que sólo tiene 4 conexiones con el resto de la gráfica.