PRINCIPIUL CUTIEI ȘI APLICAȚII – PRINCIPIUL CUȘTILOR DE PORUMBEI

PRINCIPIUL CUTIEI ȘI APLICAȚII –
PRINCIPIUL CUȘTILOR DE PORUMBEI

Există probleme de matematică ce pot fi abordate cu mijloacele
gândiri cotidiene, dar care necesită multă imaginașie și
inginiozitate. Un exemplu de astfel de probleme sunt problemele care
pot fi rezolvate utiliând principiul cutiei (în engleză the
pigeohole principle- principiul cuștilor de porumbei).
,,Dacă n obiecte se repartizează în m cutii și n>m, atunci cel
puțin o cutie conține mai mult de un obiect”
Dacă de exemplu, avem 10 mingi și 9 cutii, putem așeza mingile
în cutii în mai multe moduri. Putem așeza toate mingile într-o
singură cutie, sau putem încerca să le distribuim în mod egal.
Dar, indiferent cum am face acestă așezare, cel puțin într-o
cutie vom avea mai mult de o minge. Acesta deorece există mai multe
mingi decât cutii.
Putem formula o formulă mai generală a principiului cutiei: ,,
Fie k≥1.Dacă mai mult de k obiecte sunr așezate în n cutii,
atunci cel puțin una din cutii trebuie să conțină mai mult de k
obiecte”
Voi prezenta câteva probleme care se pot rezolva folosind acest
principiul, unele dintre ele sunt simple, dar altele pot fi destul
de dificile (în special în alegerea obiectelor și a cutiilor).
1.În școala noastră sunt 12 clase, fiecare clasă având 31 de
elevi. Să se arate că există cel puțin doi elevi care sunt
născuți în aceeași zi și lună.
Soluție : Avem 31∙12=372 elevi și 365 (sau 366) de zile
într-un an. Deoarece exiștă mai mulți elevi( obiecte) decât
zilele anului (cutiile), există cel puțin doi elevi născuți în
aceeași zi și lună ( dar nu neapărat în același an).
2.La o conferință participă 100 de oaneni. Arătați că există
doi dintre ei care au același număr de cunoștințe printre
participanți.
Soluție :Avem 100 de obiecte, trebuie să găsim cutiile. S-ar
parea că ar trebui să atașam fiecărui participant numărul
cunoștințelor sale. Am avea un număr cuprins între 0 și 99, dar
asta ar însemna că avem 100 de cutii și nu am putea aplica
principiul cutiei
Există însă o subtilitate. Să presupunem că persoana x are 99
de cunoștințe printre ceilalți participanți, asta ar însemna
că nu există nici o persoană care să aibă 0 cunoștințe
(deorece x îi cunoște pe toți, și toți îl cunosc pe x). Acum
avem doar cutiile cu 1,2,3....,99 cunoștințe ( adică 99 de cutii)
și putem aplica principiul cutiei.
Dacă nu există o persoană care să-i cunoască pe toți
ceilalți, atunci luam cutiile 0,1,2,...,98.Avem tot 99 de cutii și
aplicăm din nou principul cutiei.
3.Într-un cub cu latura de 1 sunt situate n^3+1 puncte
distincte.Să se demonstreze că printre aceste puncte există două
la distanța mai mică sau cel mult egală cu √3/n.
Soluție : Împărțim muchile cubului în n părți de lungimi
egale și apoi împărțim cubul în n^3cubulețe. Conform
principiului cutiei, există un cubuleț ce conține în interior
sau pe una din fețe, două din cele n^3+1 puncte date. Distanța
dintre aceste puncre este cel mult egală cu lungimea diagonelei
cubulețului, adică √3/n.
4. ,, Dacă o mulțime A ⊂N, are 5 elemente, putem alege 3
elemente cu proprietatea că suma lor de divide cu 3”
Soluție : Fie A_0 acele elemente din A care dau 0 la împărțirea
cu 3.
A_1 cele care dau restul 1
A_2 cele care dau restul 2
Dacă cel puțin una din mulțimile A_0,A_1,A_2 este vidă, avem
două cutii și 5 obiecte, deci cel puțin una dintre cele două
mulțimi are cel puțin 3 elemente, suma acestora se divide cu 3(
dacă cele trei elemente sunt din A_1,suma lor se divide evident cu
3)
Dacă nici una dintre mulțimile〖 A〗_0,A_1,A_2 nu este vidă,
alegem câte un element din fiecare ,adică numerele :
n_1=3k ∈A_0
n_2=3p+1 ∈A_1
n_3=3t+2 ∈A_2
și suma lor este :
n_1+n_2+n_3=3k+3p+1+3t+2=3(k+p+t+1), adică multiplu de 3.

Prof. Ciceu Nela