Teorema de De Bruijn

Sobre el embalaje de ladrillos rectangulares congruentes (de cualquier dimensión) en cajas rectangulares más grandes

Una coloración de los cubos unitarios en una caja que puede usarse para demostrar la imposibilidad de llenarla con ladrillos, ya que cada ladrillo cubre 4 cubos blancos y 4 negros, pero la caja contiene 8 cubos blancos más que negros. ${\displaystyle 6\cdot 6\cdot 6}$ ${\displaystyle 1\cdot 2\cdot 4}$

En un artículo de 1969, el matemático holandés Nicolaas Govert de Bruijn demostró varios resultados sobre el empaquetamiento de ladrillos rectangulares congruentes (de cualquier dimensión) en cajas rectangulares más grandes, de tal manera que no quede espacio libre. Uno de estos resultados se conoce ahora como el teorema de De Bruijn . Según este teorema, un "ladrillo armónico" (uno en el que la longitud de cada lado es un múltiplo de la longitud del lado inmediatamente inferior) solo se puede empaquetar en una caja cuyas dimensiones sean múltiplos de las dimensiones del ladrillo. ^[1]

Ejemplo

De Bruijn se vio obligado a demostrar este resultado después de que su hijo de siete años, F. W. de Bruijn, no pudiera empaquetar ladrillos de dimensiones iguales en un cubo. ^{[2] [3]} El cubo tiene un volumen igual al de los ladrillos, pero solo se pueden empaquetar ladrillos en él. Una forma de ver esto es dividir el cubo en cubos más pequeños de tamaño coloreados alternativamente en blanco y negro. Esta coloración tiene más celdas unitarias de un color que del otro, pero con esta coloración cualquier colocación del ladrillo debe tener el mismo número de celdas de cada color. Por lo tanto, cualquier mosaico de ladrillos también tendría el mismo número de celdas de cada color, una imposibilidad. ^[4] El teorema de De Bruijn demuestra que un empaquetamiento perfecto con estas dimensiones es imposible, de una manera más general que se aplica a muchas otras dimensiones de ladrillos y cajas. ${\displaystyle 1\cdot 2\cdot 4}$ ${\displaystyle 6\cdot 6\cdot 6}$ ${\displaystyle 27}$ ${\displaystyle 26}$ ${\displaystyle 27}$ ${\displaystyle 2\cdot 2\cdot 2}$ ${\displaystyle 1\cdot 2\cdot 4}$

Cajas que son múltiplos del ladrillo

Supongamos que una caja rectangular de dimensión 1 (matemáticamente un cuboide ) tiene lados de longitudes enteras y un ladrillo tiene longitudes . Si los lados del ladrillo se pueden multiplicar por otro conjunto de números enteros de modo que sean una permutación de , la caja se denomina múltiplo del ladrillo. La caja se puede llenar con dichos ladrillos de una manera trivial con todos los ladrillos orientados de la misma manera. ^[1] ${\displaystyle d}$ ${\displaystyle A_{1}\cdot A_{2}\cdot \dotso \cdot A_{d}}$ ${\displaystyle a_{1}\cdot a_{2}\cdot \dotso \cdot a_{d}}$ ${\displaystyle b_{i}}$ ${\displaystyle a_{1}b_{1},a_{2}b_{2},\dots a_{d}b_{d}}$ ${\displaystyle A_{1},A_{2},\dots ,A_{d}}$

Una generalización

No todos los empaques implican cajas que son múltiplos de ladrillos. Por ejemplo, como observa de Bruijn, una caja rectangular se puede llenar con copias de un ladrillo rectangular, aunque no con todos los ladrillos orientados de la misma manera. Sin embargo, de Bruijn (1969) demuestra que si los ladrillos pueden llenar la caja, entonces para cada uno al menos uno de los es un múltiplo. En el ejemplo anterior, el lado de longitud es un múltiplo de ambos y . ^[1] ${\displaystyle 5\cdot 6}$ ${\displaystyle 2\cdot 3}$ ${\displaystyle a_{i},}$ ${\displaystyle A_{i}}$ ${\displaystyle 6}$ ${\displaystyle 2}$ ${\displaystyle 3}$

Ladrillos armónicos

