Conexión de un $n, n$ de los puntos de la cuadrícula

Question

Me topé con el problema de conectar los puntos en un $n, n$ cuadrícula con una cantidad mínima de líneas rectas sin levantar el lápiz.

Para $n=1, n=2$ es trivial. Para $n=3$ usted puede encontrar la solución con un poco de ensayo y error (esto se lo dejo al lector como es un divertido para hacer, se puede hacer con 4 líneas). He encontrado una posible solución para un $4,4$ cuadrícula y animado, utiliza las líneas 6 y es probablemente mejor (esperemos que ayudarán a comprender mejor el problema, el camino no tiene que ser cerrado como en la animación, extremos abiertos están permitidos!):

Ahora mi pregunta es, para la mayor $n$, hay una manera de obtener la cantidad de líneas mínimas de usar y hace un algoritmo que existen para encontrar una solución real? Creo que es bastante difícil de modelo de las "líneas rectas" con la teoría de grafos.

Editar: La lectura de Erics excelente respuesta que he encontrado la siguiente página web: http://www.mathpuzzle.com/dots.html que también le da un algoritmo para conectar los puntos en $2n-2$ pasos, las soluciones a $10,10$ y menciones:

Toshi Kato conjeturas: En $(2N+1)x(2N+1)$ cuadrícula, $N \geq 2$ Con $4N$ las líneas continuas, y no la elevación de su el lápiz del papel, puede ir a través de todos los puntos de una $(2N+1)x(2N+1)$ cuadrícula, terminando en el mismo lugar donde empezó. Pero debe visitar al menos uno punto dos veces en de la ruta.

En $(2N)x(2N)$ cuadrícula, $N \geq 2$ Con $4N-2$ las líneas continuas, y no la elevación de su el lápiz del papel, puede ir a través de todos los puntos de una $(2N)x(2N)$ cuadrícula, terminando en el mismo lugar donde empezó. Y puede visitar cada uno de los puntos de una sola vez.

Parece ser un problema abierto para mostrar que $2n-2$ es óptimo.

También he encontrado la siguiente página con una prueba de que en el $3,3$ cuadrícula no puede ser $2$ líneas paralelas: http://fahim-patel.blogspot.com/2011/01/proof.html yo creo que puede ser interesante para venir para arriba con una prueba de que $2n-2$ es óptimo (sin embargo, tal vez no hay ninguna prueba de ello, ya que sólo se vio soluciones para pequeñas $n$, para un mayor $n$ no podrían ser algunos de los acontecimientos que no conocen).

Answer 1

Pregunta interesante. En lo que sigue considerar el $n\times n$ cuadrado de la cuadrícula. Observe que el trivial solución obtenida siguiendo una plaza en espiral hacia el centro a partir de una esquina exterior de los rendimientos de una solución con $2n-1$ líneas.
Para ver por qué, observe que 2 reduce las líneas de la cuadrícula a un $(n-1)\times (n-1)$ cuadrícula, y puesto que el $1\times 1$ red requiere sólo 1 línea, la inducción de los rendimientos de $2n-1$ líneas.

Podemos hacer mejor? Basado en las publicaciones en el foro y mis propios intentos, creo que la respuesta es que el $2n-2$ líneas es óptimo. Mostrar que esto es posible es nuevo sencillo. Comience en una esquina, y en espiral hacia el centro hasta que sólo hay un $3\times 3$ cuadrícula restantes. El recuerdo de que por encima de 2 líneas en la espiral reducirá la red por una dimensión, por lo que por el momento no se han utilizado $2\cdot (n-3)=2n-6$ líneas. En la última línea, el final es por lo que estamos en una posición para ir a través de la diagonal de la $3\times 3 $ cuadrícula. Puesto que el $3\times 3$ cuadrícula tiene una solución con $4$ líneas de partida en diagonal desde una esquina, hemos encontrado una solución a la $n\times n$ cuadrícula utilizando sólo $2n-2$ líneas.

Ahora, la pregunta sigue siendo, es $2n-2$ óptimo? Cuanto más pienso en ello, más me lo creo, pero una prueba no salto a la mente. Voy a pensar más.

Edit: por supuesto, $n=1,2$ son excepciones, y requieren $2n-1$ líneas. El método que presenta puede ser modificado ligeramente para producir un trazado cerrado. Todo lo que debe ser cambiado es la forma en que el final de la $3\times 3$ cuadrícula es atravesado, y tal vez de mover la posición inicial de la primera línea a un lugar un poco fuera de la original $n\times n$ cuadrícula. En otras palabras, la conjetura de Toshi Kato es cierto.

Edit 2: Para una prueba de que $2n-2$ es óptimo, ver Joriki, la respuesta a esta pregunta No levantar el lápiz en la $n\times n$ cuadrícula.

Answer 2

Hay una cierta discusión de este problema aquí: http://www.tek-tips.com/viewthread.cfm?qid=1370890&page=2