Principiul Dirichlet (combinatorie)

Principiul Dirichlet este o metodă simplă, intuitivă și adesea utilă pentru a demonstra afirmațiile de mulțimi finite . Acest principiu este adesea folosit în matematica discretă , unde stabilește o legătură între obiecte ("iepuri") și recipiente ("celule") în anumite condiții [1] . În engleză și în alte limbi, această declarație este cunoscută sub numele de principiul porumbeilor , când obiectele sunt porumbei, iar recipientele sunt cutii [ 2] .

Cea mai comună este formularea cea mai simplă a principiului Dirichlet [3] :

Dacă iepurii sunt așezați în cuști, iar numărul de iepuri este mai mare decât numărul de cuști, atunci cel puțin una dintre cuști conține mai mult de un iepure.

Există, de asemenea, o expresie comună pentru aceasta:

Dacă numărul de celule este mai mare decât numărul de iepuri, atunci cel puțin o celulă este goală.

Pentru alte formulări mai generale, vezi de mai jos .

Istoricii au găsit prima formulare a acestui principiu în colecția populară Récréations Mathématiques ( franceză Récréations Mathématiques , 1624, sub numele H. van Etten ), care a fost publicată (probabil) de matematicianul francez Jean Leurechon [4] . Acest principiu a devenit larg răspândit după aplicarea lui de către Dirichlet (începând din 1834) în domeniul teoriei numerelor [5] .

Principiul lui Dirichlet, într-o formă sau alta, este aplicat cu succes în demonstrarea teoremelor, făcând aceste demonstrații mai simple și mai clare. Printre domeniile sale de aplicare se numără matematica discretă, teoria [6]etc.sistemelor de inegalități liniare, analiza solvabilitățiiaproximărilor diofantine [3] .

Altă formulare

Dovada

Principiul lui Dirichlet în cea mai simplă formulare: „ dacă numărul de iepuri este mai mare decât numărul de celule, atunci cel puțin una dintre celule conține mai mult de un iepure ” poate fi dovedit prin metoda „prin contradicție” . Să fie cuști și iepuri, în plus . Denota. numărul de iepuri din celula -a ( ). Să presupunem că există cel mult un iepure în fiecare cușcă: $n$ $m$ $m>n$ $k_i$ $i$ $i=1,2,\dots n$

$k_{1}\leqslant 1$ (numarul de iepuri din prima cusca este mai mic sau egal cu 1);
$k_{2}\leqslant 1$ (numarul de iepuri din a 2-a cusca este mai mic sau egal cu 1);
...
$k_{n}\leqslant 1$ (numărul de iepuri din celula -a este mai mic sau egal cu 1). $n$

Apoi numărul total de iepuri Prin urmare Dar în funcție de starea problemei . Am o contradicție, ■ . $m=k_{1}+k_{2}+\ldots +k_{n}\leqslant 1+1+\ldots +1=n.$ $m\leqslant n$ $m>n$

Afirmația pereche este dovedită în mod similar: „ dacă numărul de celule este mai mare decât numărul de iepuri, atunci cel puțin o celulă este goală ”.

În plus față de cele două formulări de mai sus, există două mai utile, care sunt, de asemenea, ușor de demonstrat [7] :

Dacă iepurii sunt așezați în cuști și nu există cuști goale, atunci există exact un iepure în fiecare cușcă. $n$ $n$
Dacă iepurii sunt așezați în cuști și nicio cușcă nu conține mai mult de un iepure, atunci există exact un iepure în fiecare cușcă. $n$ $n$

Opțiuni pentru formulări mai generale [8] :

Cu orice distribuire sau mai multe articole în cutii, în orice cutie va exista nu mai puțin de un articol. $kn+1$ $n$ $k+1$
Dacă iepurii sunt așezați în cuști, atunci cel puțin o cușcă conține cel puțin iepuri și cel puțin o cușcă nu conține mai mult de iepuri. Aici , colțurile lui Iverson și rotunjesc expresia cuprinsă în ele la întreg, respectiv, în sus și în jos. $m$ $n$ $\left\lceil {\frac {m}{n}}\right\rceil$ $\left\lfloor {\frac {m}{n}}\right\rfloor$ $\lceil \dots \rceil$ $\lfloor \dots \rfloor$
Să fie dată o funcție definită pe o mulțime finită și maparea acesteia la o mulțime finită : unde este un număr natural , iar construcția formei înseamnă numărul de elemente ale mulțimii finite ( cardinalitatea mulțimii ). Apoi funcția va lua o anumită valoare cel puțin o dată. $f,$ $A$ $B$ $f\colon A\rightarrow B,$ $\left|A\right|>n\cdot \left|B\right|,$ $n$ $\left|X\right|$ $X$ $f$ $n+1$

