De Bruijns sætning

De Bruijns sætning er et resultat af kombinatorisk geometri , ifølge hvilken rektangulære blokke (af enhver dimension), hvor længden af hver side er et multiplum af den næste mindre sidelængde ("harmoniske mursten") kun kan pakkes ind i en rektangulær blok ("kasse"), hvis sider er et multiplum af murstenens sider.

Etableret og udgivet i 1969 af den hollandske matematiker Nicholas de Bruijn i én artikel, sammen med andre resultater om pakning af kongruente rektangulære blokke - mursten i store rektangulære blokke - kasser, så der ikke er tom plads [1] .

Eksempel

De Bruijn beviste denne påstand, efter at hans syv-årige søn ikke formåede at passe størrelsesblokke ind i en terning [2] [3] . Terningen havde et volumen svarende til volumenet af blokke, men kun blokke kan placeres i den. For at forstå dette, lad os opdele terningen i mindre terninger, farvet skiftevis i hvid og sort, og bemærke, at en sådan partition har flere enhedsterninger (celler) af en farve end en anden, mens enhver pakning af blokke i en terning skal have en lig antal celler af hver farve [4] . De Bruijns teorem beviser, at en perfekt pakning med sådanne sidelængder er umulig. Sætningen gælder for andre størrelser af mursten og kasser. $1\ gange 2\ gange 4$ $6\ gange 6\ gange 6$ $27$ $26$ $27$ $1\ gange 2\ gange 4$

Bokse, der er multipla af blokke

Antag, at en dimensionel rektangulær kasse (i matematiske termer, en cuboid ) har heltal sidelængder , og klodserne har sidelængder . Hvis længderne af siderne af en mursten kan ganges med heltal , og resultatet af multiplikationen er en permutation af tallene , siges boksen at være et multiplum af murstenen. Kassen kan derefter fyldes med sådanne klodser på en triviel måde med samme orientering af klodserne [1] . $d$ ${\displaystyle A_{1}\times A_{2}\times \dots \times A_{d))$ ${\displaystyle a_{1}\times a_{2}\times \dots \times a_{d))$ $b_{i}$ ${\displaystyle a_{1}b_{1},a_{2}b_{2},\dots a_{d}b_{d))$ ${\displaystyle A_{1},A_{2},\dots ,A_{d))$

Generalisering

Ikke for hver pakke skal æsken nødvendigvis være et multiplum af en klods. For eksempel, som de Bruijn bemærkede, kan en rektangulær kasse fyldes med kopier af rektangulære klodser, men ikke alle klodser vil være lige orienterede. Imidlertid beviste de Bruijn [5] , at hvis mursten kan fylde en kasse, så skal mindst en af mængderne for hver af dem være et multiplum af en af siderne af murstenen. I ovenstående eksempel er boksens sidelængde et multiplum af både og [1] . $5\ gange 6$ $2\ gange 3$ $a_{i},$ $A_{i}$ $6$ $2$ $3$

Harmoniske mursten

Det andet resultat af de Bruijn, som kaldes de Bruijns sætning, vedrører det tilfælde, hvor hver side af murstenen er et multiplum af den nærmeste mindre side. De Bruijn kalder disse klodser for harmoniske . For eksempel har de mest almindeligt anvendte mursten i byggeriet i USA dimensioner (i tommer) og er ikke harmoniske, i Rusland er murstensstandarden 250 × 120 × 65 mm, så de er også uharmoniske, men " romerske mursten ” (hvorfra der blev bygget bygninger i det gamle Rom) havde harmoniske dimensioner [6] . $2{\frac {1}{4}}\ gange 4\ gange 8$ $2\ gange 4\ gange 12$

De Bruijns sætning siger, at hvis en harmonisk mursten er pakket ind i en kasse, så skal kassen være et multiplum af murstenen. For eksempel kan tredimensionelle harmoniske klodser med sidelængder 1, 2 og 6 kun pakkes i kasser, hvor en af de tre sider er et multiplum af seks og en af de to andre har en lige længde [1] [7] . Pakning af harmoniske mursten i en kasse kan bruge kopier af mursten med en tur. Hvorom alting er, siger sætningen, at selvom en sådan pakning eksisterer, skal der eksistere en pakning med parallelle oversættelser af murstenen.

I 1995 blev et alternativt bevis for det tredimensionelle tilfælde af de Bruijns sætning givet ved hjælp af polynomiers algebra [8] .

Disharmoniske mursten

Brains tredje resultat er, at hvis en klods er uharmonisk, så eksisterer der en kasse, der ikke er et multiplum af en klods og kan fyldes med den givne klods. At pakke en mursten ind i en kasse giver et eksempel på dette [1] . I det todimensionelle tilfælde er de Bruijns tredje resultat let at vise. Æskestørrelse og nem at pakke ved hjælp af murstenskopier med dimensioner stablet side til side. Af samme grund en kasse med dimensioner og også nem at pakke med kopier af samme klods. Drejer vi en af disse to kasser, så deres lange sider bliver parallelle og placerer disse to kasser side om side, får vi en pakke klodser i en større kasse med dimensioner og . Denne store kasse er et multiplum af murstenen, hvis og kun da murstenen er harmonisk. $2\ gange 3$ $5\ gange 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}$

Noter

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

Litteratur

NG de Bruijn. Fyldning af kasser med mursten // The American Mathematical Monthly. - 1969. - T. 76 . — S. 37–40 . - doi : 10.2307/2316785 .
Ross Honsberger. Matematiske ædelstene II. - Washington, DC: Mathematical Association of America, 1976. - s. 69 . — ISBN 9780883853009 .
JW Nienhuys. De Bruijns kombinatorik: klasseværelsesnotater . - 2011. - S. 156.
John J. Watkins. Over hele linjen: Matematikken i skakbrætproblemer . - Princeton University Press, 2012. - S. 226. - ISBN 9781400840922 .
RT Kreh. Murerfærdigheder . — 5. - Cengage Learning, 2003. - S. 18. - ISBN 9780766859364 .
Sherman K. Stein, Sandor Szabo. Algebra og fliselægning: Homomorfismer i geometriens tjeneste . - Washington, DC: Mathematical Association of America, 1994. - V. 25. - S. 52. - (Carus Mathematical Monographs). - ISBN 0-88385-028-1 .
Paul Boysen. Polynomier og pakninger: et nyt bevis på de Bruijns sætning // Diskret matematik . - 1995. - T. 146 , no. 1-3 . — S. 285–287 . - doi : 10.1016/0012-365X(94)00070-1 .