23 votos

No levantar el lápiz en la parrilla de $n\times n$

¿Existe $n$, e $r<2n-2$, de tal manera que el $n\times n$ cuadrado de la cuadrícula puede ser conectado con una ininterrumpida camino de $r$ líneas rectas?

Nota: Esto, en esencia, ha sido ya preguntó - ver este MSE hilo. Estoy publicando esta pregunta porque yo quería que se centran explícitamente en uno de los sin respuesta partes.

Observe que $2n-1$ es la solución trivial. Este se obtiene por cualquiera de espiral hacia el centro, o en zig-zag hacia arriba y hacia abajo. En el otro MSE hilo, he publicado una respuesta que muestra $2n-2$ fue posible por $n\geq 3$. (esto se obtiene de disminuir a las $3\times 3$ de los casos) me sentí $2n-2$ debe ser óptima, pero yo no podía pensar en una prueba. (Además, no es necesariamente claro que por 100 millones de dólares por 100 mil millones de cuadrícula no se puede usar algún tipo de inteligencia para eliminar una sola línea)

Esto me viene molestando desde que la vi, y me gustaría saber si alguien tiene alguna idea.

Gracias,

Edit: Esto es con respecto a una pregunta/respuesta que he recibido: No sólo son de 45 grados líneas permitido, pero las líneas en cualquier dirección. Naturalmente 0,45,90 parece la mejor ya que los ángulos se cruzará con el de la mayoría de celosía puntos, y nos preguntamos: "¿alguna solución óptima consiste sólo de líneas en estos ángulos?". La respuesta es un definitivo no. Considere la siguiente solución a la $10\times 10$ red, que utiliza 18 líneas (por lo $2n-2$, es decir, actualmente la óptima). También hay esta la solución a la $8\times 8 $ cuadrícula con 14 líneas.

Curiosamente, esta solución a la $10\times 10 $ generaliza a dar otro $2n-2$ línea de solución a la $n\times n$ cuadrícula cuando se $n$ es incluso.

(He encontrado esta $8\times8$ $10\times 10$ solución en un enlace publicado por user3123 en la otra página de preguntas. Específicamente fue este enlace.)

28voto

JiminyCricket Puntos 143

Creo que esta es una prueba de que usted no puede hacer mejor que $2n-2$:

Deje $m$ el número de líneas horizontales y verticales en el camino. Luego, desde allí se $2n$ filas y columnas, hay $2n-m$ filas y columnas que no contienen una línea a lo largo de su longitud; decir, $k$ filas y $l$ columnas con $k+l=2n-m$. Imaginar los puntos de la cuadrícula donde estas filas y columnas se cruzan sacado de la red y dispuestos en un rectángulo de $k$ filas y $l$ columnas. Desde cada uno de los puntos en este rectángulo es tanto en una fila y de una columna que no contiene una línea a lo largo de su longitud, cada uno de estos puntos debe ser en alguna línea que no es ni horizontal ni vertical.

Si $k=0$, luego tenemos a $n$ líneas horizontales, y estos deben ser conectados al menos $n-1$ sin líneas horizontales para hacer una ininterrumpida trayectoria. Así, por $k=0$ debe ser $2n-1$ líneas, por lo que podemos descartar el caso.

Si $k=1$, luego tenemos a $n-1$ líneas horizontales, y tenemos que conectar cada una de las $n$ puntos de cuadrícula en el resto de la fila con una línea separada, así que de nuevo debemos tener al menos $2n-1$ líneas, por lo que podemos descartar el caso.

Por lo tanto $k\ge2$, y de la misma manera $l\ge2$. Por lo tanto podemos considerar que la frontera del rectángulo, es decir, los dos hileras exteriores y los dos ultraperiféricas columnas. Esta frontera se compone de $2k+2l-4=2(k+l-2)=2(2n-m-2)$ puntos de cuadrícula. Cada línea que no se ejecuta a lo largo de la longitud de una de estas filas o columnas puede golpear a más de dos de estos puntos. Eso significa que debe tener al menos $2n-m-2$ líneas, además de la $m$ líneas horizontales y verticales, para un total de $2n-2$.

P. S.: Usted puede verificar esto en la $8\times8$ $10\times10$ soluciones vinculadas a la pregunta: en cada caso, el "rectángulo", construido en la prueba es en realidad un rectángulo contiguo en la cuadrícula (con $k=6$, $l=8$ y $k=10$, $l=2$, respectivamente), y se puede ver que la ruta de acceso de forma óptima conecta dos puntos de ese rectángulo de la frontera con cada línea que no es horizontal o vertical.

5voto

Eric Naslund Puntos 50150

Desde que tengo para explicar Joriki la solución a todas las personas que he mencionado el problema, me decidí a proporcionar un tipo de solución de escribir en mis propias palabras. A pesar de que no hay nuevas ideas, no parece haber ninguna buena razón para no compartir lo que de todos modos:

Lema Vamos $a\geq 1$, $b\geq 1$. Dado un $a\times b$ cuadrícula rectangular, sin el uso de líneas horizontales o verticales requiere al menos de $a+b-2$ líneas para cubrir todos los puntos. (De aquí el camino no necesita estar conectado)

prueba: Considerar el exterior de la red. Si $a\geq 2$$b\geq 2$, entonces cada línea diagonal que se puede cubrir en más de dos puntos, pero no se $2a+2b-4$ puntos que deben ser cubiertos. Si $b=1$, entonces cada línea diagonal que se cubre en más de 1 punto, y por lo tanto necesitamos $a=a+b-1>a+b-2$ líneas. Del mismo modo, si $a=1$.

Dada una solución a la $n\times n$ cuadrícula, vamos a $h$ el número de líneas horizontales, y $v$ el número de líneas verticales utilizados. Si $h=n$, debemos tener al menos $2n-1$ líneas ya se tardará al menos $n-1$ líneas para unir todas estas partes horizontales. Asimismo, para $v=n$.

Ahora, vamos a $v<n$, $h<n$ y eliminar todas las filas y columnas, donde una línea horizontal o vertical aparece. A continuación, tenemos una $n-h\times n-v$ cuadrícula de la izquierda, que por el lema requiere al menos $(n-h)+(n-v)-2=2n-2-h-v$ líneas para cubrir. Puesto que ya hemos usado $h+v$ líneas de la cuadrícula completa requiere de $(h+v)+(2n-2-h-v)=2n-2$ líneas, y la prueba está completa.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X