Suponga que tiene un cuadrícula, y un conjunto W de fichas blancas y un conjunto B de fichas negras que se colocan al azar en esta cuadrícula.
Creo que al menos uno de los conjuntos W, B debe incluir un camino conectado de mosaicos desde un lado de la cuadrícula hasta el lado opuesto de la cuadrícula.
Lo que quiero decir con ruta conectada: los mosaicos tienen el mismo color y son vecinos por pares entre sí (cada par de ellos comparte un borde o un vértice).
Creo que tal camino conectado, que conecta un lado de la cuadrícula con el lado opuesto, debe incluirse en B o W, independientemente de la distribución de los mosaicos.
Sospecho que es suficiente probar esto para el caso en que W y B tienen el mismo tamaño . También sospecho que uno podría comenzar con un patrón de estilo de tablero de ajedrez y desde allí cubrir todas las demás distribuciones de fichas en blanco y negro. Finalmente, sospecho que el Principio de Pigeon Hole podría probarlo de una sola vez; pero no he encontrado el punto de entrada correcto a esta ruta. ¿Alguien sabe una prueba simple corta?
Sí, siempre hay ese camino. Piense en esto como un laberinto: puede caminar sobre los mosaicos negros y los mosaicos blancos son paredes. Comience, digamos, en la esquina inferior derecha, justo debajo del laberinto, mirando hacia el laberinto. Entra en el laberinto si puedes, o gira a la izquierda. Ahora pon tu mano en la pared a tu derecha. (Si es necesario, agregue una columna de mosaicos blancos a la derecha del laberinto). Empiece a caminar, manteniendo siempre la mano en la pared. Pasarás de abajo hacia arriba, o tu mano trazará una pared contigua de derecha a izquierda.
Esto surgió recientemente en Posibilidad de que las hormigas no puedan cruzar un puente en forma de cuadrícula .
Un enfoque diferente.
Supongamos por una contradicción que no existe tal camino. Ahora considere algún componente conectado de ancho máximo (es decir, se maximiza la diferencia de la distancia del mosaico más a la derecha y el mosaico más a la izquierda). Wlog es un componente conectado blanco. Tenga en cuenta que el componente conectado debe estar rodeado solo por mosaicos negros y mosaicos de pared de rejilla. Pero no puede darse el caso de que esté rodeado por algún mosaico de grid-wall en la parte superior Y en la parte inferior porque de lo contrario tendríamos un camino conectado. El mismo argumento se aplica para izquierda/derecha. Por lo tanto, podemos suponer wlog que nuestro componente conectado está rodeado de mosaicos negros (sin pared) en la parte superior y a la derecha. Pero el componente conectado de estos mosaicos negros tiene un ancho mayor que nuestro componente conectado. una contradicción
pez luna
joriki
pez luna
noel
noel