Exemple de aplicații

Teorema 1 . Pentru orice alegere de cinci puncte în interiorul pătratului unității , există o pereche de puncte separate unul de celălalt de cel mult ${\frac {\sqrt {2}}{2}}.$

Dovada . Teorema la prima vedere pare complicată și neevidentă, dar cu ajutorul principiului Dirichlet se dovedește fără dificultate [9] . Împărțiți pătratul în 4 sferturi, așa cum se arată în figură. Conform principiului Dirichlet, cel puțin două dintre cele cinci puncte selectate vor cădea într-un sfert, iar apoi distanța dintre ele nu va fi mai mare decât diagonala sfertului, egală cu ■ ${\sqrt {{\left({\frac {1}{2}}\right)}^{2}+{\left({\frac {1}{2}}\right)}^{ 2}}}={\frac {\sqrt {2}}{2}}.$

Teorema 2 . O parte din compania oamenilor dau mâna. Demonstrați că în companie există cel puțin două persoane care au făcut același număr de strângeri de mână [10] . $N$ $\stanga(N>1\dreapta)$

Dovada . Let - „cutii”. Să punem în cutie acei membri ai companiei care și-au dat mâna. Dacă caseta nu este goală, atunci unul sau mai mulți membri ai companiei nu au făcut nicio strângere de mână și, prin urmare, caseta este atunci goală, deoarece numărul de strângeri de mână este mai mic . Rezultă că sunt întotdeauna mai puține non-gol. cutii decât și, prin urmare, cel puțin o cutie corespunde la două sau mai multe persoane. ■ $\{H_{0},H_{1},\dots H_{N-1}\}$ $N$ $H_{k}$ $k$ $H_{0}$ $H_{N-1}$ $N.$ $N,$

Teorema 3 . Pentru orice număr irațional pozitiv , există infinit de fracții care diferă de mai puțin decât cu (aceasta este una dintre versiunile teoremei Dirichlet privind aproximațiile diofantine ) [11] [12] . $A$ ${\frac {p}{q)),$ $A$ ${\frac {1}{q^{2)}}$

Dovada . Pentru un număr natural arbitrar , să facem un set de valori: $N$ $(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],

\dots ,

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

unde denotă partea întreagă a unui număr.

[X]

Toate aceste numere aparțin intervalului de la 0 la 1 inclusiv. Le împărțim în casete: în prima casetă punem numere de la 0 inclusiv la non-inclusiv, în a doua - de la inclusiv la non-inclusiv, etc., în al- lea - de la inclusiv la non-inclusiv. Dar, deoarece numărul de numere este mai mare decât numărul de casete, atunci, conform principiului Dirichlet, într-una dintre casete vor exista cel puțin două diferențe: și când $N$ $1/N$ $1/N$ $2/N$ $N$ $(N-1)/N$ $N/N$ $\stanga(N+1\dreapta)$ $\stanga(N\dreapta),$ $d_{i}=\stanga(i\cdot a-[i\cdot a]\dreapta)$ $d_{j}=\left(j\cdot a-[j\cdot a]\right)$ $i<j.$

Valorile diferențelor în funcție de construcție diferă cu mai puțin decât Presupunând și obținem: ${\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)),

sau: (pentru că ).

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

q\leqslant N

Datorită caracterului arbitrar al numărului, apropierea unei fracții de un număr poate fi făcută arbitrar de mică (în acest caz, este cu siguranță diferită de zero, deoarece este irațională prin condiție). Prin urmare, numărul de fracții care corespund unor aproximări din ce în ce mai apropiate este infinit. ■ $N$ $p/q$ $A$ $A$ ${\frac {p}{q)),$

Exemple suplimentare pot fi găsite în următoarele surse.

Articolul Teorema restului chineză .
Carte de N. B. Alfutova și A. V. Ustinov [13] .
Cartea M. Aigner M. și G. Ziegler [14] .
Carte de A. A. Andreev și colab. [15]

Aplicații geometrice

În geometrie se folosesc mai multe variante ale principiului Dirichlet, referitoare la lungimi, arii și volume [16] .

