Dirichlet-elv (kombinatorika)

A Dirichlet-elv egy egyszerű, intuitív és gyakran hasznos módszer a véges halmazok állításainak bizonyítására . Ezt az elvet gyakran használják a diszkrét matematikában , ahol bizonyos feltételek mellett kapcsolatot hoz létre az objektumok ("nyulak") és a konténerek ("cellák") között [1] . Angolul és néhány más nyelven ezt az állítást galamblyuk elvként ismerik , amikor az objektumok galambok, a tartályok pedig dobozok [ 2] .

A legelterjedtebb a Dirichlet-elv [3] legegyszerűbb megfogalmazása :

Ha a nyulak ketrecben ültették, és a nyulak száma nagyobb, mint a ketrecek száma, akkor legalább az egyik ketrecben egynél több nyul van.

Van rá egy közös kifejezés is:

Ha a sejtek száma nagyobb, mint a nyulak száma, akkor legalább egy cella üres.

Egyéb, általánosabb megfogalmazásokért lásd alább .

Ennek az elvnek az első megfogalmazását a történészek a Récréations Mathématiques ( francia Récréations Mathématiques , 1624, H. van Etten néven ) című népszerű gyűjteményben találták meg, amelyet (feltehetően) Jean Leurechon francia matematikus [4] adott ki . Ez az elv azután vált széles körben elterjedtté, hogy Dirichlet (1834-től) alkalmazta a számelmélet területén [5] .

A Dirichlet-elvet ilyen vagy olyan formában sikeresen alkalmazzák a tételek bizonyításában, egyszerűbbé és világosabbá téve ezeket a bizonyításokat. Alkalmazási területei közé tartozik a diszkrét [6]stb.megoldhatóságának elemzésea lineáris egyenlőtlenség-rendszerek diofantinuszi közelítésekmatematika, a [3] .

Egyéb megfogalmazás

Bizonyíték

Dirichlet elve a legegyszerűbb megfogalmazásban: " ha a nyulak száma nagyobb, mint a sejtek száma, akkor legalább az egyik sejt egynél több nyulat tartalmaz " az "ellentmondásos" módszerrel igazolható . Legyenek ketrecek és nyulak ráadásul . Jelöli. a nyulak száma a -edik cellában ( ). Tegyük fel, hogy minden ketrecben legfeljebb egy nyúl van: $n$ $m$ $m>n$ $k_i$ $én$ $i=1,2,\pontok n$

$k_{1}\leqslant 1$ (az 1. ketrecben lévő nyulak száma legfeljebb 1);
$k_{2}\leqslant 1$ (a 2. ketrecben lévő nyulak száma kisebb vagy egyenlő, mint 1);
...
$k_{n}\leqslant 1$ (a nyulak száma a -edik cellában kisebb vagy egyenlő, mint 1). $n$

Ezután a nyulak teljes száma Így De a probléma állapotától függően . Van egy ellentmondás, ■ . $m=k_{1}+k_{2}+\ldots +k_{n}\leqslant 1+1+\ldots +1=n.$ $m\leqslant n$ $m>n$

Hasonlóképpen igazolódik a pár állítás: " ha a cellák száma nagyobb, mint a nyulak száma, akkor legalább egy cella üres ."

A fenti két megfogalmazáson kívül van még két hasznos, könnyen bizonyítható [7] :

Ha a nyulak ketrecben ülnek , és nincs üres ketrec, akkor minden ketrecben pontosan egy nyúl van. $n$ $n$
Ha a nyulakat ketrecbe helyezik , és egy ketrecben sem található egynél több nyúl, akkor minden ketrecben pontosan egy nyúl van. $n$ $n$

Az általánosabb megfogalmazások lehetőségei [8] :

Bármilyen kiosztással vagy több dobozban lévő tétellel , minden dobozban nem lesz kevesebb, mint egy tétel. $kn+1$ $n$ $k+1$
Ha a nyulakat ketrecben ültetik, akkor legalább egy ketrecben legalább nyul van , és legalább egy ketrecben legfeljebb nyul található . Itt Iverson sarkai és a bennük lévő kifejezés egészére kerekítve, felfelé és lefelé. $m$ $n$ $\left\lceil {\frac {m}{n}}\right\rceil$ $\left\lfloor {\frac {m}{n}}\right\rfloor$ $\lceil \dots \rceil$ $\lfloor \dots \rfloor$
Legyen adott egy véges halmazra definiált és azt véges halmazra leképező függvény : ahol valamilyen természetes szám , a forma konstrukciója pedig a véges halmaz elemeinek számát ( a halmaz számosságát ) jelenti. Ekkor a függvény legalább egyszer felvesz valamilyen értéket. $f,$ $A$ $B$ $f\colon A\rightarrow B,$ $\left|A\right|>n\cdot \left|B\right|,$ $n$ $\left|X\right|$ $x$ $f$ $n+1$

