Teorema de De Bruijn
![](http://upload.wikimedia.org/wikipedia/commons/thumb/6/64/De_Bruijn_theorem_coloring.svg/220px-De_Bruijn_theorem_coloring.svg.png)
En un artículo de 1969, el matemático holandés Nicolaas Govert de Bruijn demostró varios resultados sobre cómo empaquetar ladrillos rectangulares congruentes (de cualquier dimensión) en cajas rectangulares más grandes, de tal manera que no quede espacio entre ellos. Uno de estos resultados se conoce ahora como 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 del siguiente lado más pequeño) solo se puede empaquetar de forma compacta 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, que entonces tenía siete años, F. W. de Bruijn, no pudiera empaquetar ladrillos de dimensión en un cubo que medía .[2][3] El cubo tiene un volumen igual al de ladrillos, pero solo se pueden empaquetar en él 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. Esta coloración tiene más celdas unitarias de un color que del otro, pero con esta coloración cualquier ubicación de un ladrillo de debe tener el mismo número de celdas de cada color. Por lo tanto, cualquier alicatado mediante ladrillos también debería tener el mismo número de celdas de cada color, algo que es imposible.[4] El teorema de De Bruijn demuestra que un empaquetado perfecto (sin huecos) 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
Supóngase que una caja rectangular de dimensiones (matemáticamente un cuboide) tiene longitudes laterales enteras y un ladrillo tiene longitudes . Si los lados del ladrillo se pueden multiplicar por otro conjunto de números enteros de modo que sea una permutación de , la caja se llama "múltiplo" del ladrillo. Entonces, la caja se puede llenar con dichos ladrillos de forma trivial, con todos los ladrillos orientados de la misma manera.[1]
Generalización
No todos los empaquetdos incluyen cajas cuyas sus dimensiones son todas múltiplos de las de los ladrillos. Por ejemplo, como observó De Bruijn, una caja rectangular de se puede llenar con ladrillos rectangulares de , aunque no con todos los ladrillos orientados de la misma manera. Sin embargo, de Bruijn (1969) demostró que si los ladrillos pueden llenar la caja, entonces al menos uno de los es un múltiplo de cada En el ejemplo anterior, el lado de longitud es un múltiplo de y de .[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 son armónicas, pero un tipo de ladrillo vendido como "ladrillo romano" tiene 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 lados 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 empaquetados de un ladrillo armónico en una caja pueden implicar copias del ladrillo que giran entre sí. Sin embargo, el teorema establece que las únicas cajas que se pueden empaquetar de esta manera son las cajas que también se pueden empaquetar mediante traslaciones del ladrillo.
Boisen (1995) ideó una demostración alternativa del caso tridimensional del teorema de De Bruijn, basada 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 se puede llenar y que no es un múltiplo del ladrillo. El embalaje del ladrillo en la caja de proporciona un ejemplo de este fenómeno.[1]
![](http://upload.wikimedia.org/wikipedia/commons/thumb/d/dc/7x10_box_packed_with_2x5_bricks.svg/220px-7x10_box_packed_with_2x5_bricks.svg.png)
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 rellenar con ladrillos de dimensiones , colocados unos al lado de los otros. Por la misma razón, una caja con dimensiones y también es fácil de empaquetar con el mismo tipo de ladrillos. Al girar una de estas dos cajas para que sus lados largos queden paralelos y colocarlas una al lado de la otra, se empaqueta 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, N. G. (1969), «Filling boxes with bricks», The American Mathematical Monthly 76 (1): 37-40, JSTOR 2316785, MR 0234841, doi:10.2307/2316785 ..
- ↑ Honsberger, Ross (1976), Mathematical Gems II, Washington, DC: Mathematical Association of America, p. 69, ISBN 9780883853009 ..
- ↑ Nienhuys, J. W. (11 de septiembre de 2011), Kloks, Ton; Hung, Ling-Ju, eds., De Bruijn's combinatorics: classroom notes, p. 156 ..
- ↑ Watkins, John J. (2012), Across the Board: The Mathematics of Chessboard Problems, Princeton University Press, p. 226, ISBN 9781400840922 ..
- ↑ Kreh, R. T. (2003), Masonry Skills (5th edición), 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: Mathematical Association of America, p. 52, ISBN 0-88385-028-1, MR 1311249 ..
- ↑ Boisen, Paul (1995), «Polynomials and packings: a new proof of de Bruijn's theorem», Discrete Mathematics 146 (1–3): 285-287, MR 1360122, doi:10.1016/0012-365X(94)00070-1 ..
Enlaces externos
- Weisstein, Eric W. «de Bruijn's Theorem». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research.
Datos: Q5244285