¿Tienen todas las fichas de dominó al menos dos fichas "expuestas"?

Question

En un azulejos en forma de dominó un dominó es expuesta si tiene un borde largo que no es vecino de otra ficha de dominó. Una ficha de dominó que comparte una arista con una arista larga de otra ficha de dominó cubre el borde (o el dominó, si entendemos a qué borde nos referimos) y evita que se exponga allí.

En esta imagen, las fichas expuestas están en rojo. El borde superior de la ficha de dominó azul está cubierto por la ficha de dominó roja situada encima.

Un mosaico con sólo fichas horizontales de un $2\times 4$ tiene cuatro fichas expuestas (las cuatro están expuestas), mientras que un mosaico del mismo rectángulo con sólo fichas verticales tiene dos fichas expuestas.

¿Tiene cualquier mosaico de dominó finito (con más de un dominó) en el plano euclidiano al menos dos dominós expuestos?

Intentar construir un contraejemplo hace que parezca "obvio", y después de intentar algunas aproximaciones he elaborado una prueba de esta afirmación, pero es muy torpe y no me extrañaría que pasara por alto casos y tuviera errores. (Algunos intentos anteriores fracasaron debido a todo tipo de casos no considerados).

Así que me pregunto si hay una prueba más clara de esta afirmación.

Aquí está mi intento. (Si se trata de un hecho obvio con una prueba sencilla, puede omitir esto a continuación y simplemente indicarme la dirección correcta).

Boceto

• Defino un "borde superior" para una figura de poliomino. En la figura anterior, el borde superior se muestra en verde.
• Demuestro que una figura debe tener un borde superior. (Esta es la parte realmente fea).
• Demuestro que un dominó expuesto debe existir examinando dos casos:
  • No hay fichas de dominó verticales a lo largo del borde superior
  • Hay una ficha de dominó vertical, y la más a la izquierda está expuesta, o está cubierta, lo que significa que a la izquierda de ella hay una ficha de dominó horizontal expuesta en el borde.

Una definición y prueba análoga para el borde inferior (amarillo en la imagen) muestra que hay otra ficha de dominó expuesta, y en conjunto esto demuestra que debe haber al menos dos.

Otras cosas que he probado

