Dada una $5 \times 5$ junta de $25$ células. ¿Es posible colorear $24$ de ellos en uno de tres colores de tal manera, que las tres formas resultantes de los colores particulares son congruentes entre sí?
Respuestas
¿Demasiados anuncios?
Misha
Puntos
1723
Actualización: Corregido un error no crítico señalado por NickG en los comentarios, que me impedía encontrar todas las soluciones posibles que no cubrieran todas las celdas menos una.
Esto no es, como, una solución súper satisfactoria ni nada...
Pero hice una búsqueda por fuerza bruta en el ordenador y no encontré ninguna partición cercana del $5\times 5$ tablero en tres congruentes $8$ -figuras celulares, conectadas o no.
En la búsqueda se encontraron cinco conectado $7$ -figuras de celdas cuyas copias congruentes se pueden empaquetar en un $5\times 5$ tablero (a veces en más de un sentido). Se muestran a continuación:
Mi método de fuerza bruta consistió en hacer una lista de todas las transformaciones que pueden tomar algunas celdas del $5\times 5$ a otras células. Así que mi primera lista de candidatos eran todos los pares de estas transformaciones.
A cada par de transformaciones $(\tau_1, \tau_2)$ asocié una lista de $25$ triples $(P, \tau_1(P), \tau_2(P))$ donde $P$ abarca todas las casillas del tablero. Como filtro preliminar, descarté todas las triplas cuyos tres elementos no eran distintos por pares o no cabían todos en el tablero; después descarté todos los pares $(\tau_1, \tau_2)$ cuyos triples restantes no cubrían al menos $24$ células del tablero. (Actualización: para encontrar todos $7$ -cifras de células, tenemos que reducir este número a $21$ .)
Para cada uno de los restantes $939$ pares, definí un grafo en los triples, donde dos triples eran adyacentes si compartían uno o más puntos, y luego encontré un conjunto máximo independiente en el grafo. Dado cualquiera de estos conjuntos independientes, podemos obtener un paquete de tres figuras congruentes tomando el primer elemento de cada triple como una figura, y aplicando $\tau_1$ y $\tau_2$ para obtener las otras dos cifras.
Ninguno de estos gráficos tenía un conjunto independiente de tamaño $8$ pero algunos tenían un conjunto independiente de tamaño $7$ . (Había muchas soluciones, así que filtré por conectividad y sólo encontré una restante, hasta la simetría).
Si alguien ve cosas que se me hayan pasado con la búsqueda, o puede encontrar una conexión diferente $7$ -de células que se pueden empaquetar en un $5\times 5$ (lo que también demostraría que mi programa puede pasar cosas por alto), házmelo saber.
Actualización: Generalizando al siguiente caso no trivial, mi ordenador piensa que el $7\times 7$ tablero no admite un empaquetamiento de tres congruentes $16$ -figuras celulares. Hay múltiples empaquetamientos de tres congruentes $15$ -figuras de celdas, ninguna de las cuales está conectada, aunque ésta es la que más se acerca:
Takahiro Waki
Puntos
1
(1) 
(2) 
(3) 
Uno de ellos tiene dos esquinas. Entonces en el caso de $(1)$ , otra forma también debe tener dos esquinas. Sin embargo $(2,1)(4,1)(2,5)(4,5)$ no puede dividirse en tres áreas.
En el caso de $(2)$ no podemos dibujar $(3,3), (5,1)$ o $(5,5)$ en un color, satisfaciendo la condición.
En el caso de $(3)$ si dibujamos el color de $(3,3)$ no podemos hacer formas congruentes. Por lo tanto tres formas congruentes son imposibles.
