Principiul CUTIEI (al lui DIRICHLET)
Chiar dacă principiul cutiei lui Dirichelet se bazează pe una dintre cele mai simple observații matematice, rezolvarea problemelor folosind această metodă nu este o sarcină prea ușoară. În acest articol vom prezenta câteva probleme dificile care pot fi rezolvate folosind principiul cutiei (Dirichlet).
Principiul cutiei (Dirichlet) se bazează pe una dintre cele mai simple observații matematice: dacă avem n obiecte dispuse în n – 1 cutii, atunci există cel puțin o cutie care conține două obiecte.
Generalizare: La rezolvarea unor probleme este util de aplicat principiul Dirichlet generalizat.
Daca plasăm pn+1 obiecte în n cutii, atunci cel putin o cutie va contine cel puțin “p+1” obiecte.
Dar, pe cât de simplu este acest principiu, pe atât de complexe sunt implicațiile lui. Existã destule probleme, unele dintre ele propuse spre rezolvare la diferite concursuri de matematică, a cãror soluție se poate obține mult mai ușor dacă se folosește principiul cutiei .
Materialul prezentat mai jos va conține problemele cu număr impar rezolvate, cele cu număr par fiind propuse spre rezolvare.
Problema 1. În 500 de cutii se află mere. Se știe că în fiecare cutie se află cel mult 240 mere. Să se demonstreze că există cel puțin 3 cutii ce conțin același număr de mere.
Soluție. Fie că în primele 240 cutii se află un număr diferit de mere (1,2,…,240) și în următoarele 240 de cutii la fel (adică se examinează cazul extremal). Astfel, au rămas 500 – 2·240 = 20 cutii, în care trebuie plasate mere de la 1 la 240.
Problema 2 .Să se demonstreze că din 11 cifre pot fi selectate două cifre identice.
Problema 3. Să se demonstreze că printre orice șase numere întregi există două numere a căror diferență este divizibilă prin 5.
Soluție. Considerăm 5 cutii etichetate cu numerele 0,1,2,3,4, care reprezintă resturile împarțirii la 5. Repartizăm în aceste cutii șase numere întregi arbitrare, independente de restul împărțirii la 5, adică în aceeași cutie se plasează numerele cu același rest de împărțire la 5. Cum numere (“obiecte”) sunt mai multe decât cutii, conform principiului Dirichlet, există o cutie ce conține mai mult decât un obiect. Deci, există (cel puțin) două numere plasate în aceeași cutie. Prin urmare, există două numere cu același rest de împărțire prin 5. Atunci, diferența lor este divizibilă prin 5.
Problema 4. Într-o grupă sunt 25 de studenți cu vârste cuprinse de la 19 la 24 de ani. Să se arate că există cel puțin 5 studenți cu aceeași vârstă.
Problema 5..La un test de matematică, din cei 40 de elevi participanți, 25 de elevi au rezolvat prima problemă, 30 de elevi au rezolvat a doua problemă, 35 de elevi au rezolvat-o pe a treia, iar 33 de elevi au rezolvat problema a patra. Arătați că cel puțin trei elevi au rezolvat toate cele patru probleme.
Soluție: Presupunem că niciun elev nu a rezolvat toate cele patru probleme, deci fiecare a rezolvat cel mult trei. Atunci cei 40 de elevi au rezolvat cel mult 40×3=120 probleme. Dar numărul de probleme rezolvate de elevi a fost de 25+30
+35+33=123 probleme. Deci, având în plus 3 probleme rezolvate, înseamnă că cel puțin trei elevi au rezolvat toate cele 4 probleme
Problema 6. La un concurs de matematică participă 300 de elevi, repartizați în mod egal în 15 săli. Să se afle:
- a) Cel mai mic număr de fete care ar trebui să participe, știind că, indiferent cum s-ar face repartizarea, în fiecare sala trebuie să fie cel puțin o fată.
- b) Cel mai mare număr de fete care ar putea participa, astfel încât, indiferent de repartizare, să existe o sală numai cu băieți.
Problema 7. Să se arate că oricum am alege 7 numere pătrate perfecte distincte există cel puțin două a căror diferență se divide prin 10 .
Soluție : Voi studia cum se comportă un pătrat perfect la împărțirea prin 10, adică ce resturi poate da un p.p la împărțirea prin 10.
Deci fiind 6 cutii, oricum am alege 7 pătrate perfecte distincte vor exista două care să aparțină aceleiași mulțimi, adică să dea același rest la împărțirea prin 1 , ceea ce înseamnă că diferența lor se divide prin 10.
Problema 8. Să se arate că din orice trei numere prime, mai mari decât 3, se pot alege două cu proprietatea ca suma sau diferența lor se divide cu 12.
Cu ajutorul principiului cutiei se pot rezolva și probleme de geometrie.
Problema 9. În interiorul unui triunghi echilateral cu lungimea laturii 1 sunt plasate 5 puncte. Să se demonstreze că există două puncte din cele 5 cu distanța dintre ele mai mică decât 0,5.
Soluție. Divizăm triunghiul echilateral cu latura 1 în patru triunghiuri echilaterale cu lungimea laturii de 0,5 (fig. 1).
Atunci într-unul dintre triunghiuri vor fi cel puțin două puncte din cele 5. Maximul distanței în acel triunghi va fi lungimea laturii, adică 0,5.
Problema 10: (dată la examenul de admitere la Politehnică în anii ’80) Să se arate că oricum am alege 5 puncte distincte in interiorul unui pătrat de latură 1, există două cu distanța dintre ele mai mică decât .
Bibliografie
- Mircea Ganga, Teme si probleme de matematica, Ed. Tehnica, Bucuresti, 1991, 331p.
- V.A.Ufnarovski, Acvariu Matematic, “Stiinta”, Chisinau, 1988, 237p.
- Probleme de matematicã traduse din revista sovieticã Kvant, Editura Didacticã ºi Pedagogicã, București,1983