Construyendo un cubo a partir de pequeños ladrillos de manera que ninguna línea pueda ser empujada entre las costuras.

Question

Estoy improvisando sobre una vieja pregunta de entrenamiento de concursos con la que me enfrenté hace 40 años.

El problema original era:

Se construye un cubo sólido de $20\times20\times20$ a partir de ladrillos rectangulares de dimensiones $2\times2\times1$. Demuestra que es posible "empujar" una línea a través del cubo de tal manera que la línea no sea obstruida por ninguno de los ladrillos.

Solución: Necesitamos $2000$ ladrillos para construir este cubo. Imagina que los bordes del cubo se alinean con los ejes de coordenadas, y que el cubo está en el primer octante con uno de sus vértices en el origen. Entonces hay $19^2$ líneas paralelas al eje $z$ que atraviesan el cubo, cada una dada por las ecuaciones $x=a, y=b, a,b\in\{1,2,\ldots,19\}$, líneas parametrizadas por la elección del par $(a,b)$. De manera similar, hay $19^2$ líneas paralelas a los ejes $x$ y $y$ para un total de $3\cdot19^2$ líneas. Resulta que una de estas líneas atravesará el cubo a lo largo de las grietas entre los ladrillos. La observación clave es que cada línea será bloqueada por un número par de ladrillos (spoiler oculto a continuación por si prefieres pensarlo por ti mismo).

Tomemos una de esas líneas, digamos $z$ arbitrario, $x=a$, $y=b$. Considera los dos planos, el primero definido por $x=a$ y el segundo por $y=b$. Estos dos planos dividen el cubo en cuatro partes, cuyo volumen es un número entero par. Luego considera cómo los ladrillos están divididos por estos dos planos. Vemos que un ladrillo bloqueará esta línea si y solo si su volumen se divide equitativamente entre las cuatro partes, contribuyendo de forma impar a cada parte. La afirmación sigue.

Dado que $2\cdot3\cdot19^2>2000$, es imposible que todas estas líneas estén bloqueadas por dos o más ladrillos. Por lo tanto, al menos una de ellas no está obstruida, lo que prueba la afirmación.

Ok, esa fue la historia de fondo. Continuemos con la pregunta real.

A medida que el tamaño del cubo, llámalo $n$, crece, el número de ladrillos aumenta como $n^3/4$, pero el número de esas líneas, llámalas líneas enteras, aumenta solo como un polinomio cuadrático de $n$. Por lo tanto, tarde o temprano el argumento anterior deja de funcionar. De hecho, esto ocurre ya con $n=22$ ya que $2\cdot3\cdot21^2<22^3/4$. Los parámetros $a,b$ obviamente van desde $1$ hasta $n-1$.

¿Es posible construir un cubo sólido de $22\times22\times22$ con ladrillos de $2\times2\times1$ de tal manera que todas las líneas enteras estén bloqueadas por al menos un (por lo tanto, al menos dos) ladrillos? Si esto no es posible con $n=22$, ¿cuál es el valor más pequeño de $n$ para el cual esta construcción es posible (si existe)?

---

Dado que la respuesta a mi pregunta es desconocida, agradeceré respuestas explicando una construcción para la elección del respondiente de $n$.

Answer 1

Considera la recta determinada por $(x,y)=(a,b)$ y las cuatro regiones en las cuales los planos $x=a$ y $y=b$ dividen nuestro cubo de $2n\times 2n\times 2n$. En particular, considera el número de cubos unitarios dentro de las regiones diagonalmente opuestas $x,y\leq a,b$ y $x,y\geq a,b$, que es $$2nab+2n(2n-a)(2n-b)\equiv 0\bmod 4.$$ Módulo $4$, esto es equivalente al doble del número de bloques que cruzan los planos $x=a$ o $y=b$ (los bloques cuyos centros la recta $(x,y)=(a,b)$ atraviesa deben contarse solo una vez aquí, no dos veces). Vemos que una de estas rectas debe atravesar los centros de al menos $4$ bloques. De lo contrario, entonces el número total de bloques es exactamente $2$ para cada una de estas rectas; sin embargo, hay $8n-5\equiv 1\bmod 2$ tales rectas.

Entonces, tenemos un conjunto de rectas $L$ tales que, para cada par de planos intersectados dentro de nuestro cubo de $2n\times2n\times2n$, al menos uno de ellos contiene una recta en $L$. Necesitamos establecer un límite inferior para el tamaño de este conjunto $L$.

---

