Dirichlet-periaate (kombinatoriikka)

Dirichlet-periaate on yksinkertainen, intuitiivinen ja usein hyödyllinen menetelmä äärellisten joukkovaatimusten todistamiseen . Tätä periaatetta käytetään usein diskreetissä matematiikassa , jossa se muodostaa yhteyden esineiden ("kanit") ja säiliöiden ("solut") välille tietyissä olosuhteissa [1] . Englannissa ja joissakin muissa kielissä tämä väite tunnetaan nimellä pigeonhole-periaate , kun esineet ovat kyyhkysiä ja säiliöt laatikoita [ 2] .

Yleisin on Dirichlet-periaatteen [3] yksinkertaisin muotoilu :

Jos kanit istuvat häkeissä ja kaneja on enemmän kuin häkkien lukumäärä, vähintään yhdessä häkeissä on useampi kuin yksi kani.

Sille on myös yleinen ilmaus:

Jos solujen lukumäärä on suurempi kuin kanien lukumäärä, vähintään yksi solu on tyhjä.

Muita yleisempiä formulaatioita, katso alla .

Historioitsijat löysivät tämän periaatteen ensimmäisen muotoilun suositusta kokoelmasta Récréations Mathématiques ( ranskalainen Récréations Mathématiques , 1624, nimellä H. van Etten ), jonka julkaisi (oletettavasti) ranskalainen matemaatikko Jean Leurechon [4] . Tämä periaate tuli laajalle levinneeksi sen jälkeen, kun Dirichlet (vuodesta 1834) soveltaa sitä lukuteorian alalla [5] .

Dirichlet'n periaatetta sovelletaan muodossa tai toisessa menestyksekkäästi lauseiden todistuksessa, mikä tekee näistä todisteista yksinkertaisempia ja selkeämpiä. Sen sovellusalueita ovat diskreetti [6]jne.ratkaistavuuden analyysi, lineaaristen epäyhtälöiden järjestelmien diofantinisten approksimaatioidenmatematiikka, [3] .

Muu sanamuoto

Todiste

Dirichlet'n periaate yksinkertaisimmassa formulaatiossa: " jos kanien lukumäärä on suurempi kuin solujen lukumäärä, niin ainakin yksi soluista sisältää useamman kuin yhden kanin " voidaan todistaa "ristiriitaisesti" -menetelmällä . Olkoon lisäksi häkkejä ja kaneja . Merkitse. kanien lukumäärä -: nnessä solussa ( ). Oletetaan, että jokaisessa häkissä on enintään yksi kani: $n$ $m$ $m>n$ $k_i$ $i$ $i=1,2,\pisteet n$

$k_{1}\leqslant 1$ (kanien lukumäärä ensimmäisessä häkissä on pienempi tai yhtä suuri kuin 1);
$k_{2}\leqslant 1$ (kanien lukumäärä toisessa häkissä on pienempi tai yhtä suuri kuin 1);
...
$k_{n}\leqslant 1$ (kanien lukumäärä -. solussa on pienempi tai yhtä suuri kuin 1). $n$

Sitten kanien kokonaismäärä siis Mutta ongelman tilan mukaan . Tuli ristiriita, ■ . $m=k_{1}+k_{2}+\ldots +k_{n}\leqslant 1+1+\ldots +1=n.$ $m\leqslant n$ $m>n$

Parilauseke todistetaan samalla tavalla: " jos solujen määrä on suurempi kuin kanien lukumäärä, niin ainakin yksi solu on tyhjä ."

Edellä olevien kahden formulaation lisäksi on kaksi muuta hyödyllistä, jotka on myös helposti todistettavissa [7] :

Jos kanit istuvat häkeissä, eikä tyhjiä häkkejä ole, kussakin häkissä on tasan yksi kani. $n$ $n$
Jos kanit sijoitetaan häkkeihin, eikä missään häkissä ole enemmän kuin yksi kani, jokaisessa häkissä on täsmälleen yksi kani. $n$ $n$

Vaihtoehdot yleisemmille formulaatioille [8] :

