Principiul lui Dirichlet

Principiul lui Dirichlet sau Principiul cutiei sau Principiul porumbeilor este o generalizare a următoarei afirmații: Dacă avem trei pantofi, atunci avem sigur cel puțin doi pantofi drepți sau cel puțin doi pantofi stângi.

El este cunoscut în mai multe variante echivalente:

1. Dacă avem n cutii în care punem n+1 bile, atunci va exista cel puțin o cutie cu cel puțin două bile.
   • Dacă avem n porumbei și n-1 cuști, atunci cel puțin o cușcă va conține cel puțin doi porumbei.
2. Dacă N obiecte trebuie plasate în M containere, unde N>M, atunci cel puțin un container va conține mai mult decât un obiect.
3. Dacă plasăm $k \times n+1$ obiecte în $n$ cutii ($n,k \in \mathbb{N}$), atunci cel puțin $k + 1$ vor fi în aceeași cutie.

Aplicații

Șosete

Avem N perechi de șosete de culori diferite. Ele sunt într-un sertar într-o cameră fără lumină. Câte șosete trebuie extrase din sertar pentru a fi siguri că avem două șosete împerechiate?

Soluție: Avem N culori (cutii). Conform principiului cutiei, dacă alegem N+1 șosete, vom avea cel puțin două de aceeași culoare. În pus, dacă alegem N șosete, pot fi de culori diferite două câte două. Răspunsul este deci N+1.

Aniversări

Într-o școală sunt 367 de elevi. Arătați că cel puțin doi dintre își serbează ziua de naștere la aceeași dată.

Soluție: Într-un an sunt cel mult N=366 zile (cutii). Avem M>N obiecte (elevi), deci cel puțin doi elevi își vor serba ziua de naștere la aceeași dată.

Numere

În orice mulțime de N+1 numere naturale există cel puțin două a căror diferență se divide cu N.

Soluție: Resturile posibile la împărțirea cu N sunt 0, 1, 2, ..., N-1. Deoarece avem N+1 numere, vom avea două numere cu același rest al împărțirii la N. Diferență lor se divide cu N!

Pătrate perfecte

În orice mulțime cu 7 pătrate perfecte există cel puțin două a căror diferență se divide cu 10.

Soluție: Un pătrat perfect se poate termina cu cifra 0, 1, 4, 5, 6 sau 9, adică resturile posibile la împărțirea unui pătrat perfect la 10 sunt 0 1 4 5 6 9. Sunt 6 resturi posibile și 7 numere, deci vor fi cel puțin două cu același rest; diferența lor va fi divizibilă cu 10.

Pătrate

Arătați că oricum am plasa 5 puncte pe suprafața unui pătrat cu latura 1, există două puncte între care distanța este cel mult $\frac{\sqrt{2}}{2}$.

Soluție: Împărțim pătratul inițial în patru pătrate cu latura $\frac{1}{2}$. Unul dintre pătrate va conține cel puțin două puncte, iar distanța dintre ele este cel mult egală cu diagonala pătratului, adică $\frac{\sqrt{2}}{2}$.