Lema. Considera rectas completamente dentro de un prisma rectangular de $u\times v\times w$ con $u+v+w$ par (entonces, si $u=v=w=2$, hay $3$ tales rectas). Un conjunto $L$ de estas rectas satisface que, para cualquier par de planos (reticulados) intersectados dentro de este prisma rectangular, $L$ contiene al menos una recta que se encuentra completamente en uno de estos planos. Entonces, $|L|\geq \frac{u+v+w}2-1$.

Prueba. Demostramos esto por inducción en $u+v+w$ con $u,v,w\geq 2$. Nuestro paso inductivo solo tratará con $u,v,w>2$, así que necesitamos probar el caso en el que, sin pérdida de generalidad, $u=2$ en nuestro caso base. Haremos esto después del paso inductivo.

Sin pérdida de generalidad, permita que la recta $(x,y)=(u-1,v-1)$ esté en $L$. Considera una nueva construcción $L'$ en un prisma de $u-1\times v-1\times w$ que consiste en un máximo de $|L|-1$ rectas de manera que

• dada una recta $\ell\in L$ que no esté en $x=u-1$ o en $y=v-1$, $\ell$ se agrega a $L'$,

• dada una recta $\ell\in L$ con $x=u-1$, la recta $\ell-(1,0,0)$ se agrega a $L'$, y

• dada una recta $\ell\in L$ con $y=v-1$, la recta $\ell-(0,1,0)$ se agrega a $L'$.

Vemos que $L'$ satisface las condiciones requeridas, ya que un plano $P$ en el caso de $u-1\times v-1\times w$ contiene una recta en $L$ si y solo si contiene una recta en $L'$. Esto reduce $u+v+w$ en $2$ y el número de rectas en (al menos) $1$, por lo que podemos aplicar nuestra hipótesis inductiva para finalizar.

Este argumento funciona para reducir $u+v+w$ mientras haya una recta que se pueda elegir y que no reduzca la longitud de ningún lado a menos de $2$, así que si no podemos hacer el argumento anterior, podemos asumir que $u=2$ y que no hay rectas de la forma $(y,z)=(b,c)$ en $L$. Aquí, debemos tener que, para cualquier $y=b$, la recta $(x,y)=(1,b)$ está en $L$, y para cualquier $z=c$ la recta $(x,z)=(1,c)$ está en $L$, por lo que $L$ tiene un tamaño de al menos $$v+w-2=(v-2)+(w-2)+2\geq \frac{v+w}{2}=\frac{u+v+w}{2}-1,$ terminando nuestra prueba. $\square$

---

Entonces, $L$ tiene un tamaño de al menos $3n-1$. Esto significa que el número de bloques cuyos centros son intersectados por algunas rectas es al menos $$2\left(3(2n-1)^2\right)+2(3n-1).$$ En $n=11$ esto es $2710$, que es más que $2\cdot 11^3$, finalizando la prueba para un cubo de lado $22$. Lamentablemente, esto no es lo suficientemente fuerte para resolver el caso $n=24$.

Answer 2

Me encontré con un problema de dos dimensiones similar cuando era un escolar, leyendo una traducción rusa de 1971 de "Rompecabezas matemáticos y diversiones" de Martin Gardner. A continuación añado las partes relevantes de su artículo "Políominos y rectángulos sin defectos" extraído de "Nuevas diversiones matemáticas".

Answer 3

He escrito un programa que implementa una construcción aleatoria similar a la de mi otra respuesta, y he usado este programa para encontrar un mosaico que bloquee todas las líneas para el caso $n = 102$.

Lamentablemente, esto no es muy revelador: el mosaico es aleatorio y (esencialmente) desestructurado, y no proporciona mucha información sobre la naturaleza del problema. Me gustaría ver una construcción que pueda ser razonablemente verificada por un humano; mi publicación tiene principalmente la intención de obtener un poco de cierre y establecer un límite superior razonable.

Enfoque (similar a la otra respuesta):

Nuevamente, para mayor comodidad queremos pensar en el cubo de $n \times n \times n$ como un cubo de $k \times k \times k$ de subcubos de $2 \times 2 \times 2$ (a los que simplemente me referiré como "cubos"), con centros en puntos en $\{1, 3, 5, \dots, 2k-1\}^3$. El principal beneficio de esta idea es que permite una construcción muy modular, donde podemos colocar una configuración dada de baldosas localmente (llenando completamente un pequeño número de cubos adyacentes) sin preocuparnos por cómo esto afectará la estructura global del mosaico.