Kun jakelu tai useampia tuotteita laatikoissa on, missä tahansa laatikossa on vähintään yksi tuote. $kn+1$ $n$ $k+1$
Jos kanit istutetaan häkeissä, vähintään yhdessä häkissä on vähintään kaneja ja vähintään yhdessä häkissä enintään kaneja. Tässä Iversonin kulmat ja pyöristää niihin sisältyvä ilmaisu kokonaisuudeksi, vastaavasti ylös ja alas. $m$ $n$ $\left\lceil {\frac {m}{n}}\right\rceil$ $\left\lfloor {\frac {m}{n}}\right\rfloor$ $\lceil \dots \rceil$ $\lfloor \dots \rfloor$
Olkoon äärelliselle joukolle määritelty ja sen kuvaaminen äärelliseen joukkoon määritetty funktio : jossa on jokin luonnollinen luku ja muodon konstruktio tarkoittaa äärellisen joukon alkioiden lukumäärää ( joukon kardinaliteetti ). Tällöin funktio saa jonkin arvon ainakin kerran. $f,$ $A$ $B$ $f\colon A\rightarrow B,$ $\left|A\right|>n\cdot \left|B\right|,$ $n$ $\left|X\right|$ $X$ $f$ $n+1$

Sovellusesimerkkejä

Lause 1 . Jokaisessa yksikköneliön sisällä olevan viiden pisteen valinnassa on pistepari, jotka eroavat toisistaan enintään ${\frac {\sqrt {2}}{2}}.$

Todiste . Lause näyttää ensi silmäyksellä monimutkaiselta ja epäilmiseltä, mutta Dirichlet-periaatteen avulla se todistetaan vaivattomasti [9] . Jaa neliö 4 neljään osaan kuvan osoittamalla tavalla. Dirichlet-periaatteen mukaan vähintään kaksi viidestä valitusta pisteestä putoaa yhteen neljännekseen, jolloin niiden välinen etäisyys on enintään neljänneksen diagonaali, joka on yhtä suuri kuin ■ ${\sqrt {{\left({\frac {1}{2}}\right)}^{2}+{\left({\frac {1}{2}}\right)}^{ 2}}}={\frac {\sqrt {2}}{2}}.$

Lause 2 . Osa ihmisistä kättelee. Todista, että yrityksessä on vähintään kaksi henkilöä, jotka ovat tehneet saman määrän kättelyjä [10] . $N$ $\left(N>1\right)$

Todiste . Anna - "laatikot". Laitetaan laatikkoon ne seuran jäsenet, jotka kättelivät. Jos laatikko ei ole tyhjä, niin yksi tai useampi yrityksen jäsen ei ole tehnyt yhtään kädenpuristusta, ja siksi laatikko on silloin tyhjä, koska kädenpuristusten määrä on silloin pienempi . Tästä seuraa, että ei-tyhjiä on aina vähemmän laatikoita kuin ja siten vähintään yksi laatikko vastaa kahta tai useampaa henkilöä. ■ $\{H_{0},H_{1},\dots H_{N-1}\}$ $N$ $H_{k}$ $k$ $H_{0}$ $H_{N-1}$ $N.$ $N,$

Lause 3 . Millä tahansa positiivisella irrationaaliluvulla on äärettömän monta murtolukua , jotka eroavat pienemmästä kuin by (tämä on yksi Dirichlet-lauseen versioista diofantiiniapproksimaatioista ) [11] [12] . $a$ ${\frac {p}{q)),$ $a$ ${\displaystyle {\frac {1}{q^{2))))$

Todiste . Tehdään mielivaltaiselle luonnolliselle luvulle joukko arvoja: $N$ ${\näyttötyyli (N+1)}$

d_{1}=1\cdot a-[1\cdot a],

d_{2}=2\cdot a-[2\cdot a],

d_{3}=3\cdot a-[3\cdot a],

\pisteet,

d_{N+1}=(N+1)\cdot a-[(N+1)\cdot a],

jossa tarkoittaa luvun kokonaislukuosaa .

[x]