Dacă pe un segment de lungime există mai multe segmente cu o sumă de lungimi mai mare decât , atunci cel puțin două dintre aceste segmente au un punct comun. $L$ $L$
Generalizare . Dacă există mai multe segmente pe un segment de lungime a căror sumă de lungimi este mai mare decât , atunci cel puțin un punct este acoperit de cel puțin unul dintre aceste segmente. $L$ $kL$ $k+1$
Dacă suma lungimilor segmentelor este mai mică de , atunci acestea nu pot acoperi complet segmentul de lungime . $L$ $L$
Dacă există mai multe figuri în interiorul figurii unei zone a cărei sumă de zone este mai mare decât , atunci cel puțin două dintre ele au un punct comun. $S$ $S$
Dacă suma suprafețelor mai multor figuri este mai mică , atunci acestea nu pot acoperi cifra suprafeței . $S$ $S$

Declarații similare pot fi formulate pentru volume.

Exemplul [17] . Mai multe cercuri sunt plasate aleatoriu într-un cerc cu diametrul 6, suma diametrelor lor este egală cu 50. Demonstrați că există o linie care intersectează cel puțin nouă dintre aceste cercuri.

Dovada . Fie un diametru arbitrar al cercului original (de lungime 6). Să proiectăm toate cercurile interioare la un diametru de . Suma lungimilor proiecțiilor este în mod evident egală cu suma diametrelor cercurilor, adică 50, și acopera (nu neapărat complet) diametrul . Din moment ce , atunci, conform celei de-a doua versiuni a principiului Dirichlet, există un punct pe segmentul AB care aparține proiecțiilor a cel puțin nouă cercuri. Atunci linia care trece prin acest punct și perpendiculară pe diametru este cea necesară, ea intersectează toate aceste nouă cercuri. ■ $D$ $D$ $D$ $50>8\cdot D$ $D$

Variații și generalizări

O modalitate de a generaliza principiul Dirichlet îl extinde la numerele reale [18] .

Dacă iepurii au mâncat un kg de iarbă, atunci cel puțin un iepure a mâncat cel puțin un kg de iarbă. $m$ $n$ $n\peste m$

Consecințe [18] .

Dacă suma numerelor este mai mare , atunci cel puțin unul dintre aceste numere este mai mare $n$ $S$ ${\frac {S}{n}}.$
Dacă media aritmetică a mai multor numere este mai mare decât , atunci cel puțin unul dintre aceste numere este mai mare $A$ $A.$

Există o generalizare a principiului Dirichlet în cazul mulțimilor infinite : nu există injectarea unui set mai puternic într-unul mai puțin puternic [19] .

Exemple [19] .

Dacă un număr infinit de porumbei este conținut într-un set finit de celule, atunci cel puțin o celulă va conține mai mult de un porumbel. Mai mult, este ușor să arăți că va exista un număr infinit de porumbei în cel puțin o celulă.
Dacă un set nenumărat de porumbei este conținut într-un set numărabil de cutii, atunci cel puțin o celulă va conține mai mult de un porumbel. Mai mult, se poate demonstra că în cel puțin o celulă va exista un număr nenumărat de porumbei.

Generalizarea de mai sus se bazează, de exemplu, pe demonstrarea lemei lui Siegel propusă de Axel Thue [20] .

O serie de generalizări moderne ale principiului Dirichlet sunt date în articolul Teoria Ramsey .

Principiul probabilistic al lui Dirichlet. Să presupunem că iepurii stau în cuști aleatorii din aceleași cuști și iepurii stau în cuști aleatorii din aceleași cuști. Indicați prin probabilitatea ca un iepure cu un iepure să stea într-o cușcă.

m

k

n

k

p(m,n,k)

Dacă pentru unele fixe , atunci pentru .

m\cdot n>k^{1+\varepsilon }

\varepsilon >0

p(m,n,k)\la 1

k\to \infty

Dacă pentru unele fixe , atunci pentru .

m\cdot n<k^{1-\varepsilon }

\varepsilon >0

p(m,n,k)\la 0

k\to \infty

Note

