Teorema de De Bruijn

El teorema de De Bruijn es el resultado de la geometría combinatoria , según la cual los bloques rectangulares (de cualquier dimensión) en los que la longitud de cada lado es un múltiplo de la siguiente longitud del lado más pequeño ("ladrillos armoniosos") solo pueden empaquetarse en un bloque rectangular. ("caja"), el tamaño de cuyos lados es un múltiplo de los lados del ladrillo.

Establecido y publicado en 1969 por el matemático holandés Nicholas de Bruijn en un artículo, junto con otros resultados sobre el empaquetamiento de bloques rectangulares congruentes - ladrillos en grandes bloques rectangulares - cajas, de modo que no quede espacio vacío [1] .

Ejemplo

De Bruijn probó esta afirmación después de que su hijo de siete años no pudiera encajar bloques de tamaño en un cubo [2] [3] . El cubo tenía un volumen igual al volumen de los bloques, pero solo se pueden colocar bloques en él. Para entender esto, dividamos el cubo en cubos más pequeños, coloreados alternativamente en blanco y negro, y tengamos en cuenta que dicha partición tiene más cubos unitarios (celdas) de un color que de otro, mientras que cualquier empaquetamiento de bloques en un cubo debe tener un tamaño igual . número de celdas de cada color [4] . El teorema de De Bruijn demuestra que es imposible un empaquetamiento perfecto con tales longitudes laterales. El teorema se aplica a otros tamaños de ladrillos y cajas. ${\ estilo de visualización 1 \ veces 2 \ veces 4}$ ${\ estilo de visualización 6 \ veces 6 \ veces 6}$ $27$ ${\ estilo de visualización 26}$ $27$ ${\ estilo de visualización 1 \ veces 2 \ veces 4}$

Cajas que son múltiplos de bloques

Suponga que una caja rectangular bidimensional (en términos matemáticos, un paralelepípedo ) tiene longitudes de lado enteras y los ladrillos tienen longitudes de lado . Si las longitudes de los lados de un ladrillo se pueden multiplicar por números enteros y el resultado de la multiplicación es una permutación de los números , se dice que la caja es un múltiplo del ladrillo. Luego, la caja se puede llenar con dichos ladrillos de manera trivial con la misma orientación de los ladrillos [1] . $d$ ${\displaystyle A_{1}\times A_{2}\times \dots \times A_{d))$ ${\displaystyle a_{1}\times a_{2}\times \dots \times a_{d))$ $bi}$ ${\displaystyle a_{1}b_{1},a_{2}b_{2},\puntos a_{d}b_{d))$ ${\displaystyle A_{1},A_{2},\puntos,A_{d))$

Generalización

No para todos los paquetes, la caja debe ser necesariamente un múltiplo de un ladrillo. Por ejemplo, como señaló de Bruijn, una caja rectangular se puede llenar con copias de ladrillos rectangulares, pero no todos los ladrillos tendrán la misma orientación. Sin embargo, de Bruijn [5] probó que si los ladrillos pueden llenar una caja, entonces para cada uno , al menos una de las cantidades debe ser un múltiplo de uno de los lados del ladrillo. En el ejemplo anterior, la longitud del lado de la caja es un múltiplo de ambos y [1] . ${\ estilo de visualización 5 \ veces 6}$ ${\ estilo de visualización 2 \ veces 3}$ ${\ estilo de visualización a_ {i},}$ $Ai}$ $6$ $2$ $3$

Ladrillos armoniosos

El segundo resultado de de Bruijn, que se llama teorema de de Bruijn, se refiere al caso en que cada lado del ladrillo es un múltiplo del lado más pequeño más cercano. De Bruijn llama a estos ladrillos armoniosos . Por ejemplo, los ladrillos más utilizados en la construcción en Estados Unidos tienen dimensiones (en pulgadas) y no son armoniosos, en Rusia el estándar de ladrillo es de 250 × 120 × 65 mm, por lo que también son inarmónicos, pero “ Roman bricks ” (a partir del cual se construyeron los edificios en la antigua Roma) tenía dimensiones armoniosas [6] . $2{\frac{1}{4}}\veces 4\veces 8$ ${\ estilo de visualización 2 \ veces 4 \ veces 12}$