• Un método de teoría de gráficos. Aquí la dificultad fue enmarcar el problema -tal vez porque no tengo muchos conocimientos en este campo-, decidir cuáles deben ser los vértices y las aristas, e imponer todas las restricciones, etc.
• Inducción. Empezar con una ficha de dominó. Tiene dos aristas. Si se añade una ficha de dominó en cualquier lugar, sólo se puede cubrir una arista y exponer otra. Esto resulta ser falso (tenemos que hacer algo más complicado para mostrar que las figuras en las que podemos matar aristas largas sin exponer más aristas sólo pueden surgir si añadimos más aristas que una a la vez, o no cubrimos aristas en cada paso. Incluso cuando se sortea esta dificultad, es difícil demostrar que no podemos hacer un bucle para acercar dos aristas lo suficiente como para poder cubrirlas con una sola ficha de dominó.
• Contradicción. Asumo que existe un mosaico sin aristas expuestas (en esta versión, sólo intento demostrar que debe existir al menos una ficha de dominó expuesta). A continuación, intento demostrar que podemos quitar una ficha superior y transformar el mosaico, si es necesario, mediante "volteos" (cambiar la orientación de dos fichas de dominó en un $2\times 2$ cuadrado) para conservar las propiedades del dominó no expuesto. Finalmente, queda una figura mínima, para la cual (pensé), podemos demostrar que debe tener dos aristas. La prueba falla porque hay demasiados casos en los que no he podido averiguar cómo mantener la propiedad de no exposición.

También hubo otros intentos más extraños (como tratar de demostrar mediante un argumento de color de tablero de ajedrez que si existe esa figura sin fichas expuestas no puede ser tilebale).

Detalle

Partiendo de un vértice, podemos describir un tramo de frontera que va en el sentido de las agujas del reloj utilizando letras $N$ , $E$ , $S$ , $W$ que corresponde a las direcciones en las que tenemos que mover una unidad para llegar al siguiente punto de la red (que puede corresponder a un vértice del dominó o al centro de una arista larga).

A borde superior es entonces la palabra más larga (en el sentido de las agujas del reloj), que contiene cualquier arista superior del dominó, que comienza con $N$ , sólo contiene $N$ , $E$ , $S$ y termina con $E$ . En la imagen, es $NENEESE$ .

Para demostrar que una figura tiene un borde superior, la construimos como sigue:

1. Elige una ficha de dominó superior y toma el vértice superior derecho, y llámalo $A$ . A partir de aquí, atravesar la frontera en sentido contrario a las agujas del reloj, justo antes de llegar a la primera $W$ carta (nótese que el $W$ es en el sentido de las agujas del reloj, por lo que desde la dirección contraria a las agujas del reloj es en realidad este) y llamamos a este vértice $B$ . A partir de $B$ volviendo en el sentido de las agujas del reloj hacia $A$ La secuencia debe comenzar con N, para:
   • No puede ser $W$ (nos detuvimos justo antes de la primera),
   • No puede ser $E$ ( $E$ no puede proceder $W$ )
   • No puede ser $S$ (si lo fuera, no podríamos volver a $A$ sin viajar $W$ (Esta es una parte dudosa, en mi opinión, no parece del todo convincente).
2. Ahora dejemos que todo esto (de $B$ a $A$ ) sea el inicio del borde superior. Hasta ahora, cumple todos los requisitos de la definición (comienza con $N$ , sólo contiene $N$ , $S$ , $E$ ) excepto que podemos hacerlo más largo (sólo en el sentido de las agujas del reloj desde $A$ , ya que en sentido contrario a las agujas del reloj desde $B$ tenemos un $W$ ).
3. Para hacerlo más largo, vamos en el sentido de las agujas del reloj hasta la primera $W$ y luego retroceder hasta el último $E$ . Ahora nosotros: empezamos en $N$ , finaliza en $E$ y sólo tienen $N$ , $S$ y $E$ en el medio - tenemos el borde superior.

Para demostrar que el borde superior tiene una ficha expuesta, consideramos dos casos:

Caso 1. el borde superior está hecho sólo de fichas de dominó colocadas horizontalmente. En este caso, hay que encontrar la más alta. Debe estar expuesta, ya que el borde superior no puede ser cubierto por ninguna ficha de dominó (ya que está en la parte superior).

Caso 2. el borde superior tiene una ficha de dominó colocada verticalmente a lo largo del borde. Encuentra la más cercana (a lo largo del borde) a $B$ . Esta ficha vertical está expuesta, o sólo tiene fichas horizontales colocadas entre ella y $B$ a lo largo de la frontera. En este último caso, encuentre la más alta de estas fichas horizontales. No puede estar cubierta en su parte superior por una ficha vertical (ya que si lo está, esta ficha no puede ser la más cercana a $B$ a lo largo del borde, ya que esa ficha está cubierta y dos fichas de diferente orientación no pueden cubrirse mutuamente), y no puede ser cubierta por una ficha horizontal (ya que es la más alta), por lo que está expuesta.

Entre estos casos entonces, debe haber una ficha de dominó expuesta en el borde superior.

Procedemos de forma similar para definir un borde inferior (a partir de $S$ y terminando con $W$ y que sólo contenga $S$ , $N$ y $W$ , $SWWWWNWNW$ en la imagen), y demostrar que debe haber una ficha de dominó expuesta en el borde inferior.

Observa que los bordes superior e inferior no se superponen. Dado que una figura debe tener un borde superior e inferior, y cada uno contiene una ficha de dominó expuesta, y no se superponen, el mosaico debe tener al menos dos fichas de dominó expuestas.

---

Answer 1

tl;dr . Lo estás pensando demasiado.

1. Coge cualquier baldosa. Si es horizontal, mira su lado superior (largo). Si no, mira el lado derecho (largo).
2. Introduzca las coordenadas: $(x,y)=(0,0)$ en el centro de ese lado.
3. Si ese lado está libre, hemos terminado. Si no lo está, debe haber otra baldosa que lo bloquee (quizá parcialmente). Cambia a esa baldosa (o a la que esté más a la derecha/arriba de las dos, si hay dos).
4. Si es horizontal, mira su parte superior. Si no, mira el lado derecho.
5. Compruebe el valor de $x+y$ en el centro de ese lado. Asegúrese de que en aumenta cuando pasamos de una baldosa horizontal a una vertical o viceversa, o (en el peor de los casos) se mantiene constante cuando pasamos a una baldosa de la misma orientación.
6. Vaya al paso 3 y continúe. Debe terminar en algún lugar, ya que sólo hay un número determinado de baldosas y nunca se repiten. (No puede haber un ciclo de baldosas con diferente orientación, porque $x+y$ aumenta cuando cambiamos de orientación, y nunca disminuye. Tampoco puede haber un ciclo hecho sólo de baldosas horizontales, pues en ese caso $y$ aumenta constantemente en cada paso).

Para localizar el segundo lado largo expuesto, vuelva a la baldosa inicial y repita todo en la dirección opuesta.