Kaikki nämä luvut kuuluvat väliin 0 - 1 mukaan lukien. Jaamme ne laatikoihin: ensimmäiseen laatikkoon laitamme numerot 0:sta ei-inklusiiviseen, toiseen - kattavasta ei-kattavaan jne., th - kattavasta ei-kattavaan. Mutta koska numeroiden lukumäärä on suurempi kuin laatikoiden lukumäärä, niin Dirichlet-periaatteen mukaan yhdessä laatikoista on vähintään kaksi eroa: ja kun $N$ $1/N$ $1/N$ $2/N$ $N$ ${\näyttötyyli (N-1)/N}$ $N/N$ $\left(N+1\right)$ $\left(N\right),$ $d_{i}=\left(i\cdot a-[i\cdot a]\right)$ $d_{j}=\left(j\cdot a-[j\cdot a]\right)$ $i<j.$

Rakennekohtaisten erojen arvot eroavat vähemmän kuin Olettaen ja saamme: ${\frac {1}{N}}:$ $d_{j}-d_{i}<{\frac {1}{N)).$ $q=ji$ $p=[j\cdot a]-[i\cdot a],$

|q\cdot ap|<{\frac {1}{N)),

tai: (koska ).

\left|a-{\frac {p}{q}}\right|<{\frac {1}{q\cdot N}}\leqslant {\frac {1}{q^{2}} }

q\leqslant N

Luvun mielivaltaisuudesta johtuen murto -osan läheisyys lukuun voidaan tehdä mielivaltaisen pieneksi (tässä tapauksessa se on varmasti nollasta poikkeava, koska se on ehdoiltaan irrationaalinen). Siksi yhä läheisempiä approksimaatioita vastaavien murtolukujen määrä on ääretön. ■ $N$ $p/q$ $a$ $a$ ${\frac {p}{q)),$

Lisää esimerkkejä löytyy seuraavista lähteistä.

Artikkeli Kiinan jäännöslause .
N. B. Alfutovan ja A. V. Ustinovin kirja [13] .
Kirja M. Aigner M. ja G. Ziegler [14] .
Kirja A. A. Andreev et al. [15]

Geometriset sovellukset

Geometriassa käytetään useita Dirichlet-periaatteen muunnelmia, jotka liittyvät pituuksiin, pinta-aloihin ja tilavuuksiin [16] .

Jos pituussegmentissä on useita segmenttejä, joiden pituuksien summa on suurempi kuin , niin ainakin kahdella näistä segmenteistä on yhteinen piste. $L$ $L$
Yleistys . Jos pituussegmentissä on useita segmenttejä, joiden pituuksien summa on suurempi kuin , niin ainakin yksi näistä segmenteistä peittää ainakin yhden pisteen . $L$ $kL$ $k+1$
Jos osien pituuksien summa on pienempi kuin , ne eivät voi peittää pituussegmenttiä kokonaan . $L$ $L$
Jos alueen kuvion sisällä on useita lukuja, joiden alueiden summa on suurempi kuin , niin ainakin kahdella niistä on yhteinen piste. $S$ $S$
Jos useiden kuvioiden pinta-alojen summa on pienempi , ne eivät voi kattaa pinta-alalukua . $S$ $S$

Samanlaisia lausuntoja voidaan muotoilla volyymeille.

Esimerkki [17] . Ympyrään, jonka halkaisija on 6, sijoitetaan satunnaisesti useita ympyröitä, joiden halkaisijoiden summa on 50. Osoita, että on olemassa suora, joka leikkaa vähintään yhdeksän näistä ympyröistä.

Todiste . Antaa olla mielivaltainen halkaisija alkuperäisen ympyrän (pituus 6). Projisoidaan kaikki sisäympyrät halkaisijaan . Ulokkeiden pituuksien summa on ilmeisesti yhtä suuri kuin ympyröiden halkaisijoiden summa, eli 50, ja ne peittävät (ei välttämättä kokonaan) halkaisijan . Koska , Dirichlet-periaatteen 2. version mukaan segmentillä AB on piste, joka kuuluu vähintään yhdeksän ympyrän projektioihin. Sitten tämän pisteen läpi kulkeva ja halkaisijaan nähden kohtisuora viiva on vaadittu, se leikkaa kaikki nämä yhdeksän ympyrää. ■ $D$ $D$ $D$ $50>8\cdot D$ $D$

