En un artículo de 1969, el matemático holandés Nicolaas Govert de Bruijn demostró varios resultados sobre el empaquetado de ladrillos rectangulares congruentes (de cualquier dimensión) en cajas rectangulares más grandes, de tal manera que no quede espacio. Uno de estos resultados se conoce ahora como teorema de De Bruijn . De acuerdo con este teorema, un "ladrillo armónico" (uno en el que la longitud de cada lado es un múltiplo de la siguiente longitud del lado más pequeño) solo se puede empaquetar en una caja cuyas dimensiones sean múltiplos de las dimensiones del ladrillo. [1]
Ejemplo
De Bruijn fue llevado a demostrar este resultado después de que su hijo de siete años, FW de Bruijn, no pudo empacar ladrillos de dimensiones en un cubo. [2] [3] El cubo tiene un volumen igual al de ladrillos, pero solo se pueden empaquetar ladrillos. Una forma de ver esto es dividir el cubo en cubos más pequeños de tamaño coloreados alternativamente en blanco y negro. Este color tiene más celdas unitarias de un color que del otro, pero con este color cualquier ubicación delEl ladrillo debe tener el mismo número de celdas de cada color. Por lo tanto, cualquier mosaico con 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 empaque perfecto con estas dimensiones es imposible, de una manera más general que se aplica a muchas otras dimensiones de ladrillos y cajas.
Cajas que son múltiplos del ladrillo
Suponga que un -La caja rectangular dimensional (matemáticamente un cuboide ) tiene longitudes de lados enteros y un ladrillo tiene longitudes . Si los lados del ladrillo se pueden multiplicar por otro conjunto de números enteros así que eso son una permutación de, la caja se llama múltiplo del ladrillo. Luego, la caja se puede llenar con estos ladrillos de una manera trivial con todos los ladrillos orientados de la misma manera. [1]
Una generalización
No todos los embalajes involucran cajas que sean múltiplos de ladrillos. Por ejemplo, como observa De Bruijn, un La 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 al menos uno de los es un múltiplo. En el ejemplo anterior, el lado de la longitud es un múltiplo de ambos y . [1]
Ladrillos armónicos
El segundo de los resultados de De Bruijn, el llamado teorema de De Bruijn, se refiere al caso en el que cada lado del ladrillo es un múltiplo entero del siguiente lado más pequeño. De Bruijn llama armónico a un ladrillo con esta propiedad . Por ejemplo, los ladrillos más utilizados en EE. UU. Tienen dimensiones (en pulgadas), que no es armónico, pero un tipo de ladrillo vendido como "ladrillo romano" tiene las dimensiones armónicas . [5]
El teorema de De Bruijn establece que, si un ladrillo armónico se empaqueta 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 es un múltiplo de seis y uno de los dos lados restantes es par. [1] [6] Los empaques de un ladrillo armónico en una caja pueden involucrar copias del ladrillo que se rotan entre sí. Sin embargo, el teorema establece que las únicas cajas que pueden empaquetarse de esta manera son cajas que también podrían empaquetarse mediante traslados del ladrillo.
Boisen (1995) proporcionó una prueba alternativa del caso tridimensional del teorema de De Bruijn, basado en el álgebra de polinomios . [7]
Ladrillos no armónicos
El tercero de los resultados de De Bruijn es que, si un ladrillo no es armónico, entonces hay una caja que puede llenar que no es un múltiplo del ladrillo. El embalaje de la ladrillo en el El cuadro proporciona un ejemplo de este fenómeno. [1]
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 copias de un ladrillo con dimensiones , colocados uno al lado del otro. Por la misma razón, una caja con dimensiones y También es fácil de empaquetar con copias del mismo ladrillo. Al girar una de estas dos cajas para que sus lados largos queden paralelos y colocarlas una al lado de la otra, se forma 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.
Referencias
- ↑ a b c d e de Bruijn, NG (1969), "Llenar cajas con ladrillos" , The American Mathematical Monthly , 76 (1): 37–40, doi : 10.2307 / 2316785 , JSTOR 2316785 , MR 0234841.
- ^ Honsberger, Ross (1976), Gemas Matemáticas II , Washington, DC: Asociación Matemática de América, p. 69, ISBN 9780883853009.
- ^ Nienhuys, JW (11 de septiembre de 2011), Kloks, Ton; Hung, Ling-Ju (eds.), Combinatoria de De Bruijn: notas de clase , p. 156.
- ^ Watkins, John J. (2012), A través del tablero: Las matemáticas de los problemas del tablero de ajedrez , Princeton University Press, p. 226, ISBN 9781400840922.
- ^ Kreh, RT (2003), Habilidades de albañilería (5ª ed.), Cengage Learning, p. 18, ISBN 9780766859364.
- ^ Stein, Sherman K .; Szabó, Sándor (1994), Algebra and Tiling: Homomorphisms in the Service of Geometry , Carus Mathematical Monographs, 25 , Washington, DC: Asociación Matemática de América, p. 52 , ISBN 0-88385-028-1, MR 1311249.
- ^ Boisen, Paul (1995), "Polinomios y empaquetaduras: una nueva demostración del teorema de De Bruijn", Matemáticas discretas , 146 (1-3): 285-287, doi : 10.1016 / 0012-365X (94) 00070-1 , MR 1360122.
enlaces externos
- Weisstein, Eric W. "Teorema de Bruijn" . MathWorld .