Principiul lui Dirichlet

De la Wikipedia, enciclopedia liberă
Salt la: Navigare, căutare

Principiul lui Dirichlet (sau al sertarelor, sau al porumbeilor) este o teoremă matematică ce afirmă că dacă există n obiecte dispuse în n-1 cutii, atunci există o cutie care conține cel puțin două obiecte. Chiar dacă principiul lui Dirichlet este binecunoscut, originile lui sunt obscure. Acest principiu a fost folosit de către Dirichlet într-o lucrare din 1879, dar a fost cu siguranță folosit anterior : Gauss a folosit acest principiu în Disquisitiones Arithmeticae (1801) și este foarte probabil ca el să fi fost folosit și mai înainte în literatură. Descrierea axiomatică a numerelor naturale de către Peano avea să intervină abia în 1889 și avea să fie apreciată de către Russel abia în 1919.

Demonstrație[modificare | modificare sursă]

Presupunem prin absurd că cineva a reușit să plaseze n obiecte în n-1 cutii în condițiile din enunț, fără însă ca vreuna din cutii să conțină mai mult de un singur obiect. Atunci în fiecare cutie găsim maximum un obiect. Vom avea așadar două tipuri de cutii :

- cutii cu câte un obiect
- cutii goale.

Nu se poate ca toate cutiile să fie goale, deoarece avem mai multe obiecte decât cutii. Atunci există o cutie care conține un obiect. Înlăturăm acea cutie și obiectul conținut în ea.

Rămâne o situație în care avem n-1 obiecte plasate în n-2 cutii.

După încă n-3 astfel de operații de înlăturare obținem o ultimă cutie, care conține două obiecte. Aceasta însă contravine presupunerii inițiale.

Astfel, presupunerea de mai sus este falsă, iar Principiul lui Dirichet este cu necesitate adevărat. Q.E.D.

Enunțuri echivalente[modificare | modificare sursă]

Forma funcțională[modificare | modificare sursă]

Dacă A și B sunt mulțimi cu |A| > |B|, atunci pentru fiecare funcție f:A-->B găsim un element b în B astfel încât |f-1(b)| > 1.

Forma partițională[modificare | modificare sursă]

Fie P o partiție a unei mulțimi A, astfel că P are mai puțin de |A| părți. Atunci una dintre părți conține mai mult decât un singur element al lui A.

Exemple[modificare | modificare sursă]

Exemplul 1[modificare | modificare sursă]

Există un număr de n perechi de pantofi de mărimi diferite, dar neordonați pe perechi. Care este numărul minim de pantofi care trebuie cercetați pentru a forma o pereche?

Răspunsul este evident: Utilizăm câte o cutie (inițial goală) pentru fiecare mărime. După așezarea în cutii a n+1 pantofi, o cutie va conține doi pantofi. Deci în mod sigur vom reuși ca al (n+1)-lea pantof să îl putem împerechea cu unul din cei n anterior selectați.

Exemplul 2[modificare | modificare sursă]

Se consideră vectorul \vec v = (a_1, a_2, \cdots , a_n), cu coordonatele numere naturale. Se caută indicii i < j cu proprietatea ca a_i + \cdots + a_j să fie multiplu de n.

Vom nota pentru orice x \in \mathbb N prin \hat x clasa sa de echivalență modulo n.

Considerăm sumele s_k = a_1 + \cdots + a_k pentru k=1, \cdots , n. Fie \hat s_k clasele de echivalență corespunzătoare.

Avem cazurile:

1) dacă există k cu \hat s+x = \hat 0, atunci o soluție este (i, j) = (1, k).

2) în caz contrar, este clar că \hat s_1, \cdots , \hat s_n \in . Conform principiului lui Dirichlet, vor exista indicii k<1 cu \hat s_k = s_1. Atunci o soluție este (i, j) = (k+1, 1).

Vezi și[modificare | modificare sursă]

Bibliografie[modificare | modificare sursă]