[10] Principiul lui Dirichlet / Principiul cutiei

[Admin]

Principiul lui Dirichlet (sau Principiul cutiei .. sau al sertarelor .. sau al porumbeilor - în engleză se mai numeşte Pigeonhole principle) 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 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 Matematică.

Principiul lui Dirichlet - ro.wikipedia.org
Pigeonhole principle - en.wikipedia.org

PS.
Prin simplitatea lui acest principiu se poate explica şi la clasa a 5-a.
Am ales prezentarea lui într-un topic din "zona de teorie" pentru clasa a 10-a deoarece principiul are multe aplicaţii în Combinatorică. Dar în general aplicaţiile lui sunt în zone vaste din Matematică.

[Admin]

Principiul lui Dirichlet Extins - Extended Pigeonhole Principle

Dacă nk+1 obiecte sunt aşezate în n cutii, atunci cel puţin o cutie va conţine cel puţin k+1 obiecte.
If nk+1 objects are placed in n boxes, then (at least) one of the boxes must contain at least k+1 objects.

Remarcă
În formulările în limba engleză (dar şi în multe locuri în română) lipseşte cel mai adesea expresia "at least" ("cel puţin") atunci când se face "referire la cutii". Ori acesta e un element totuşi important. Sunt probleme care chiar se bazează mai mult pe numărul cutiilor care conţin cel puţin x obiecte ...

De exemplu, dacă avem 3001 obiecte de aşezat în 1000 de cutii atunci avem "măcar" o cutie cu "minim" 4 obiecte.
Să ne gândim că punem 1000 obiecte într-o cutie, 2001 în altă cutie .. iar restul cutiilor rămân goale.
Deci avem 2 cutii cu minim 4 obiecte.

[Admin]

Principiul lui Dirichlet Generalizat - Generalized Pigeonhole Principle

Presupunem că avem nk+s sau mai multe obiecte de aşezat în n cutii.
Atunci pentru fiecare m, care verifică 0 ≤ m ≤ n , există m cutii care au împreună cel puţin mk + min(s,m) obiecte.

Suppose nk+s or more objects are placed in n boxes.
Then for each 0 ≤ m ≤ n there exist m boxes with a total of at least mk + min(s,m) objects.

[Admin]

[Admin]

Problemă. Se dă un pătrat cu latura de lungime $1$.
Să se arate că oricum am alege $5$ puncte interioare lui
există cel puțin $2$ astfel încât distanța dintre ele să fie mai mică decât $\dfrac{\sqrt{2}}{2}$.

Rezolvare - Principiul lui Dirichlet (principiul cutiei)

și împărțirea în $4$ pătrate identice, ca în imagine.