Muunnelmia ja yleistyksiä

Yksi tapa yleistää Dirichlet-periaate laajentaa sen reaalilukuihin [18] .

Jos kanit söivät kilon ruohoa, niin ainakin yksi kani söi vähintään kilon ruohoa. $m$ $n$ $n\over m$

Seuraukset [18] .

Jos lukujen summa on suurempi , vähintään yksi näistä luvuista on suurempi $n$ $S$ ${\frac {S}{n}}.$
Jos useiden lukujen aritmeettinen keskiarvo on suurempi kuin , niin ainakin yksi näistä luvuista on suurempi $A$ $A.$

Dirichlet-periaate on yleistetty äärettömien joukkojen tapaukseen: tehokkaampaa joukkoa ei ruiskuteta vähemmän tehokkaaseen joukkoon [19] .

Esimerkit [19] .

Jos äärettömään joukkoon soluja sisältyy ääretön määrä kyyhkysiä, niin ainakin yksi solu sisältää useamman kuin yhden kyyhkysen. Lisäksi on helppo osoittaa, että ainakin yhdessä solussa on ääretön määrä kyyhkysiä.
Jos lukematon joukko kyyhkysiä sisältyy laskettavaan laatikkosarjaan, vähintään yksi solu sisältää useamman kuin yhden kyyhkysen. Lisäksi voidaan osoittaa, että ainakin yhdessä solussa on lukematon määrä kyyhkysiä.

Yllä oleva yleistys perustuu esimerkiksi Axel Thuen [20] esittämään Siegelin lemman todistukseen .

Joukko Dirichlet-periaatteen moderneja yleistyksiä esitetään artikkelissa Ramsey Theory .

Dirichlet'n todennäköisyysperiaate. Oletetaan, että kanit istuvat satunnaisissa häkeissä ja kanit istuvat satunnaisissa häkeissä samoista häkeistä. Merkitään todennäköisyydellä, että kani ja kani istuu jossain häkissä.

m

k

n

k

p(m,n,k)

Jos joillekin kiinteä , niin .

{\displaystyle m\cdot n>k^{1+\varepsilon ))

\varepsilon > 0

p(m,n,k)\to 1

k\to \infty

Jos joillekin kiinteä , niin .

{\displaystyle m\cdot n<k^{1-\varepsilon ))

\varepsilon > 0

p(m,n,k)\to 0

k\to \infty

Muistiinpanot

