Principiul lui Dirichlet
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ă cel puțin o cutie care conține 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.
Cuprins |
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.
Vezi și [modificare]
Bibliografie [modificare]
- Ronald L. Graham, Martin Grötschel and László Lovász, Handbook of Combinatorics vol. 2, MIT Press, 1995
