Principiul lui Dirichlet

Principiul lui Dirichlet (sau al sertarelor) 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

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

Forma funcțională modificare

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

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

Exemplul 1 modificare

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

Se consideră vectorul   cu coordonatele numere naturale. Se caută indicii   cu proprietatea ca   să fie multiplu de n.

Vom nota pentru orice   prin   clasa sa de echivalență modulo n.

Considerăm sumele   pentru   Fie   clasele de echivalență corespunzătoare.

Avem cazurile:

1) dacă există k cu   atunci o soluție este  

2) în caz contrar, este clar că   Conform principiului lui Dirichlet, vor exista indicii   cu   Atunci o soluție este  

Vezi și modificare

Bibliografie modificare