Cómo demostrar el número de soluciones del puzzle de los nueve puntos

Question

El objetivo de la Puzzle de nueve puntos es dibujar un camino que conecte 9 puntos dispuestos en un $3\times 3$ cuadrícula utilizando 4 líneas rectas continuas, sin levantar nunca el bolígrafo/lápiz de la hoja de papel. A continuación se muestra una solución (alerta de spoiler):

En la página de Wikipedia enlazada anteriormente, la solución está etiquetada como "Una de las muchas soluciones del rompecabezas..." Sin embargo, esta página afirma que es la única solución al rompecabezas. En mi somera exploración del rompecabezas, todas las soluciones que he encontrado son una rotación de la solución anterior o la misma solución con un punto de partida diferente. Por ejemplo, la siguiente solución:

es sólo un $90\,^{\circ}$ rotación de la primera.

Alternativamente, si numeramos los puntos así:

la primera solución puede generarse utilizando las trayectorias $$9\rightarrow 5\rightarrow 1\rightarrow 2\rightarrow 3\rightarrow 6\rightarrow 8\rightarrow 7\rightarrow 4\rightarrow 1 \tag{1}\label{a} $$ y $$9\rightarrow 5\rightarrow 1\rightarrow 4\rightarrow 7\rightarrow 8\rightarrow 6\rightarrow 3\rightarrow 2\rightarrow 1 \tag{2}\label{b} $$ que son sólo reflexiones sobre $y=-x$ (si el punto 1 es el origen) entre sí.

Otro camino (y su reflejo) que genera la primera solución es: $$1\rightarrow 2\rightarrow 3\rightarrow 6\rightarrow 8\rightarrow 7\rightarrow 4\rightarrow 1\rightarrow 5\rightarrow 9 \tag{3}\label{c}$$

[Tenga en cuenta que la ruta $\eqref{c}$ es el camino $\eqref{a}$ con los dos primeros elementos invertidos y trasladados al final del camino]

Mi pensamiento inicial es ese, si la primera solución es efectivamente la solución única, entonces el artículo de la Wikipedia puede estar contando todas las rotaciones, reflexiones y caminos alternativos como soluciones diferentes al rompecabezas porque no se me ocurre otra solución.

Pregunta:

Tratar las soluciones que son rotaciones o reflexiones entre sí o las soluciones que generan la misma "imagen" a pesar de su trayectoria exacta como soluciones equivalentes. ¿Cuántas soluciones hay y cómo se puede demostrar (aparte de la fuerza bruta) que el rompecabezas sólo tiene $K$ ¿solución(es)?

Esta cuestión puede requerir una definición más rigurosa de "misma imagen", pero no se me ocurre una forma mejor de describirla.

Answer 1

Olvida para empezar que tenemos que encontrar un camino pero simplemente trata de cubrir el $9$ puntos por cuatro líneas rectas infinitas .

Llamar a una línea que cubra $n$ señala un $n$ -línea. Dado que cuatro líneas que cubren sólo $2$ puntos que cada uno nunca puede cubrir $9$ puntos una solución tiene al menos una $3$ -línea en ella. Al identificar rotaciones y reflexiones tenemos exactamente tres tipos distintos de $3$ -líneas:

No hay paralelo $3$ -líneas

No es posible tener una solución que implique un $3$ -líneas. Por ejemplo, si tenemos la siguiente situación:

Cuando los dos azules $3$ -se han colocado las líneas indicadas anteriormente tenemos que cubrir los tres puntos restantes con dos líneas. Por tanto, al menos una línea debe cubrir más de un punto, lo que implica que hay que añadir la línea gris discontinua. Pero tres líneas paralelas son claramente imposibles, ya que se necesita dos movimientos lineales adicionales para visitar y viajar a lo largo de los tres, pero sólo tenemos un ¡línea de la izquierda!

Descartando el tipo 3

Con lo anterior podemos descartar tipo 3 ser parte de cualquier solución: No podemos tener ninguna línea paralela a la inicial $3$ -línea por el argumento anterior. Esto significa en realidad que cada una de las tres líneas restantes tiene que cubrir exactamente $2$ de los restantes $6$ puntos cada uno. Además sólo podemos tener una línea ortogonal a la $3$ -de otra manera tendríamos de nuevo una línea paralela $3$ -líneas (en la dirección ortogonal).

Así que tenemos que tener dos líneas que pasen por $2$ de los restantes $6$ puntos cada uno que no son paralelos ni ortogonales a la $3$ -línea de tipo 3 . Si se tienen en cuenta las simetrías, se obtienen esencialmente dos configuraciones a considerar. La primera es:

que claramente no tiene solución ya que las líneas sólo intersección en un punto, por lo que se necesita mucho más que cuatro movimientos lineales para viajar, ya que tendría que volver a esta intersección una y otra vez en cualquier camino que atraviese partes de todas estas líneas. La otra configuración a considerar es:

