Un problema sobre orientado a la cara en la Plaza de la cuadrícula

Question

Considere la posibilidad de una $n \times n$ cuadrado de la cuadrícula (finito) (un cuadrado se divide en pequeños cuadrados por líneas paralelas a sus lados). El límite de la plaza está orientado, (en sentido horario o en sentido antihorario) que es, una dirección es elegido en él y fija, de tal manera que si se mueve en esa dirección a lo largo de la frontera, los puntos internos de la plaza de permanecer siempre a su izquierda o a su derecha (dependiendo de la orientación). Para cada uno de los bordes internos de la subdivisión, una dirección que se especifica, de tal manera que para cada vértice interior, hay exactamente dos bordes llegando al vértice y dos bordes se va a alejar de ella (ver diagrama a continuación).

Entonces mi pregunta es que ocurre que hay al menos uno orientado a la cara en la subdivisión?

(Por ejemplo, en la figura, no es exactamente un ejemplo de la cara, es decir, en el extremo inferior de la esquina derecha).

Answer 1

Sí. De manera más general, en una $m\times n$ cuadrícula ( $m,n \in \mathbb{N}\setminus \{0\}$ ), donde los bordes están orientados a la satisfacción de estas condiciones siempre hay por lo menos un cuadrado cuyo límite está orientado como el límite de la red.

Supongamos que el gran límite está orientado positivamente (a la izquierda).

La afirmación se comprueba fácilmente si $n = 1$ (y es trivial para $m = n = 1$). Desde la parte superior de borde horizontal está orientado a la izquierda, y el borde inferior derecho, debe haber al menos un cuadrado cuyo borde superior está orientada a la izquierda y cuyo borde inferior está orientado a la derecha (ir de arriba a abajo hasta llegar a la primera plaza, cuyo borde inferior está orientado a la derecha).

Así que supongamos $n > 1$ y la mirada en el borde izquierdo de la plaza en la esquina superior derecha. Si el borde está orientada hacia abajo, hay al menos una plaza en la columna de la derecha cuyo límite está orientado positivamente. Si el cuadrado en la esquina no lo es, su borde inferior está orientado a la izquierda, por lo que la izquierda y el borde inferior de la plaza de los dos entran en la parte inferior izquierda del vértice del cuadrado, y por lo tanto los otros dos bordes adyacentes al vértice salir. En particular, el borde izquierdo de la plaza de abajo va hacia abajo. Luego de su borde inferior está orientado a la derecha, y tenemos nuestra orientado a la frontera, o es orientado a la izquierda y tenemos la misma configuración anterior, de modo que el borde izquierdo de la tercera plaza, desde la parte superior de la columna de la derecha también está orientado hacia abajo. Este se detiene en el último, cuando llegamos a la plaza en la esquina inferior derecha.

Si todos los bordes izquierdo de las casillas en la columna de la derecha están orientados hacia arriba, se puede colocar simplemente (ignorar) la columna de la derecha y en el $m \times (n-1)$ de los casos, donde la hipótesis de inducción garantiza una orientada a la plaza.

Así es mirar en el caso de que el extremo izquierdo de la parte superior derecha de la plaza está orientada hacia arriba, y hay al menos una plaza en la columna de la derecha, cuyo borde izquierdo está orientada hacia abajo. Mira en la parte más alta de dicha plaza, se $s_1$. A continuación, los dos bordes verticales adyacentes a su superior izquierda del vértice salir, y por lo tanto, el borde superior de $s_1$ está orientado a la izquierda. A continuación, esencialmente estamos en la situación que se discutió por primera vez. Si $s_1$'s de límite aún no está orientado, su borde inferior está orientado a la izquierda, y el borde izquierdo de la plaza de abajo también está orientado hacia abajo. Tan pronto como nos encontramos con una plaza de abajo $s_1$ cuyo borde inferior está orientado a la derecha, nos están haciendo, y que debe ocurrir, ya que el borde inferior de la parte inferior derecha de la plaza está orientada a la derecha.