La idea es colocar, para cada línea, una pequeña configuración de baldosas que bloquee la línea. La configuración utilizada depende de la paridad de las coordenadas de la línea. Considere una línea en la dirección $z$, dada por las ecuaciones $x = a$ e $y = b$. Para cualquier línea de este tipo, nuestra configuración se colocará en algún nivel $h$, para un $h$ impar entre $1$ y $2k-1$. Si tanto $a$ como $b$ son impares, colocamos la primera configuración debajo en el cubo con centro en $(a, b, h)$. Si $a$ es impar y $b$ es par, colocamos la segunda configuración debajo en los cubos adyacentes con centros en $(a, b-1, h)$, $(a, b+1, h)$. De manera similar, si $a$ es par y $b$ es impar, colocamos la segunda configuración en los cubos adyacentes con centros en $(a-1, b, h)$, $(a+1, b, h)$. Finalmente, si tanto $a$ como $b$ son pares, colocamos la tercera configuración debajo en los cubos adyacentes con centros en $(a-1, b-1, h)$, $(a-1, b+1, h)$, $(a+1, b-1, h)$, $(a+1, b+1, h)$.

Espero que los diagramas aclaren que si se colocan como se describe, una configuración bloqueará su línea asociada. Versiones rotadas de las configuraciones anteriores pueden colocarse análogamente para bloquear líneas en las direcciones $x$ y $y$. Una vez que hemos elegido un nivel para cada línea, nuestro trabajo está hecho siempre y cuando las configuraciones de baldosas, al colocarse en los niveles asociados, no se superpongan: después de colocar estas configuraciones, ningún cubo está parcialmente lleno, por lo que podemos llenar todos los cubos vacíos de acuerdo con la primera configuración anterior, produciendo un mosaico completo del cubo de $n \times n \times n$. Por lo tanto, para construir un buen mosaico, es suficiente dar una lista de niveles para todas las líneas que no produzca superposiciones.

Resultados:

He escrito un programa que implementa la idea anterior eligiendo niveles al azar para cada línea, una por una. Mientras lo hace, el programa construye un esqueleto del mosaico, llenando los cubos ocupados por las configuraciones especificadas, verificando que no se produzca superposición. Para una línea dada, si el nivel elegido produce superposición con las configuraciones de bloqueo colocadas anteriormente, el programa lo intenta nuevamente, eligiendo un nuevo nivel al azar repetidamente hasta que se encuentre uno que no produzca superposición. Si no puede encontrar uno, el programa se rinde.

En el caso $n = 110$, el programa tiene éxito, empíricamente, alrededor del 80% del tiempo. Para $n$ un poco por debajo de esto, comienza a fallar la mayor parte del tiempo. El mosaico exitoso más pequeño que encontré fue en $n = 102$. He publicado esto en un archivo de pastebin aquí. El mosaico está formateado como tres matrices anidadas en sintaxis de python, de manera que el nivel para la línea en la dirección $x$ dada por $y = a$, $z = b$ es xlist[a-1][b-1], el nivel para la línea en la dirección $y$ dada por $x = a$, $z = b$ es ylist[a-1][b-1], y el nivel para la línea en la dirección $z$ dada por $x = a, y = b$ es zlist[a-1][b-1]. También he añadido código python que realiza el paso de verificación, de comprobar que no se produce superposición al colocar configuraciones en los niveles especificados, en otro archivo de pastebin aquí.

Answer 4

Espero que exista una construcción requerida para $n$ suficientemente grande y debería demostrarse mediante un ejemplo concreto. Pero creo que un revestimiento correspondiente es bastante irregular, por lo que es difícil de describir y su construcción es más bien una tarea para un solucionador de acertijos que para un matemático. Así que lo posteé también en Puzzling.SE.

Dado que los revestimientos considerados son demasiado complicados para ser tratados a mano, escribí un programa auxiliar. Lo comparto para facilitar a otros usuarios de MSE la resolución del problema y, posiblemente, ganar la recompensa. El programa tiene una interfaz sencilla e intuitiva, que se asemeja un poco a “Tetris”, vea una captura de pantalla del programa. En el campo de trabajo principal se muestran dos capas consecutivas del cubo de un tamaño seleccionado, paralelas a uno de los tres planos de coordenadas, que también se pueden seleccionar. Los ladrillos se pueden añadir o quitar en unos pocos clics, consulte la ayuda del programa para más detalles. Para facilitar la diversidad, cada nuevo ladrillo obtiene un color aleatorio personal. Los puntos rojos indican las líneas desbloqueadas, perpendiculares a los respectivos planos de coordenadas. Los revestimientos parciales construidos se pueden guardar y cargar. Descargas: un archivo ejecutable para Windows, un archivo zip con los archivos fuente de Delphi 5. He dedicado una respuesta separada al programa para posibles preguntas o discusiones relacionadas, como errores informados o propuestas de mejora. También le he descrito el problema a mi colega, el Dr. Misha Mytrofanov, quien se mostró interesado y va a trabajar con el programa hoy.