Una ruta que pasa por todas las calles de la ciudad

Question

Usted está conduciendo un coche en una ciudad con $N$ larga, recta calles. No hay dos calles paralelas de modo que hay un cruce (cruce de caminos) para cada par de calles. Cada intersección tiene sólo dos calles perpendiculares. Ninguna calle estricta dirección norte-sur.

Sólo hay una conducción regla: al llegar a la intersección que tiene que hacer un giro para que la siguiente calle que lleva hacia el este (norte-oriental, oriente, sur-oriente, no importa). En un mapa, que significa que usted tiene que mantener la conducción a la derecha del mapa.

Demostrar que siempre es posible hacer un paseo por la ciudad que visitas todas las calles al menos una vez.

Aquí es una ciudad con $N$=6 calles. Algunos de los complicados rutas no visitar todas las calles (ruta azul no visitar la calle $a$. Pero el rojo de la ruta le llevará a través de todas las calles.

Traté de resolver el problema de la siguiente manera: Cada calle se compone de segmentos creados por la intersección de calles. Me han asignado un collor a cada calle. Obviamente, cada calle tiene 6 segmentos y he representado a cada segmento con un punto de color:

Mira el "largo" de las rutas, es decir, rutas a partir de algunos oeste-la mayoría del segmento de calle. Cada ruta representa una secuencia de segmentos (puntos de colores). Hay 6 rutas, una por cada calle de la ciudad:

...o, con las calles eliminado:

Fue capaz de concluir varias cosas desde el final de la gráfica:

• Hay $N$ diferentes colores (con exactamente $N$ vértices tener un color), $N$ poligonal cadenas, $N^2$ color vértices.
• Las cadenas no se intersecan (esto puede ser demostrado con bastante facilidad)
• En una sola cadena, hay al menos dos vértices entre dos vértices del mismo color.
• Básicamente, esto significa que en cualquier cadena va a encontrar 3 diferentes colores para cualquiera de los cuatro vértices consecutivos.

Basado en que yo todavía no podía probar que una cadena deben tener los vértices con todos los colores posibles. Lo que probablemente significa que mi enfoque es 100% malo. Pero el problema es que sigue siendo interesante.

Answer 1

Consideramos sólo las rutas que empiezan muy a la izquierda (más allá de cualquier punto de intersección) y el final muy a la derecha (más allá de cualquier punto de intersección). Las rutas que no funcionan porque no va lo suficientemente lejos en una dirección o la otra no son interesantes.

Cada ruta que falla, falla por una de dos razones:

1. Siempre queda estrictamente por debajo de una determinada calle, nunca tocarlo.
2. Siempre queda estrictamente por encima de una determinada calle, nunca tocarlo.

Estos dos motivos no pueden ser ambas verdaderas por la misma ruta. Cualquiera de las dos calles que se cruzan, por lo que la región que estrictamente por encima de la calle $X$ pero estrictamente por debajo de la calle $Y$ no ir todo el camino de la izquierda a la derecha: que no puede contener una ruta entera.

Así podemos clasificar las malas rutas en "muy bajo" de las rutas que no porque siempre permanecer por debajo de algunas calles, y "demasiado alta" rutas que no porque ellos siempre se mantienen por encima de algunas calles.

Ya has observado que hay $N$ rutas, que pueden ser ordenados verticalmente, y nunca de la cruz (a pesar de que se puede tocar): si la ruta $r$ comienza por encima de la ruta $s$, entonces siempre estará por encima de la ruta $s$. En particular, si una ruta es "demasiado bajo", lo es cada ruta debajo de ella; si una ruta es "demasiado alta", entonces también lo es cada ruta anterior.

Supongamos que la ruta $r$ está por encima de la ruta $s$, y la ruta de $r$ es "demasiado alta", ya que siempre se mantiene por encima de la calle $X$, mientras que la ruta $s$ es "muy bajo", ya que siempre se mantiene por debajo de la calle $Y$. Entonces el punto de intersección de $X$ e $Y$ debe estar por debajo de la ruta $r$ pero por encima de ruta $s$. Por lo tanto, hay otra ruta entre $r$ e $s$ pasar por el punto de intersección. (Alternativamente, si $X$ e $Y$ son de la misma calle, a continuación, la ruta que se inicia en esa calle debe ser de entre $r$ e $s$.) En otras palabras, un "demasiado alta" ruta es de nunca junto a una "muy bajo" de la ruta.

El más alto de la ruta no puede ser "demasiado baja" porque no hay nada por encima de él; si esto falla, se produce un error porque es "demasiado alta". Del mismo modo, el nivel más bajo de la ruta debe ser "demasiado baja" si se produce un error. Por lo tanto, va de arriba a abajo, debemos cambiar de "demasiado alto" a "muy bajo" en algún momento. Para ello, debe haber al menos una ruta en el medio que no es ni "demasiado alta" ni "demasiado bajo": que ruta debe visitar cada una de sus calles.

Answer 2

Misha la Respuesta es esencialmente correcta, pero sentí la necesidad de elaborar un poco y completar algunos detalles.

Con $n$ líneas $n$ rutas: una para cada carretera, a partir de la west-la mayoría de los punto de la carretera y en dirección este.

Ahora, si usted dibuja una línea vertical hacia el oeste de todas las intersecciones, entonces el orden en que esa línea se cruza con la calle (y, por supuesto, llegará a una intersección con todas las calles) el fin de las rutas de norte a sur. De hecho, estos puntos de intersección puede ser visto como el 'punto de partida' para cada ruta. Aviso de que si hacemos lo mismo para el este oa ll las intersecciones de las calles, obtendríamos lo que podría ser considerado como el " fin de puntos de las rutas, y que sería exactamente en el orden inverso, va de norte a sur.

Ahora, observe las siguientes afirmaciones son todas verdaderas:

I. Cada segmento de calle es atravesada por una ruta exactamente: si usted comienza en ese segmento de la calle, entonces sólo hay un camino para seguir esa ruta hacia el este, y sólo hay una manera de continuar hacia el oeste, y esto es por supuesto una de las rutas

II. Cada intersección se obtiene visitado por exactamente dos de las rutas: desde cualquier intersección hay dos segmentos de la calle que va al este, y ya por I. cada segmento de calle pertenece a exactamente una ruta, que significa exactamente dos rutas de ir a través de una intersección.

III. Dos caminos nunca se cruzan entre sí: si, lo que significaría que ambas rutas tendría que ir directamente a algunos de intersección, que es contra las reglas.

IV. Nunca va a ser un cruce entre dos periodos consecutivos de rutas (es decir, al sur de una ruta, y al norte de la otra): si hay, entonces, de considerar cualquiera de las rutas que va a través de la intersección: esta ruta tiene que cruzar uno de ellos volviendo al punto de partida, que de nuevo es imposible III

V. no puede haber dos periodos consecutivos de rutas y de dos diferentes calles de la $A$ e $B$ cuando una ruta es completamente norte de $A$, y el otro completamente al sur de $B$: (este es el argumento central de Misha en la Respuesta), si esto llegara a ocurrir, entonces la intersección de a$A$ e $B$ sería completamente entre los dos periodos consecutivos de rutas, que por vía IV es imposible.

OK, así que finalmente (otra vez, como en Misha de la respuesta), considerar las sucesivas rutas comenzando con la más septentrional. Claramente la más septentrional uno no puede ser completamente al sur de la calle, así que si hay algo mal, entonces, debe ser porque es completamente norte de la calle. Ahora, mientras la ruta bajo consideración es completamente al norte de la calle $A$, consideran que su sucesivos de la ruta. Esta calle $A$ en algún punto de ser incluido por algunos ruta que vamos hacia abajo de la lista de rutas, (ya que cada calle de la ciudad es atravesada por alguna ruta). Por otra parte, si la ruta actual es todavía completamente al norte de la calle algunos $A$, es imposible que su sucesor ruta para ir completamente al sur de algunos de los diferentes street $B$, para que vaya en contra de V, y por tanto, por el momento llegar a una ruta que incluye street $A$, no hemos ido completamente al sur de la calle $B$. Este proceso se puede seguir para cualquier otro de la calle que todavía estamos completamente hacia el norte, y de nuevo, es imposible siempre se termina por el sur de algunos otros de la calle. Por lo tanto, en algún momento todas las calles deben ser incluidos en alguna ruta.