↑ Andreev și colab., 1997 , p. 3.
↑ În germană, afirmația se numește „principiul cutiei” ( germană: schubfachprinzip )
↑ 1 2 Uspensky, V. A. Prefață la matematică [colecție de articole]. - Sankt Petersburg. : SRL „Comerciant și editura Amphora”, 2015. - S. 336-338. — 474 p. — (Știința populară, nr. 12). - ISBN 978-5-367-03606-0 .
↑ Rittaud, Benoît; Heeffer, Albrecht (2014). „Principiul porumbeilor, cu două secole înainte de Dirichlet” . Inteligetorul matematic . 36 (2): 27-29. DOI : 10.1007/s00283-013-9389-1 . HDL : 1854/LU-411526 . MR 3207654 . Arhivat din original pe 25.12.2021 . Accesat 2021-10-01 . Parametrul depreciat folosit |deadlink=( ajutor )
↑ Jeff Miller, Peter Flor, Gunnar Berg, Julio González Cabillon . Principiul porumbeilor Arhivat la 12 februarie 2010 la Wayback Machine // Jeff Miller (ed.) Primele utilizări cunoscute ale unora dintre cuvintele matematicii Arhivat la 4 martie 2009 la Wayback Machine . Document electronic, preluat la 11 noiembrie 2006
↑ Enciclopedia Mat., 1982 .
↑ Brualdi, Richard A. (2010), Introductory Combinatorics (ed. a 5-a), Prentice Hall , p. 70, ISBN 978-0-13-602040-0
↑ Alfutova N. B., Ustinov A. V., 2009 , p. 17.
↑ Rue, Juanjo. Etern rătăcitor // Arta numărului. Combinatorică și enumerare (Capitolul 3). - M. : De Agostini, 2014. - S. 87. - 144 p. — (Lumea matematicii: în 45 de volume, volumul 34). - ISBN 978-5-9774-0729-8 .
↑ Foxford .
↑ Duran, Antonio. Poezia numerelor. Fine și matematică. - M. : De Agostini, 2014. - S. 57. - 160 p. — (Lumea matematicii: în 45 de volume, volumul 27). — 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 și colab., 1997 .
↑ Andreev și colab., 1997 , p. 13-16.
↑ Andreev și colab., 1997 , p. paisprezece.
↑ 1 2 Andreev și colab., 1997 , p. 16-18.
↑ 12 Francis Su . Principiul porumbeilor . Preluat la 3 octombrie 2021. Arhivat din original la 3 octombrie 2021. (nedefinit)
↑ Thue , 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/ crll.13,5solver.sub . .uni-goettingen.de/purl?PPN243919689_0135 > Arhivat 30 octombrie 2020 la Wayback Machine

Literatură

Aigner M. , Ziegler G. Principiul Dirichlet și dubla numărare () capitolul 22) // Dovezi din carte . Cele mai bune dovezi din vremea lui Euclid până în zilele noastre. — M .: Mir, 2006. — 256 p. — ISBN 5-03-003690-3 .
Alfutova N. B., Ustinov A. V. Algebră și teoria numerelor. Culegere de sarcini pentru școlile de matematică. - Ed. a 3-a, Rev. adaugă .. - M . : MTSNMO, 2009. - 336 p. - ISBN 978-5-94057-550-4 .
Andreev A. A., Gorelov G. N., Lyulev A. I., Savin A. N. Principiul Dirichlet. Ediție educațională. - Samara: Pitagora, 1997. - 21 p. - (Seria A: Matematică. Numărul 1).
Glibichuk A. A., Dainyak A. B., Ilyinsky D. G., Kupavsky A. B., Raigorodsky A. M., Skopenkov A. B., Chernov A. A. Elemente de matematică discretă în probleme. - M. : MTSNMO, 2016. - S. 12-14. — 174 p. — ISBN 978-5-4439-3024-4 .
Principiul Dirichlet, casete // Enciclopedia matematică (în 5 volume). - M .: Enciclopedia Sovietică , 1982. - T. 2. - S. 182.
Znak E. I. Partiții ale rețelelor întregi și principiul Dirichlet // Educație matematică . - 2015. - Emisiune. 19 (seria a treia) . - S. 241-248 .

Link -uri

Boltyansky V. Șase iepuri în cinci cuști // Kvant . - 1977. - Nr. 2. - S. 17-20, 37, 42.
Bugaenko V. O. Cercul matematic. Clasa a 9-a Lecția numărul 2. Principiul Dirichlet . Data accesului: 18 noiembrie 2020. (nedefinit)
Principiul Dirichlet . Preluat: 30 martie 2020. (nedefinit)

Dicționare și enciclopedii	mare chinezesc Britannica (online)