Si el conjunto permutado de $(1,2, \dots n ) $ es esa suma de cualquier dos números adyacentes es un cuadrado. Encontrar la forma generalizada de $n$.

Question

$ \text{Let}$$ P(n) \text{be permutation of}$$ (1,2 \dots n)$$ \text{such that if}$$ P(n)={a_1,a_2, \dots a_n} $$ \text{then} $$(a_i+a_{i+1})=k^2$$ \text{where}$$ k\in \mathbb{N}$ and $i \in {1,2,3, \dots n-1}$.$\text{Find the generalized form of n}$.

Lo único que pude hacer es mirar el problema y probar algunos ejemplos. No pude pensar algo general acerca de los números que obedecieron a la propiedad. Aquí son dos de los ejemplos, $n=17,16$:

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

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

Answer 1

Trabajando en un problema relacionado con la forma natural me llevó a este problema. Creo que algunos de los resultados que obtuve no podría ser de ayuda. Primero, considere el conjunto a $\{1, 2, \dots, n\}$. Podemos construir un grafo no dirigido más de este conjunto, tomando los elementos como nodos en el gráfico, de tal manera que $(i, j)$ es una arista en el grafo iff $i + j = k^2$ algunos $k$. Válido permutación es entonces un camino Hamiltoniano (no un ciclo!) a través de este gráfico. Vamos a llamar a este gráfico de $G(n)$ en el siguiente.

El límite Inferior de los Bordes

Deje $E(n)$ el número de aristas en el grafo $G(n)$. Voy a diseñar un límite inferior para $E(n)$.

Primer aviso de que la adición de $n+1$ para el conjunto de $\{1, 2, \dots, n\}$ presenta el potencial de los nuevos bordes de la gráfica: $(1, n+1), (2, n+1), \dots, (n, n+1)$. Aquellos que realmente se convierten en los bordes son los que se suman a los cuadrados perfectos, que es exactamente el número de cuadrados perfectos en el intervalo de $[n+2, 2n+1]$. Esto a su vez es igual a:

$$\lfloor \sqrt{2n+1} \rfloor - \lfloor \sqrt{n+2} \rfloor \geq (\sqrt{2(n+1)} - 1) - (\sqrt{n+1} + 1) = (\sqrt{2} - 1)\sqrt{n + 1} - 2$$

Por lo tanto un límite inferior para $E(n)$ es:

$$\sqrt{1} - 2 + \sqrt{2} - 2 + \dots + \sqrt{n} - 2 = \sum_{i=1}^n\sqrt{i} - 2n \geq \int_0^n\sqrt{x}\;dx - 2n = \frac23n^{\frac32} - 2n = n(\frac23\sqrt{n} - 2)$$

A partir de este entonces se puede calcular el límite inferior de la media de grado de un nodo como $\dfrac{E(n)}{n} = \frac23\sqrt{n} - 2$. Traducir al problema original, esto significa que los nodos en el conjunto $\{1, 2, \dots, n\}$ tienen un promedio de al menos $\frac23\sqrt{n} - 2$ válido vecinos con los cuales hacer una permutación.

Además, la distribución de los grados parece razonablemente equilibrada entre los nodos. Es decir, ningún nodo es "acaparando" todos los bordes de la misma. Esto añade más credibilidad a la posibilidad de una "adyacentes plazas" permutación. A ver por qué este es el caso, considere la posibilidad de un número $i$ en el conjunto de nodos de $\{1, 2, \dots, n\}$. Cada cuadrado en el intervalo de $[i+1, i+n]$ corresponde a un válido borde en $i$, a excepción de $2i$. Como en el anterior, el número de plazas en este intervalo de tiempo es por lo menos:

$$\lfloor \sqrt{i+n} \rfloor - \lfloor \sqrt{i+1}\rfloor - 1 \geq \sqrt{2n} - \sqrt{n} - 3 = (\sqrt{2} - 1)\sqrt{n} - 3$$

El $-1$ cuentas para la posible squre en $2i$. El paso de $i$ $n$puede ser justificado por el estudio de la función de raíz cuadrada y darse cuenta de que, desde su pendiente es monótonamente decreciente, las diferencias son más exageradas para valores más bajos.

Nota: Este razonamiento, de hecho, pueden ser utilizados en los problemas relacionados, para adyacentes sumas agregar cubos, hypercubes, quinto poderes y así sucesivamente. De hecho, mediante la integración de obtener un límite inferior como en el anterior, siempre podemos llegar a $E_k(n) \sim n^{\frac{k+1}{k}}$. Aquí utilizo $E_k(n)$ para denotar el número de aristas en el grafo cuyos nodos son $\{1, 2, 3, \dots, n\}$ y cuyas aristas $(i, j)$ son exactamente los pares de números tales que $i+j = a^k$ algunos $a$. Es decir, es el gráfico adyacente $k^{th}$ poderes. Es interesante notar que, por lo $k$, el mínimo número de aristas por nodo es ilimitado como $n$ crece. Esto parece sugerir que, para cada potencia de $k$, y lo suficientemente grande como $n$ (dependiendo $k$), siempre hay una solución, es decir, una permutación cuya adyacentes términos suma a $k^{th}$ poderes.

Un Caso Simple

Podemos hacer algunas imposibilidad pruebas para las pequeñas $n$ por obligando a más de $2$ nodos a los bordes (inicio/fin) de la permutación. Por ejemplo, tome $n=8$. El máximo de la suma de $2$ distintos números de menos de o igual a$8$$8 + 7 = 15 < 16 = 4^2$. Así que todas las plazas en un gráfico en el conjunto $\{1, 4, 9\}$. Ahora, mira el número de $8$. Sabemos que $8 + x > 1, 4$, por lo que nos vemos obligados a tener $8+x = 9$$x=1$. Por lo $8$ debe estar en el borde, junto a $1$. Del mismo modo, $7 + x > 1, 4$ $7$ debe ser próxima a $2$ sobre el otro borde. Pero también tenemos $6 + x > 1, 4$, lo $6$ debe estar en algún borde. Pero ambos bordes son tomadas, lo cual es una contradicción. Así que no hay Hamiltonianos camino a través de $G(8)$.

Answer 2

Hurgando en internet, este Stack Overflow respuesta enlaces a A090461 en OEIS, y el último parece indicar que este es un problema abierto.

A juzgar por la OEIS página (Stack Overflow de respuesta hace referencia a ella también), se cree que existe una permutación para todos los $n > 24$. También confirma que el 15, 16, 17, y 23 son las únicas $n < 25$ para que una permutación existe.