De Bruijnin lause

De Bruijnin lause on tulosta kombinatorisesta geometriasta , jonka mukaan suorakaiteen muotoiset lohkot (mikä tahansa mitat), joissa kunkin sivun pituus on seuraavan pienemmän sivupituuden kerrannainen ("harmoniset tiilet"), voidaan pakata vain suorakaiteen muotoiseen lohkoon. ("laatikko"), jonka sivujen koko on tiilen sivujen kerrannainen.

Perusti ja julkaisi vuonna 1969 hollantilainen matemaatikko Nicholas de Bruijn yhdessä artikkelissa, sekä muita tuloksia yhtenäisten suorakaiteen muotoisten lohkojen pakkaamisesta suuriin suorakaiteen muotoisiin laatikoihin, jotta tyhjää tilaa ei ole [1] .

Esimerkki

De Bruijn osoitti tämän väitteen sen jälkeen, kun hänen seitsenvuotias poikansa ei onnistunut sovittamaan kokolohkoja kuutioon [2] [3] . Kuution tilavuus oli yhtä suuri kuin lohkojen tilavuus, mutta siihen voidaan sijoittaa vain lohkoja. Tämän ymmärtämiseksi jaetaan kuutio pienempiin kuutioihin, jotka on värjätty vuorotellen valkoiseksi ja mustaksi, ja huomioidaan, että tällaisessa osiossa on enemmän yhden värisiä yksikkökuutioita (soluja) kuin toista, kun taas minkä tahansa lohkojen pakkaamisen kuutioon on oltava yhtä suuri. kunkin värin solujen lukumäärä [4] . De Bruijnin lause osoittaa, että täydellinen tiivistys sellaisilla sivupituuksilla on mahdotonta. Lause pätee muun kokoisiin tiileihin ja laatikoihin. ${\näyttötyyli 1\kertaa 2\kertaa 4}$ ${\näyttötyyli 6\kertaa 6\kertaa 6}$ $27$ $26$ $27$ ${\näyttötyyli 1\kertaa 2\kertaa 4}$

Laatikot, jotka ovat lohkojen kerrannaisia

Oletetaan, että -ulotteisella suorakaiteen muotoisella laatikolla (matematiikan termein kuutiolla ) on kokonaislukujen sivujen pituudet ja tiilillä on sivujen pituudet . Jos tiilen sivujen pituudet voidaan kertoa kokonaisluvuilla ja kertolasku on lukujen permutaatio , laatikon sanotaan olevan tiilen kerrannainen . Laatikko voidaan sitten täyttää tällaisilla tiileillä triviaalilla tavalla samalla tiilien suunnalla [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))$

Yleistys

Ei jokaisessa paketissa, laatikon on välttämättä oltava tiilen monikerta. Esimerkiksi, kuten de Bruijn totesi, suorakaiteen muotoinen laatikko voidaan täyttää kopioilla suorakaiteen muotoisista tiileistä, mutta kaikki tiilet eivät ole yhtä suunnattuja. De Bruijn [5] osoitti kuitenkin, että jos tiilet voivat täyttää laatikon, niin jokaiselle vähintään yhden määristä on oltava tiilen yhden sivun kerrannainen. Yllä olevassa esimerkissä laatikon sivun pituus on molempien ja [1] :n kerrannainen . ${\näyttötyyli 5\kertaa 6}$ ${\näyttötyyli 2\kertaa 3}$ $a_{i},$ $A_{i}$ $6$ $2$ $3$

Harmonious Bricks

Toinen de Bruijnin tulos, jota kutsutaan de Bruijnin lauseeksi, koskee tapausta, jossa tiilen kumpikin puoli on lähimmän pienemmän sivun kerrannainen. De Bruijn kutsuu näitä tiiliä harmonisiksi . Esimerkiksi Yhdysvalloissa yleisimmin käytetyt tiilet rakentamisessa ovat mitoiltaan (tuumina) eivätkä ole harmonisia, Venäjällä tiilistandardi on 250 × 120 × 65 mm, joten ne ovat myös epäharmonisia, mutta " Roomalaiset tiilet ” (josta rakennettiin rakennuksia muinaisessa Roomassa) oli harmoniset mitat [6] . $2{\frac {1}{4}}\times 4\times 8$ ${\näyttötyyli 2\kertaa 4\kertaa 12}$