Alkalmazási példák

1. tétel . Az egységnégyzeten belüli öt pont bármely választása esetén van egy pontpár, amelyet egymástól legfeljebb ${\frac {\sqrt {2}}{2}}.$

Bizonyíték . A tétel első pillantásra bonyolultnak és nem nyilvánvalónak tűnik, de a Dirichlet-elv segítségével minden nehézség nélkül bebizonyítható [9] . Osszuk a négyzetet 4 negyedre az ábrán látható módon. A Dirichlet-elv szerint az öt kiválasztott pont közül legalább kettő egy negyedbe esik, és ekkor a köztük lévő távolság nem lehet nagyobb, mint a negyed átlója, egyenlő ■ ${\sqrt {{\left({\frac {1}{2}}\right)}^{2}+{\left({\frac {1}{2}}\right)}^{ 2}}}={\frac {\sqrt {2}}{2}}.$

2. Tétel . Az emberek társaságának egy része kezet fog. Bizonyítsuk be, hogy a társaságban legalább két ember van, aki ugyanannyi kézfogást végzett [10] . $N$ $\left(N>1\right)$

Bizonyíték . Legyen - „dobozok”. Tegyük a dobozba a társaság azon tagjait, akik kezet fogtak. Ha a doboz nem üres, akkor a társaság egy vagy több tagja nem fogott kézfogást, így a doboz üres, mert akkor kevesebb a kézfogás, ebből következik, hogy mindig kevesebb a nem üres dobozok, mint , és ezért legalább egy doboz két vagy több személynek felel meg. ■ $\{H_{0},H_{1},\dots H_{N-1}\}$ $N$ $H_{k}$ $k$ $H_{0}$ $H_{N-1}$ $N.$ $N,$

3. tétel . Bármilyen pozitív irracionális számhoz végtelenül sok tört különbözik a kisebbtől, mint -tól (ez a Dirichlet-tétel egyik változata a diofantinuszi közelítésekről ) [11] [12] . $a$ ${\frac {p}{q)),$ $a$ ${\displaystyle {\frac {1}{q^{2))))$

