El camino más largo en una cuadrícula

Question

¿Cuál es el camino más largo en un cuadrado de la cuadrícula de una esquina a la esquina opuesta en diagonal?

En los bordes de la cuadrícula sólo puede ser atravesado una vez, pero los puntos de cuadrícula puede ser utilizado varias veces (en un cuadrado de la cuadrícula que significa máximo de dos veces).

Después de tocar el violín con este tiempo, me parece que las siguientes rutas de acceso son las más largas:

En un $2 \times 2$ cuadrícula, el camino más largo es $8$.

En un $3 \times 3$ cuadrícula, el camino más largo es $18$.

En un $4 \times 4$ cuadrícula, el camino más largo es $32$.

En un $5 \times 5$ cuadrícula, el camino más largo es $50$.

En general, la regla parece ser que el camino más largo para un $n \times n$ cuadrícula es $2n^2$.

¿Alguien puede confirmar esto? He buscado una prueba de ello, pero no era capaz de encontrarlo.

Answer 1

Hay $2n(n+1)$ potencial de los bordes de la cuadrícula, pero algunos de ellos necesitan ser dejado fuera porque los puntos de la cuadrícula en el límite sólo tienen $3$ potencial de los bordes de la reunión, y sólo dos de ellos pueden estar en su camino.

Además, una de las aristas incidentes al inicio y al final de nodo debe ser dejado fuera.

Si contamos el número de la izquierda-cabo de media bordes conseguimos al menos $$ 4(n-1) + 2 = 4n-2 $$ así al menos lo $2n-1$ de la $2n(n+1)$ bordes debe de faltar. Así que en la mayoría de los que hay $$ 2n(n+1)-(2n-1) = 2n^2 +1 $$ en los bordes de la ruta.

Sin embargo, la longitud de la ruta de acceso debe ser aún: el Color de los puntos de la cuadrícula alternativamente en blanco y negro en un patrón de tablero de ajedrez. Dos esquinas opuestas del mismo color, pero cada movimiento que cambia el color, por lo que debe haber un número par de movimientos.

Esto muestra que la longitud de la ruta es en la mayoría de las $2n^2$.

Por otro lado, debe quedar claro que el patrón ha encontrado logra este número para mayor $n$, así que es el máximo real.