De Bruijn tétele

De Bruijn tétele a kombinatorikus geometria eredménye , amely szerint az olyan (bármilyen méretű) téglalap alakú blokkok, amelyekben mindkét oldal hossza többszöröse a következő kisebb oldalhossznak ("harmonikus téglák") csak téglalap alakú blokkba csomagolható. ("doboz"), amelynek oldalainak mérete a tégla oldalainak többszöröse.

1969 -ben alapította és publikálta Nicholas de Bruijn holland matematikus egy cikkben, más eredményekkel együtt az egybevágó téglalap alakú tömbök – téglák – nagy téglalap alakú tömbökbe – dobozokba való csomagolásáról, hogy ne maradjon üres hely [1] .

Példa

De Bruijn bebizonyította ezt az állítást, miután hétéves fiának nem sikerült méretű blokkokat egy kockába illesztenie [2] [3] . A kocka térfogata megegyezett a blokkok térfogatával, de csak blokkok helyezhetők el benne. Ennek megértéséhez osszuk fel a kockát kisebb, felváltva fehérre és feketére színezett kockákra, és vegyük észre, hogy egy ilyen partíciónak több az egyik színű egységkockája (cellája) van, mint a másiknak, míg a kockák kockába történő becsomagolásánál egyenlőnek kell lennie. az egyes színek celláinak száma [4] . De Bruijn tétele bizonyítja, hogy ilyen oldalhosszúságokkal tökéletes tömítés lehetetlen. A tétel más méretű téglákra és dobozokra is vonatkozik. $1\times 2\times 4$ $6\times 6\times 6$ $27$ $26$ $27$ $1\times 2\times 4$

A blokkok többszöröseiből álló dobozok

Tételezzük fel, hogy egy dimenziós téglalap alakú doboz (matematikai értelemben egy téglatest ) egész oldalhosszúságú , a téglák oldalhossza pedig . Ha egy tégla oldalainak hossza megszorozható egész számokkal , és a szorzás eredménye a számok permutációja , akkor a dobozt a tégla többszörösének mondjuk. A dobozt ezután triviális módon, a téglák azonos tájolásával lehet megtölteni ilyen téglákkal [1] . $d$ ${\displaystyle A_{1}\times A_{2}\times \dots \times A_{d))$ ${\displaystyle a_{1}\times a_{2}\times \dots \times a_{d))$ $kettős}$ ${\displaystyle a_{1}b_{1},a_{2}b_{2},\dots a_{d}b_{d))$ ${\displaystyle A_{1},A_{2},\dots ,A_{d))$

Általánosítás

Nem minden csomagnál, a doboznak feltétlenül egy tégla többszörösének kell lennie. Például, ahogy de Bruijn megjegyezte, egy téglalap alakú dobozt meg lehet tölteni téglalap alakú téglák másolataival, de nem minden tégla egyformán orientált. De Bruijn [5] azonban bebizonyította, hogy ha a téglák kitölthetnek egy dobozt, akkor minden egyes mennyiségnél legalább egy mennyiségnek a tégla egyik oldalának többszörösének kell lennie. A fenti példában a doboz oldalhossza mindkettő és [1] többszöröse . $5\times 6$ $2\times 3$ $a_{i},$ $A_{i}$ $6$ $2$ $3$

Harmonious Bricks

De Bruijn második eredménye, amelyet de Bruijn tételének neveznek, arra az esetre vonatkozik, amikor a tégla mindkét oldala a legközelebbi kisebb oldal többszöröse. De Bruijn ezeket a téglákat harmonikusnak nevezi . Például az Egyesült Államokban az építőiparban leggyakrabban használt téglák méretei (hüvelykben) vannak, és nem harmonikusak, Oroszországban a tégla szabvány 250 × 120 × 65 mm, tehát szintén inharmonikusak, de „ római tégla ” (amelyből az ókori Rómában épületek épültek) harmonikus méretei voltak [6] . $2{\frac {1}{4}}\times 4\times 8$ $2\times 4\times 12$

De Bruijn tétele kimondja, hogy ha egy harmonikus téglát csomagolunk egy dobozba, akkor a doboznak a tégla többszörösének kell lennie. Például az 1, 2 és 6 oldalhosszúságú, háromdimenziós harmonikus téglákat csak olyan dobozokba lehet csomagolni, ahol a három oldal egyike a hatos többszöröse, a másik kettő közül pedig egy páros hosszúságú [1] [7] . Harmonikus téglák dobozba csomagolásakor használhatjuk a téglák másolatait egy fordulattal. Bárhogy is legyen, a tétel kimondja, hogy még ha létezik is ilyen tömítés, léteznie kell egy tömítésnek a tégla párhuzamos fordításaival.

1995-ben megadták a de Bruijn-tétel háromdimenziós esetének alternatív bizonyítását a polinomok algebrájával [8] .

Disharmonious bricks

Brain harmadik eredménye, hogy ha egy tégla inharmonikus, akkor létezik olyan doboz, amely nem többszöröse a téglának, és az adott téglával megtölthető. Egy tégla dobozba csomagolása ad erre egy példát [1] . A kétdimenziós esetben de Bruijn harmadik eredménye könnyen kimutatható. Doboz méretű és könnyen becsomagolható tégla másolatok segítségével, egymásra rakott méretekkel. Ugyanebből az okból kifolyólag egy doboz méretekkel és könnyen csomagolható ugyanazon tégla másolataival. E két doboz egyikét úgy elforgatva, hogy a hosszú oldaluk párhuzamos legyen, és ezt a két dobozt egymás mellé helyezve, egy csomag téglát kapunk egy nagyobb, és méretű dobozban . Ez a nagy doboz akkor és csak akkor a tégla többszöröse a tégla harmonikus. $2\times 3$ $5\times 6$ $A_{1}=a_{1}$ $A_{2}=a_{1}a_{2}$ $a_{1}$ ${\displaystyle a_{1},a_{2))$ $A_{1}=a_{1}a_{2}$ $A_{2}=a_{2}$ $A_{1}=a_{1}+a_{2}$ $A_{2}=a_{1}a_{2}$

Jegyzetek

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

Irodalom

NG de Bruijn. Dobozok kitöltése téglával // The American Mathematical Monthly. - 1969. - T. 76 . – S. 37–40 . - doi : 10.2307/2316785 .
Ross Honsberger. Matematikai drágakövek II. - Washington, DC: Mathematical Association of America, 1976. - 69. o . — ISBN 9780883853009 .
JW Nienhuys. De Bruijn kombinatorikája: tantermi jegyzetek . - 2011. - S. 156.
John J. Watkins. Az egész fórumon: A sakktábla-feladatok matematikája . - Princeton University Press, 2012. - P. 226. - ISBN 9781400840922 .
RT Kreh. Kőműves készségek . — 5. - Cengage Learning, 2003. - P. 18. - ISBN 9780766859364 .
Sherman K. Stein, Szabó Sándor. Algebra és csempézés: Homomorfizmusok a geometria szolgálatában . - Washington, DC: Mathematical Association of America, 1994. - V. 25. - P. 52. - (Carus Mathematical Monographs). - ISBN 0-88385-028-1 .
Paul Boysen. Polinomok és pakolások: de Bruijn tételének új bizonyítása // Diszkrét matematika . - 1995. - T. 146 , sz. 1-3 . – S. 285–287 . - doi : 10.1016/0012-365X(94)00070-1 .

Linkek

Weisstein, Eric W. de Bruijn tétele (angolul) a Wolfram MathWorld webhelyen .