Una forma de ver por qué lo anterior no tiene solución es que algunas de las líneas sólo se intersecan de forma que algunos de sus puntos están a ambos lados del punto de intersección. Esto hace imposible pasar por todos los puntos de cualquiera de ellas sin visitar esa línea dos veces o invertir la dirección en algún punto.

Descartar la exclusividad del tipo 1 o 2

Si partimos de tipo 1 y no permiten tipo 2 y ya saben que tipo 3 debe descartarse y que ninguna línea paralela a la inicial $3$ -se permite, vemos que esto significa que una línea que pasa por el punto central de la $9$ El patrón de puntos no puede pasar por ningún otro punto del patrón, ya que eso llevaría a una de las situaciones que acabamos de mencionar. Pero con una línea que sólo pasa por el centro las dos líneas restantes deben cubrir $5$ puntos, por lo que una de las líneas debe cubrir el $3$ puntos que son paralelos a la inicial $3$ -línea que de nuevo lleva a un Paralelo $3$ -líneas contradicción.

Si partimos de tipo 2 y no permiten los otros dos tipos, sólo hay que tener en cuenta una configuración que no está cubierta:

que es otro montaje con tres líneas paralelas. Por los argumentos anteriores, tres líneas paralelas distintas nunca pueden formar parte de ninguna solución.

La solución única (tipo 1 + tipo 2)

Por inclusión-exclusión cualquier solución debe implicar tipo 1 y tipo 2 al mismo tiempo. Así que la situación se ve así para empezar:

y como ya sabemos que no podemos añadir una línea paralela a la $3$ -línea de tipo 1 sólo hay dos maneras de completar la configuración anterior. Una forma es la siguiente:

y vemos cómo el $3$ -línea de tipo 1 es la única línea que conecta con las otras tres líneas a un lado de sus puntos. Las otras tres líneas se dividen en partes que tienen puntos a cada lado. Por lo tanto, las otras tres líneas deben estar conectadas a la $3$ -línea de tipo 1 en una solución determinada. Esto es imposible, ya que cada línea sólo puede conectarse a otras dos líneas en un camino que no recorre ninguna línea dos veces.

Así que finalmente esto nos deja con la conocida solución como esencialmente la única posibilidad cuando se consideran rotaciones y reflexiones.

Answer 2

Como siempre, la solución depende enteramente de sus supuestos. De hecho, ese es el propósito declarado de este ejercicio, examinar tus supuestos. Y, sin embargo, la "solución" estándar sólo araña la superficie del examen de las soluciones. Por ejemplo... Asumimos que el papel es perfectamente plano. Suponemos que las líneas deben pasar por el centro de cada punto en lugar de tocar el borde de un punto. Suponemos que la línea no tiene grosor. Suponemos que el papel no se puede doblar. Si se descarta alguna de estas suposiciones, aparecen más soluciones. Por ejemplo, si se descarta la suposición de que la línea debe pasar por el centro de cada punto, hay una solución bastante simple de tres líneas. Las tres líneas son casi, pero no del todo, paralelas entre sí. Dos de ellas se inclinan muy ligeramente hacia abajo y una de ellas se inclina muy ligeramente hacia arriba. Extiende las líneas muy lejos de la cuadrícula y se encuentran. La distancia a la que hay que extenderlas depende del grosor de los puntos y de la distancia entre ellos.

Incluso si se restringen las respuestas al mundo de las matemáticas, donde los puntos son infinitamente pequeños y las líneas son infinitamente finas, sigue habiendo una solución de tres líneas si se utiliza un sistema de coordenadas diferente. Imagina una esfera posada sobre un plano infinito. Dibuja las coordenadas x-y en el plano, como siempre. Ahora imagina un telescopio montado en la parte superior de la esfera (el "polo norte", podríamos decir). Cada punto del plano x-y puede ser asignado a un punto específico de la esfera apuntando con el telescopio imaginario desde la cima de la esfera hacia ese punto xy y viendo dónde la línea de visión se cruza con la esfera. Ahora definimos una "línea recta" en la esfera como lo que se proyecta como una línea recta en el plano x-y. Localiza la cuadrícula de 3x3 en el plano x-y y proyéctala sobre la esfera. Dibuja tres líneas horizontales (que sean paralelas en el plano x-y) que cubran toda la cuadrícula. Proyecta estas líneas sobre la esfera. Observa que las líneas en el plano x-y que se extienden hasta el infinito son segmentos de línea en la esfera, todos los cuales se encuentran en el polo norte. Por lo tanto, puedes dibujar la cuadrícula de nueve puntos en la esfera, y trazar SÓLO TRES segmentos de línea a través de esos nueve puntos. Es fácil. Pones tu lápiz imaginario en el punto 1, trazas a través del punto 2 y el punto 3, todo el camino hasta el polo norte, luego comienzas tu segundo segmento en el ángulo perfecto para que golpee el punto 6, el punto 5 y el punto 4, y vuelves alrededor del polo norte de nuevo, donde comienzas tu tercer segmento de línea que golpea el punto 7, el punto 8 y el punto 9.