↑ Andreev et ai., 1997 , s. 3.
↑ Saksaksi väitettä kutsutaan "laatikkoperiaatteeksi" ( saksaksi: schubfachprinzip )
↑ 1 2 Uspensky, V. A. Esipuhe matematiikkaan [artikkelikokoelma]. - Pietari. : LLC "Kauppa- ja kustantamo Amphora", 2015. - S. 336-338. — 474 s. — (Populaaritiede, nro 12). - ISBN 978-5-367-03606-0 .
↑ Rittaud, Benoît; Heeffer, Albrecht (2014). "Kyyhkynenreikäperiaate, kaksi vuosisataa ennen Dirichletiä" . Matemaattinen tiedustelu . 36 (2):27-29. DOI : 10.1007/s00283-013-9389-1 . HDL : 1854/LU-411526 . MR 3207654 . Arkistoitu alkuperäisestä 2021-12-25 . Haettu 10.10.2021 . Käytöstä poistettu parametri |deadlink=( ohje )
↑ Jeff Miller, Peter Flor, Gunnar Berg, Julio González Cabillon . Pigeonhole-periaate Arkistoitu 12. helmikuuta 2010 Wayback Machinessa // Jeff Miller (toim.) Joidenkin matematiikan sanojen varhaisimmat tunnetut käyttötavat Arkistoitu 4. maaliskuuta 2009 Wayback Machinessa . Sähköinen asiakirja, haettu 11. marraskuuta 2006
↑ Mat. Encyclopedia, 1982 .
↑ Brualdi, Richard A. (2010), Introductory Combinatorics (5. painos), Prentice Hall , s. 70, ISBN 978-0-13-602040-0
↑ Alfutova N. B., Ustinov A. V., 2009 , s. 17.
↑ Rue, Juanjo. Ikuinen vaeltaja // Laskennan taito. Kombinatoriikka ja luettelointi (luku 3). - M .: De Agostini, 2014. - S. 87. - 144 s. — (Matematiikan maailma: 45 nidettä, nide 34). - ISBN 978-5-9774-0729-8 .
↑ foxford .
↑ Duran, Antonio. Numeroiden runous. Hieno ja matematiikka. - M. : De Agostini, 2014. - S. 57. - 160 s. — (Matematiikan maailma: 45 nidettä, nide 27). — ISBN 978-5-9774-0722-9 .
↑ Alfutova N. B., Ustinov A. V., 2009 , s. 19.
↑ Alfutova N. B., Ustinov A. V., 2009 , s. 17-20.
↑ Aigner, Ziegler, 2006 .
↑ Andreev et ai., 1997 .
↑ Andreev et ai., 1997 , s. 13-16.
↑ Andreev et ai., 1997 , s. neljätoista.
↑ 1 2 Andreev et ai., 1997 , s. 16-18.
↑ 12 Francis Su . Pigeonhole-periaate . Haettu 3. lokakuuta 2021. Arkistoitu alkuperäisestä 3. lokakuuta 2021. (määrätön)
↑ ti , A. (1909), Über Annäherungswerte algebraischer Zahlen , Journal für die reine und angewandte Mathematik T. 1909 (135): 284–305, ISSN 0075-4102 , doi : http:// solre . .uni-goettingen.de/purl?PPN243919689_0135 > Arkistoitu 30. lokakuuta 2020 Wayback Machinessa

Kirjallisuus

Aigner M. , Ziegler G. Dirichlet-periaate ja kaksoislaskenta () luku 22) // Todistuksia kirjasta . Paras todiste Eukleideen ajoista nykypäivään. — M .: Mir, 2006. — 256 s. — ISBN 5-03-003690-3 .
Alfutova N. B., Ustinov A. V. Algebra ja lukuteoria. Kokoelma tehtäviä matematiikan kouluille. - 3. painos, Rev. lisää .. - M . : MTSNMO, 2009. - 336 s. - ISBN 978-5-94057-550-4 .
Andreev A. A., Gorelov G. N., Lyulev A. I., Savin A. N. Dirichlet-periaate. Koulutuspainos. - Samara: Pythagoras, 1997. - 21 s. - (A-sarja: Matematiikka. Numero 1).
Glibichuk A. A., Dainyak A. B., Ilyinsky D. G., Kupavsky A. B., Raigorodsky A. M., Skopenkov A. B., Chernov A. A. Diskreetin matematiikan elementit ongelmissa. - M. : MTSNMO, 2016. - S. 12-14. — 174 s. — ISBN 978-5-4439-3024-4 .
Dirichlet-periaate, laatikot // Mathematical Encyclopedia (5 osassa). - M .: Neuvostoliiton tietosanakirja , 1982. - T. 2. - S. 182.
Znak E. I. Kokonaislukuhilojen osiot ja Dirichlet-periaate // Matemaattinen koulutus . - 2015. - Numero. 19 (kolmas sarja) . - S. 241-248 .

Linkit

Boltyansky V. Kuusi jänistä viidessä häkissä // Kvant . - 1977. - nro 2. - S. 17-20, 37, 42.
Bugaenko V. O. Matemaattinen ympyrä. Luokka 9 Oppitunti numero 2. Dirichlet-periaate . Käyttöönottopäivä: 18.11.2020. (määrätön)
Dirichlet-periaate . Haettu: 30.3.2020. (määrätön)

Sanakirjat ja tietosanakirjat	iso kiinalainen Britannica (verkossa)