De Bruijns teorem

De Bruijns teorem är ett resultat av kombinatorisk geometri , enligt vilken rektangulära block (av valfri dimension) där längden på varje sida är en multipel av nästa mindre sidolängd ("harmoniska tegelstenar") endast kan packas i ett rektangulärt block ("låda"), storleken på vars sidor är en multipel av tegelstenens sidor.

Etablerat och publicerat 1969 av den holländska matematikern Nicholas de Bruijn i en artikel, tillsammans med andra resultat om packning av kongruenta rektangulära block - tegelstenar i stora rektangulära block - lådor, så att det inte finns något tomt utrymme [1] .

Exempel

De Bruijn bevisade detta påstående efter att hans sjuåriga son misslyckades med att passa storleksblock i en kub [2] [3] . Kuben hade en volym lika med volymen av block, men bara block kan placeras i den. För att förstå detta, låt oss dela upp kuben i mindre kuber, färgade växelvis i vitt och svart, och notera att en sådan partition har fler enhetskuber (celler) av en färg än en annan, medan varje packning av block till en kub måste ha lika antal celler i varje färg [4] . De Bruijns teorem bevisar att en perfekt packning med sådana sidolängder är omöjlig. Teoremet gäller andra storlekar av tegelstenar och lådor. $1\times 2\times 4$ $6\times 6\times 6$ $27$ $26$ $27$ $1\times 2\times 4$

Rutor som är multiplar av block

Antag att en dimensionell rektangulär låda (i matematiska termer, en kuboid ) har heltals sidolängder , och tegelstenarna har sidolängder . Om längden på sidorna av en tegelsten kan multipliceras med heltal och resultatet av multiplikationen är en permutation av siffrorna , sägs rutan vara en multipel av tegelstenen. Lådan kan sedan fyllas med sådana tegelstenar på ett trivialt sätt med samma orientering av tegelstenarna [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},\dots a_{d}b_{d))$ ${\displaystyle A_{1},A_{2},\dots ,A_{d))$

Generalisering

Inte för varje paket, lådan måste nödvändigtvis vara en multipel av en tegelsten. Till exempel, som de Bruijn noterade, kan en rektangulär låda fyllas med kopior av rektangulära tegelstenar, men inte alla tegelstenar kommer att vara lika orienterade. Men de Bruijn [5] bevisade att om tegelstenar kan fylla en låda, så måste åtminstone en av kvantiteterna vara en multipel av en av sidorna av tegelstenen för varje . I exemplet ovan är lådans sidolängd en multipel av både och [1] . $5\times 6$ $2\times 3$ $a_{i},$ $A_{i}$ $6$ $2$ $3$

Harmoniska tegelstenar

Det andra resultatet av de Bruijn, som kallas de Bruijns teorem, gäller fallet när varje sida av tegelstenen är en multipel av den närmaste mindre sidan. De Bruijn kallar dessa tegelstenar för harmoniska . Till exempel har de vanligaste tegelstenarna i konstruktion i USA dimensioner (i tum) och är inte harmoniska, i Ryssland är tegelstandarden 250 × 120 × 65 mm, så de är också inharmoniska, men " romerska tegelstenar ” (av vilka byggnader byggdes i antikens Rom) hade harmoniska dimensioner [6] . $2{\frac {1}{4}}\times 4\times 8$ $2\times 4\times 12$

De Bruijns teorem säger att om en harmonisk tegelsten packas i en låda, så måste lådan vara en multipel av tegelstenen. Till exempel kan tredimensionella harmoniska tegelstenar med sidolängderna 1, 2 och 6 endast packas i lådor där en av de tre sidorna är en multipel av sex och en av de andra två har en jämn längd [1] [7] . Att packa harmoniska tegelstenar i en låda kan använda kopior av tegelstenar med en tur. Hur som helst, satsen säger att även om en sådan packning existerar så måste det finnas en packning med parallella översättningar av tegelstenen.

1995 gavs ett alternativt bevis på det tredimensionella fallet av de Bruijns sats med hjälp av polynomalgebra [8] .

Disharmoniska tegelstenar

Brains tredje resultat är att om en tegelsten är inharmonisk, så finns det en låda som inte är en multipel av en tegelsten och kan fyllas med den givna tegelstenen. Att packa en tegelsten i en låda ger ett exempel på detta [1] . I det tvådimensionella fallet är de Bruijns tredje resultat lätt att visa. Kartongstorlek och lätt att packa med hjälp av tegelkopior med måtten staplade sida till sida. Av samma anledning en låda med mått och dessutom lätt att packa med kopior av samma tegelsten. Genom att rotera en av dessa två lådor så att deras långsidor blir parallella och placera dessa två lådor sida vid sida får vi ett paket tegelstenar i en större låda med mått och . Denna stora låda är en multipel av tegelstenen om och bara då tegelstenen är harmonisk. $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}$

Anteckningar

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

Litteratur

NG de Bruijn. Fylla lådor med tegelstenar // The American Mathematical Monthly. - 1969. - T. 76 . — S. 37–40 . - doi : 10.2307/2316785 .
Ross Honsberger. Matematiska ädelstenar II. - Washington, DC: Mathematical Association of America, 1976. - s. 69 . — ISBN 9780883853009 .
JW Nienhuys. De Bruijns kombinatorik: klassrumsanteckningar . - 2011. - S. 156.
John J. Watkins. Över hela linjen: The Mathematics of Chessboard Problems . - Princeton University Press, 2012. - S. 226. - ISBN 9781400840922 .
RT Kreh. Murarkunskaper . — 5:a. - Cengage Learning, 2003. - P. 18. - ISBN 9780766859364 .
Sherman K. Stein, Sandor Szabo. Algebra och plattsättning: Homomorfismer i geometrins tjänst . - Washington, DC: Mathematical Association of America, 1994. - V. 25. - S. 52. - (Carus Mathematical Monographs). - ISBN 0-88385-028-1 .
Paul Boysen. Polynom och packningar: ett nytt bevis på de Bruijns teorem // Diskret matematik . - 1995. - T. 146 , nr. 1-3 . — S. 285–287 . - doi : 10.1016/0012-365X(94)00070-1 .

Länkar

Weisstein, Eric W. de Bruijn's Theorem (engelska) på Wolfram MathWorld- webbplatsen .