De Bruijnin lause sanoo, että jos harmoninen tiili pakataan laatikkoon, laatikon on oltava tiilen kerrannainen. Esimerkiksi kolmiulotteiset harmoniset tiilet, joiden sivupituudet ovat 1, 2 ja 6, voidaan pakata vain laatikoihin, joissa yksi kolmesta sivusta on kuuden kerrannainen ja toinen kahdesta muusta on tasapituinen [1] [7] . Harmonisten tiilien pakkaaminen laatikkoon voi käyttää tiilikopioita käänteisesti. Oli miten oli, lause sanoo, että vaikka tällainen tiiviste on olemassa, täytyy olla tiiviste, jossa on rinnakkaiset tiilen käännökset.

Vuonna 1995 annettiin vaihtoehtoinen todistus de Bruijnin lauseen kolmiulotteiselle tapaukselle käyttämällä polynomien algebraa [8] .

Epäharmoniset tiilet

Brainin kolmas tulos on, että jos tiili on epäharmoninen, niin on olemassa laatikko, joka ei ole tiilen kerrannainen ja joka voidaan täyttää annetulla tiilellä. Tiilen pakkaaminen laatikkoon antaa tästä esimerkin [1] . Kaksiulotteisessa tapauksessa de Bruijnin kolmas tulos on helppo näyttää. Laatikon kokoinen ja helppo pakata käyttämällä tiilikopioita, joiden mitat on pinottu sivuttain. Samasta syystä laatikko, jolla on mitat ja myös helppo pakata kopioiden kanssa samasta tiilestä. Kääntämällä toista näistä kahdesta laatikosta niin, että niiden pitkät sivut tulevat yhdensuuntaisiksi ja asettamalla nämä kaksi laatikkoa vierekkäin, saadaan tiilipakkaus suurempaan laatikkoon, jonka mitat ovat ja . Tämä suuri laatikko on tiilen monikerta, jos ja vain silloin tiili on harmoninen. ${\näyttötyyli 2\kertaa 3}$ ${\näyttötyyli 5\kertaa 6}$ $A_{1}=a_{1}$ $A_{2}=a_{1}a_{2}$ $a_{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}$

Muistiinpanot

↑ 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. kahdeksantoista.
↑ Stein, Szabó, 1994 , s. 52.
↑ Boisen, 1995 , s. 285-287.

Kirjallisuus

NG de Bruijn. Laatioiden täyttäminen tiileillä // The American Mathematical Monthly. - 1969. - T. 76 . - S. 37-40 . - doi : 10.2307/2316785 .
Ross Honsberger. Matemaattiset helmet II. - Washington, DC: Mathematical Association of America, 1976. - s. 69 . — ISBN 9780883853009 .
JW Nienhuys. De Bruijnin kombinatoriikka: luokkahuoneen muistiinpanot . - 2011. - S. 156.
John J. Watkins. Kaiken kaikkiaan: Shakkilautaongelmien matematiikka . - Princeton University Press, 2012. - S. 226. - ISBN 9781400840922 .
RT Kreh. Muuraustaidot . – 5. - Cengage Learning, 2003. - S. 18. - ISBN 9780766859364 .
Sherman K. Stein, Sandor Szabo. Algebra ja laatoitus: Homomorfismit geometrian palveluksessa . - Washington, DC: Mathematical Association of America, 1994. - V. 25. - S. 52. - (Carus Mathematical Monographs). - ISBN 0-88385-028-1 .
Paul Boysen. Polynomit ja pakkaukset: uusi todiste de Bruijnin lauseesta // Diskreetti matematiikka . - 1995. - T. 146 , no. 1-3 . — S. 285–287 . - doi : 10.1016/0012-365X(94)00070-1 .

Linkit

Weisstein, Eric W. de Bruijnin lause (englanniksi) Wolfram MathWorld -verkkosivustolla .