El segundo de los resultados de De Bruijn, llamado teorema de De Bruijn, se refiere al caso en el que cada lado del ladrillo es un múltiplo entero del lado inmediatamente inferior. De Bruijn llama a un ladrillo con esta propiedad armónico . Por ejemplo, los ladrillos más utilizados en los EE. UU. tienen dimensiones (en pulgadas) que no son armónicas, pero un tipo de ladrillo vendido como "ladrillo romano" tiene las dimensiones armónicas . ^[5] ${\displaystyle 2{\tfrac {1}{4}}\cdot 4\cdot 8}$ ${\displaystyle 2\cdot 4\cdot 12}$

El teorema de De Bruijn establece que, si se empaqueta un ladrillo armónico en una caja, entonces la caja debe ser un múltiplo del ladrillo. Por ejemplo, el ladrillo armónico tridimensional con longitudes de lado 1, 2 y 6 solo se puede empaquetar en cajas en las que uno de los tres lados sea múltiplo de seis y uno de los dos lados restantes sea par. ^{[1] [6]} Los empaquetamientos de un ladrillo armónico en una caja pueden implicar copias del ladrillo que se rotan unas con respecto a otras. Sin embargo, el teorema establece que las únicas cajas que se pueden empaquetar de esta manera son las cajas que también podrían empaquetarse mediante traslaciones del ladrillo.

Boisen (1995) proporcionó una prueba alternativa del caso tridimensional del teorema de De Bruijn, basada en el álgebra de polinomios . ^[7]

Ladrillos no armónicos

El tercer resultado de De Bruijn es que, si un ladrillo no es armónico, entonces existe una caja que puede llenar que no es un múltiplo del ladrillo. El empaquetamiento del ladrillo en la caja proporciona un ejemplo de este fenómeno. ^[1] ${\displaystyle 2\cdot 3}$ ${\displaystyle 5\cdot 6}$

Una caja, revestida con ladrillos, para el estuche y ${\displaystyle (a_{1}+a_{2})\cdot (a_{1}a_{2})}$ ${\displaystyle a_{1}\cdot a_{2}}$ ${\displaystyle a_{1}=2}$ ${\displaystyle a_{2}=5}$

En el caso bidimensional, el tercero de los resultados de de Bruijn es fácil de visualizar. Una caja con dimensiones y es fácil de empacar con copias de un ladrillo con dimensiones , colocadas una al lado de la otra. Por la misma razón, una caja con dimensiones y también es fácil de empacar con copias del mismo ladrillo. Al girar una de estas dos cajas de modo que sus lados largos sean paralelos y colocarlas una al lado de la otra, se obtiene un empaque de una caja más grande con y . Esta caja más grande es un múltiplo del ladrillo si y solo si el ladrillo es armónico. ${\displaystyle A_{1}=a_{1}}$ ${\displaystyle A_{2}=a_{1}\cdot a_{2}}$ ${\displaystyle a_{1}}$ ${\displaystyle a_{1},a_{2}}$ ${\displaystyle A_{1}=a_{1}\cdot a_{2}}$ ${\displaystyle A_{2}=a_{2}}$ ${\displaystyle A_{1}=a_{1}+a_{2}}$ ${\displaystyle A_{2}=a_{1}\cdot a_{2}}$

Referencias

1. de Bruijn, NG (1969), "Rellenar cajas con ladrillos", The American Mathematical Monthly , 76 (1): 37–40, doi :10.2307/2316785, JSTOR  2316785, MR  0234841.
2. Honsberger, Ross (1976), Gemas matemáticas II , Washington, DC: Asociación Matemática de América, pág. 69, ISBN 9780883853009.
3. Nienhuys, JW (11 de septiembre de 2011), Kloks, Ton; Hung, Ling-Ju (eds.), Combinatoria de De Bruijn: notas de clase, p. 156.
4. Watkins, John J. (2012), Across the Board: The Mathematics of Chessboard Problems, Princeton University Press, pág. 226, ISBN 9781400840922.
5. Kreh, RT (2003), Habilidades de albañilería (5.ª ed.), Cengage Learning, pág. 18, ISBN 9780766859364.
6. Stein, Sherman K.; Szabó, Sándor (1994), Álgebra y mosaico: homomorfismos al servicio de la geometría , Carus Mathematical Monographs, vol. 25, Washington, DC: Asociación Matemática de América, pág. 52, ISBN 0-88385-028-1, Sr.  1311249.
7. Boisen, Paul (1995), "Polinomios y empaquetamientos: una nueva prueba del teorema de De Bruijn", Discrete Mathematics , 146 (1–3): 285–287, doi :10.1016/0012-365X(94)00070-1, MR  1360122.

Enlaces externos

• Weisstein, Eric W. , "Teorema de De Bruijn", MathWorld