¿Cuál es el poliomino más pequeño que no puede rodear un agujero de $1 \times 1$?

Question

Dado un poliominó $P$, podemos preguntar si es posible que copias disjuntas de $P$ rodeen una sola celda en la cuadrícula cuadrada, es decir, para que el complemento de su unión tenga un componente conectado de tamaño $1$.

Podemos refinar aún más esto en poliominós que rodean débilmente una celda (simplemente cubriendo las cuatro celdas adyacentes al borde) y aquellos que rodean fuertemente una celda (cubriendo todas las $8$ cuadrados que comparten un vértice con el agujero). Gracias a Julian Rosen por aclarar esta distinción.

Intuitivamente, pensaba que siempre era posible, pero tenía dificultades para demostrarlo; después de suficiente lucha para demostrar que era cierto, comencé a buscar contraejemplos. Aquí hay un poliominó con $48$ celdas que ni siquiera rodea débilmente a una región de una sola celda, lo cual no es demasiado difícil de verificar manualmente:

                                                    

Después de algunas modificaciones, he reducido esto a una solución simplemente conectada con $26$ celdas:

                                                    

Tengo un ejemplo de tamaño $23$ de un poliominó que no rodea fuertemente un agujero:

                                                    

¿Cuál es el poliominó más pequeño que no puede rodear un agujero de una sola celda? Estoy interesado en esta pregunta tanto para los casos débiles como fuertes.

He escrito un código para explorar esto, y he confirmado que todos los $1,227,708$ poliominós libres con un máximo de $14$ celdas pueden rodear fuertemente un agujero. ¿Cuánto podemos ajustar estos límites?

Answer 1

Esta no es en absoluto una respuesta completa, pero como mencioné en mi último comentario, podemos avanzar restringiendo una búsqueda informática a clases de simetría particulares. He podido verificar todos los poliominós libres de tamaño $N \le 23$ que tienen un eje de simetría horizontal o vertical (una clase que contiene el ejemplo de tamaño-$23$ no fuertemente rodeante del OP). Dentro de esta clase de simetría, no hay ejemplos no débilmente rodeantes de tamaño $N \le 23$, y los ejemplos no fuertemente rodeantes más pequeños tienen tamaño $N=23$; por lo tanto, el ejemplo del OP es mínimo. De los $464188$ poliominós libres de tamaño-$23$ con un eje de simetría horizontal o vertical, solo hay dos que no pueden rodear fuertemente una sola celda: el ejemplo dado en la pregunta, y el poliominóo representado a continuación.

                                                    

Heurísticamente, se podría esperar que los ejemplos mínimos tengan algo de simetría, porque los poliominós simétricos tienen las "regiones locales que se ven diferentes" más pequeñas, y por lo tanto, menos posibilidades diferentes para empaquetar regiones locales alrededor de un agujero. Los próximos pasos podrían ser verificar los otros dos grandes clases de simetría para poliominós libres: simetría de rotación de $180^\circ$ alrededor de un punto y simetría de reflexión a través de una diagonal.

---

Actualización: Al verificar los poliominós con simetría de rotación alrededor de un punto, se encontró el siguiente ejemplo mínimo (dentro de esa clase) no fuertemente rodeante, con tamaño $20$:

                                                    

---

Segunda actualización: Al verificar los poliominós con simetría de reflexión diagonal, hay exactamente dos ejemplos mínimos (dentro de esa clase) de tamaño $19$ que no son fuertemente rodeantes. Uno se forma eliminando una celda interior del ejemplo anterior (como ya se señaló en un comentario), y el otro es nuevo:

                                  

---

Tercera actualización: Para avanzar en el caso de no débilmente rodeante (que es un criterio más estricto, por lo que los ejemplos mínimos son al menos tan grandes), miré poliominós con simetrías de reflexión vertical y horizontal. El ejemplo de tamaño-$25$ a continuación proporciona un límite superior mejorado para este caso.