Bizonyíték . Egy tetszőleges természetes számhoz készítsünk egy értékkészletet: $N$ ${\megjelenítési stílus (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],

\pontok,

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

ahol egy szám egész részét jelöli .

[x]

Mindezek a számok a 0 és 1 közötti intervallumhoz tartoznak. Dobozokba osztjuk őket : az első mezőbe számokat teszünk 0-tól a nem inkluzívig, a másodikba - az inkluzívtól a nem inkluzívig stb . De mivel a számok száma nagyobb, mint a dobozok száma, akkor a Dirichlet-elv szerint az egyik dobozban legalább két különbség lesz: és amikor $N$ $1/N$ $1/N$ $2/N$ $N$ $(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.$

A különbségek konstrukciós értékei kisebb mértékben térnek el, mint Feltételezve , így kapjuk: ${\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)),

vagy: (mert ).

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

q\leqslant N

A szám tetszőlegessége miatt a tört közelsége egy számhoz tetszőlegesen kicsinyíthető (jelen esetben biztosan nem nulla, hiszen feltétel szerint irracionális). Ezért az egyre közelebbi közelítéseknek megfelelő törtek száma végtelen. ■ $N$ $p/q$ $a$ $a$ ${\frac {p}{q)),$

További példák a következő forrásokban találhatók.

Cikk kínai maradék tétel .
N. B. Alfutova és A. V. Ustinov könyve [13] .
M. könyv Aigner M. és G. Ziegler [14] .
A. A. Andreev és társai könyve [15]

Geometriai alkalmazások

A geometriában a Dirichlet-elv számos változatát alkalmazzák a hosszokra, területekre és térfogatokra vonatkozóan [16] .

Ha egy hosszúságú szakaszon több olyan szegmens található, amelyek hosszúságának összege nagyobb, mint , akkor ezek közül legalább kettőnek van közös pontja. $L$ $L$
Általánosítás . Ha egy hosszúságú szakaszon több olyan szakasz van, amelyek hosszának összege nagyobb, mint , akkor legalább egy pontot lefed legalább az egyik szakasz. $L$ $kL$ $k+1$
Ha a szakaszok hosszának összege kisebb, mint , akkor nem fedik le teljesen a hosszúságú szakaszt . $L$ $L$
Ha egy olyan terület ábráján belül több olyan alak is található, amelyek területeinek összege nagyobb, mint , akkor ezek közül legalább kettőnek van közös pontja. $S$ $S$
Ha több alakzat területeinek összege kisebb , akkor nem fedhetik le a területi ábrát . $S$ $S$

Hasonló állítások fogalmazhatók meg a kötetekre.

Példa [17] . Egy 6 átmérőjű körben véletlenszerűen több kört helyezünk el, átmérőjük összege 50. Bizonyítsuk be, hogy van olyan egyenes, amely e körök közül legalább kilencet metsz.

Bizonyíték . Legyen az eredeti kör tetszőleges átmérője (6 hosszúságú). Vetítsük át az összes belső kört . A vetületek hosszának összege nyilvánvalóan egyenlő a körök átmérőjének összegével, azaz 50, és lefedik (nem feltétlenül teljesen) az átmérőt . Mivel tehát a Dirichlet-elv 2. változata szerint az AB szakaszon van egy pont, amely legalább kilenc kör vetületéhez tartozik. Ekkor az ezen a ponton átmenő és az átmérőre merőleges egyenes a szükséges, amely ezt a kilenc kört metszi. ■ $D$ $D$ $D$ $50>8\cdot D$ $D$

Változatok és általánosítások

A Dirichlet-elv általánosításának egyik módja a valós számokra való kiterjesztése [18] .

Ha a nyulak megettek egy kg füvet, akkor legalább egy nyúl evett legalább egy kg füvet. $m$ $n$ $n\over m$

Következmények [18] .

Ha a számok összege nagyobb, akkor ezek közül legalább egy nagyobb $n$ $S$ ${\frac {S}{n}}.$
Ha több szám számtani közepe nagyobb, mint , akkor ezek közül a számok közül legalább egy nagyobb $A$ $A.$

A Dirichlet-elvnek van egy általánosítása a végtelen halmazok esetére : nincs erősebb halmaz befecskendezése kevésbé erős halmazba [19] .

Példák [19] .

Ha egy véges sejthalmaz végtelen számú galambot tartalmaz, akkor legalább egy sejt egynél több galambot tartalmaz. Sőt, könnyen kimutatható, hogy legalább egy cellában végtelen számú galamb lesz.
Ha egy megszámlálható dobozhalmaz megszámlálhatatlan galambhalmazt tartalmaz , akkor legalább egy cella egynél több galambot tartalmaz. Sőt, kimutatható, hogy legalább egy cellában megszámlálhatatlan számú galamb lesz.

A fenti általánosítás például a Siegel-lemmának Axel Thue [20] által javasolt bizonyításán alapul .

A Dirichlet-elv számos modern általánosítását a Ramsey-elmélet című cikk tartalmazza .

Dirichlet valószínűségi elv. Tegyük fel, hogy a nyulak véletlenszerű ketrecekben ülnek, és a nyulak véletlenszerű ketrecekben ülnek ugyanabból a ketrecből. Jelölje annak valószínűségét, hogy egy nyúl és egy nyúl ül valamelyik ketrecben.

m

k

n

k

p(m,n,k)

Ha néhány fix , akkor .

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

\varepsilon >0

p(m,n,k)\to 1

k\to \infty

Ha néhány fix , akkor .

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

\varepsilon >0

p(m,n,k)\to 0

k\to \infty

Jegyzetek

↑ Andreev et al., 1997 , p. 3.
↑ Németül az állítást "doboz-elvnek" hívják ( németül: schubfachprinzip )
↑ 1 2 Uspensky, V. A. Előszó a matematikához [cikkgyűjtemény]. - Szentpétervár. : LLC "Amphora Kereskedelmi és Kiadó", 2015. - S. 336-338. — 474 p. — (Népszerű tudomány, 12. sz.). - ISBN 978-5-367-03606-0 .
↑ Rittaud, Benoît; Heeffer, Albrecht (2014). „A galamblyuk-elv, két évszázaddal Dirichlet előtt” . A matematikai intelligencia . 36 (2), 27-29. DOI : 10.1007/s00283-013-9389-1 . HDL : 1854/LU-411526 . MR 3207654 . Archiválva az eredetiből, ekkor: 2021-12-25 . Letöltve: 2021-10-01 . Elavult használt paraméter |deadlink=( súgó )
↑ Jeff Miller, Peter Flor, Gunnar Berg, Julio González Cabillon . Galamblyuk elv Archivált 2010. február 12-én a Wayback Machine -nél // Jeff Miller (szerk.) Earliest Known Uses of Some of the Words of the Mathematics Archivált 2009. március 4-én a Wayback Machine -nél . Elektronikus dokumentum, letöltve: 2006. november 11
↑ Mat. enciklopédia, 1982 .
↑ Brualdi, Richard A. (2010), Introductory Combinatorics (5. kiadás), Prentice Hall , p. 70, ISBN 978-0-13-602040-0
↑ Alfutova N. B., Ustinov A. V., 2009 , p. 17.
↑ Rue, Juanjo. Örök vándor // A számolás művészete. Kombinatorika és felsorolás (3. fejezet). - M. : De Agostini, 2014. - S. 87. - 144 p. — (A matematika világa: 45 kötetben, 34. kötet). - ISBN 978-5-9774-0729-8 .
↑ foxford .
↑ Duran, Antonio. A számok költészete. Finom és matek. - M. : De Agostini, 2014. - S. 57. - 160 p. — (A matematika világa: 45 kötetben, 27. kötet). — ISBN 978-5-9774-0722-9 .
↑ Alfutova N. B., Ustinov A. V., 2009 , p. 19.
↑ Alfutova N. B., Ustinov A. V., 2009 , p. 17-20.
↑ Aigner, Ziegler, 2006 .
↑ Andreev et al., 1997 .
↑ Andreev et al., 1997 , p. 13-16.
↑ Andreev et al., 1997 , p. tizennégy.
↑ 1 2 Andreev et al., 1997 , p. 16-18.
↑ 12 Francis Su . Galamblyuk elv . Letöltve: 2021. október 3. Az eredetiből archiválva : 2021. október 3.. (határozatlan)
↑ csütörtök , A. (1909), Über Annäherungswerte algebraischer Zahlen , Journal für die reine und angewandte Mathematik T. 1909 (135): 284–305, ISSN 0075-4102 , doi : 10.1515/ sol.1909 . .uni-goettingen.de/purl?PPN243919689_0135 > Archiválva : 2020. október 30. a Wayback Machine -nél

Irodalom

Aigner M. , Ziegler G. A Dirichlet-elv és a kettős számolás () 22. fejezet) // Bizonyítások a könyvből . A legjobb bizonyíték Eukleidész korától napjainkig. — M .: Mir, 2006. — 256 p. — ISBN 5-03-003690-3 .
Alfutova N. B., Ustinov A. V. Algebra és számelmélet. Feladatgyűjtemény matematikai iskolák számára. - 3. kiadás, Rev. add .. - M . : MTSNMO, 2009. - 336 p. - ISBN 978-5-94057-550-4 .
Andreev A. A., Gorelov G. N., Lyulev A. I., Savin A. N. A Dirichlet-elv. Oktatási kiadás. - Samara: Pythagoras, 1997. - 21 p. - (A sorozat: Matematika. 1. szám).
Glibichuk A. A., Dainyak A. B., Ilyinsky D. G., Kupavsky A. B., Raigorodsky A. M., Skopenkov A. B., Chernov A. A. Elements of discrete mathematics in problems. - M. : MTSNMO, 2016. - S. 12-14. — 174 p. — ISBN 978-5-4439-3024-4 .
Dirichlet-elv, dobozok // Mathematical Encyclopedia (5 kötetben). - M .: Szovjet Enciklopédia , 1982. - T. 2. - S. 182.
Znak E. I. Egészrácsok partíciói és a Dirichlet-elv // Matematikai oktatás . - 2015. - Kiadás. 19 (harmadik sorozat) . - S. 241-248 .

Linkek

Boltyansky V. Hat nyúl öt ketrecben // Kvant . - 1977. - 2. sz. - S. 17-20, 37, 42.
Bugaenko V. O. Matematikai kör. 9. évfolyam 2. lecke. Dirichlet-elv . Hozzáférés időpontja: 2020. november 18. (határozatlan)
Dirichlet-elv . Letöltve: 2020. március 30. (határozatlan)

Szótárak és enciklopédiák	nagy kínai Britannica (online)