El teorema de De Bruijn establece que si un ladrillo armonioso se empaqueta en una caja, entonces la caja debe ser un múltiplo del ladrillo. Por ejemplo, los ladrillos armoniosos tridimensionales con longitudes de lado 1, 2 y 6 solo se pueden empaquetar en cajas en las que uno de los tres lados sea múltiplo de seis y uno de los otros dos tenga una longitud par [1] [7] . Empacar ladrillos armoniosos en una caja puede usar copias de ladrillos con un giro. Sea como fuere, el teorema establece que incluso si existe tal empaquetamiento, debe existir un empaquetamiento con traslaciones paralelas del ladrillo.

En 1995, se dio una prueba alternativa del caso tridimensional del teorema de de Bruijn usando el álgebra de polinomios [8] .

Ladrillos inarmónicos

El tercer resultado de Brain es que si un ladrillo no es armonioso, entonces existe una caja que no es un múltiplo de un ladrillo y se puede llenar con el ladrillo dado. Empaquetar un ladrillo en una caja es un ejemplo de esto [1] . En el caso bidimensional, el tercer resultado de de Bruijn es fácil de mostrar. Tamaño de caja y fácil de empacar usando copias de ladrillo con dimensiones apiladas de lado a lado. Por lo mismo, una caja con dimensiones y además fácil de empaquetar con copias del mismo ladrillo. Girando una de estas dos cajas para que sus lados largos queden paralelos y colocando estas dos cajas una al lado de la otra, obtenemos un paquete de ladrillos en una caja más grande con dimensiones y . Esta caja grande es un múltiplo del ladrillo si y solo entonces el ladrillo es armonioso. ${\ estilo de visualización 2 \ veces 3}$ ${\ estilo de visualización 5 \ veces 6}$ $A_{1}=a_{1}$ $A_{2}=a_{1}a_{2}$ $un_{1}$ ${\displaystyle a_{1},a_{2))$ ${\displaystyle A_{1}=a_{1}a_{2))$ $A_{2}=a_{2}$ $A_{1}=a_{1}+a_{2}$ $A_{2}=a_{1}a_{2}$

Notas

↑ 1 2 3 4 5 de Bruijn, 1969 , p. 37–40.
↑ Honsberger, 1976 , pág. 69.
↑ Nienhuys, 2011 , pág. 156.
↑ Watkins, 2012 .
↑ de Bruijn, 1969 .
↑ Kreh, 2003 , pág. Dieciocho.
↑ Stein, Szabó, 1994 , p. 52.
↑ Boisen, 1995 , pág. 285–287.

Literatura

NG de Bruijn. Llenando cajas con ladrillos // The American Mathematical Monthly. - 1969. - T. 76 . — Pág. 37–40 . -doi : 10.2307/ 2316785 .
Ross Honsberger. Gemas Matemáticas II. - Washington, DC: Asociación Matemática de América, 1976. - Pág. 69 . — ISBN 9780883853009 .
JW Nienhuys. La combinatoria de De Bruijn: notas de clase . - 2011. - S. 156.
John J. Watkins. A través del tablero: las matemáticas de los problemas del tablero de ajedrez . - Princeton University Press, 2012. - Pág. 226. - ISBN 9781400840922 .
RT Kreh. Habilidades de albañilería . — 5to. - Cengage Learning, 2003. - Pág. 18. - ISBN 9780766859364 .
Sherman K. Stein, Sandor Szabo. Álgebra y Mosaico: Homomorfismos al Servicio de la Geometría . - Washington, DC: Asociación Matemática de América, 1994. - V. 25. - P. 52. - (Monografías Matemáticas de Carus). - ISBN 0-88385-028-1 .
Pablo Boysen. Polinomios y empaquetamientos: una nueva demostración del teorema de de Bruijn // Matemáticas discretas . - 1995. - T. 146 , núm. 1-3 . — S. 285–287 . - doi : 10.1016/0012-365X(94)00070-1 .

Enlaces

Weisstein, Eric W. de Bruijn's Theorem (inglés) en el sitio web de Wolfram MathWorld .