¿Dadas $15$ objetos colocados alrededor de un círculo, es posible permutar su orden tal que la distancia entre cualquier dos elementos es diferente en la segunda permutación de eso en su estado original?
Respuestas
¿Demasiados anuncios?
MJD
Puntos
37705
OEIS señala que esto está estrechamente relacionado con el problema de si existe una solución para el toroidal $N$ queens problema, que es el problema de la organización de $N$ ajedrez queens en un $N\times N$ tablero de ajedrez de manera que ninguno de los ataques de otro, donde los pares opuestos de los bordes de la junta directiva son identificados. Se refiere a La Cíclico Completar las Asignaciones de Problemas de Recuento, Hsiang, Shieh, y Chen, 2002. Teorema 2 en la página 6 de este documento declara: $$TQ(n) = 0 \text{ if and only if } 2 | n \text{ or } 3 | n.$$
$TQ(n)$ es el número de soluciones para el toroidal $N$-queens problema, y es fácilmente visible a ser igual a $n\cdot A(n)$ donde $A(n)$ es el número de soluciones para el círculo arreglando el problema que estamos resolviendo. En particular, $TQ(15) = 0$, lo $A(15) = 0$.
Por desgracia, el papel no dar una prueba. Sin embargo, como Joriki notas en los comentarios, el teorema es debido a Pólya, probablemente en Über die 'doppelt-periodischen' Lösungen des $n$-Damen-Problemas, Mathematische Unterhaltungen und Spiele., (1918), pp 364-374; según la Wikipedia, esta aparece en George Pólya: collected papers , Vol. IV, G-C. Rota, ed., MIT Press, Cambridge, Londres, 1984, pp 237-247. Web de la búsqueda para "toroidal $n$-queens", pueden producir algo más inmediatamente útil.
Mathworld cites Vardi, I. "La $n$-Queens Problemas." Ch. 6 Computacional Recreaciones en Mathematica. Redwood City, CA: Addison-Wesley, pp 107-125, 1991.
DiGi
Puntos
1925
Esta lesión.matemáticas post dice que la literatura contiene varias pruebas independientes de el resultado de que el toroidal $n$-queens problema tiene una solución iff $\gcd(n,6)=1$ y da seis referencias. Tengo acceso a uno de ellos, Torleiv Kløve, El modular $n$-queens problema, en Matemáticas Discretas, 19 (1977), 289-91. La prueba no es lo suficientemente corto como para ser digno de escribir aquí.
Queremos una función $f:\Bbb Z/n\Bbb Z\to\Bbb Z/n\Bbb Z$ tal que $f$, $f+\mathrm{id}_{\Bbb Z/n\Bbb Z}$, y $f-\mathrm{id}_{\Bbb Z/n\Bbb Z}$ son todas las inyecciones. El teorema es que ese $f$ existe iff $\gcd(n,6)=1$.
Prueba. Supongamos que $f$ es una función de este tipo, y vamos a
$$S=\sum_{k\in\Bbb Z/n\Bbb Z}k^2\quad\text{and}\quad T=\sum_{k\in\Bbb Z/n\Bbb Z}kf(k)\;.$$
A continuación,$\displaystyle\sum_{k\in\Bbb Z/n\Bbb Z}f(k)^2=S$, ya que el $f$ es inyectiva. Desde $f+\mathrm{id}_{\Bbb Z/n\Bbb Z}$ $f-\mathrm{id}_{\Bbb Z/n\Bbb Z}$ son también inyectiva,
$$S=\sum_{k\in\Bbb Z/n\Bbb Z}\big(f(k)\pm k\big)^2=\sum_{k\in\Bbb Z/n\Bbb Z}f(k)^2\pm 2\sum_{k\in\Bbb Z/n\Bbb Z}kf(k)+\sum_{k\in\Bbb Z/n\Bbb Z}k^2=2S\pm 2T\;,$$
$2S=4S$, e $2S=0$$\Bbb Z/n\Bbb Z$. En $\Bbb Z$, por lo tanto, tenemos
$$2\sum_{k=0}^{n-1}k^2=\frac{n(n-1)(2n-1)}3\equiv 0\pmod n$$
y, por tanto,$\gcd(n,3)=1$.
Ahora se apela a N. J. Fine solución de problema E 1699 (Amer. De matemáticas. Mensual 72 (1965), 552-3). Especializados en el contexto actual, el argumento (que puede haber dado Kløve la idea de que su prueba) es que
$$\sum_{k\in\Bbb Z/n\Bbb Z}\big(f(k)+k\big)=2\sum_{k\in\Bbb Z/n\Bbb Z}k$$
en $\Bbb Z/n\Bbb Z$, pero si $n$ es incluso, a continuación, $$\sum_{k=0}^{n-1}k=\frac{n(n-1)}2\equiv-\frac{n}2\equiv\frac{n}2\pmod n\;,$$
así, en $\Bbb Z/n\Bbb Z$ hemos $$\sum_{k\in\Bbb Z/n\Bbb Z}\big(f(k)+k\big)=2\cdot\frac{n}2=0\ne\sum_{k\in\Bbb Z/n\Bbb Z}k\;,$$ and $f+\mathrm{id}_{\Bbb Z/n\Bbb Z}$ cannot be injective. Thus, $n$ must be odd, and $\gcd(n,6)=1$.
Por el contrario, si $\gcd(n,6)=1$, $f(k)=2k$ es una solución. $\dashv$
