luni, 16 noiembrie 2015
miercuri, 24 iunie 2015
marți, 2 iunie 2015
joi, 21 mai 2015
PRINCIPIUL CUTIEI
Principiul cutiei-Principiul lui Dirichlet
Cea mai simpla formulare a principiului cutiei este urmatoarea : “ Dacă plasăm n + 1 obiecte în n cutii, atunci cel puţin o cutie conţine cel puţin 2 obiecte. “
Acest principiu de combinatorica a fost pentru prima data utilizat de Dirichlet(1805-1859)in teoria numerelor.Desi pare simplu are un numar foarte mare de aplicatii,fiind folosit in demonstrarea unor rezultate importante.Pentru inceput prezint citeva probleme simple fara solutii:
-Printre trei persoane exista doua de acelasi sex.
-Printre treisprezece persoane se afla doua nascute in aceeasi luna.
- Nimeni nu are mai mult de 300.000 de fire de par pe cap.Capitala Sikiniei are 300.001 locuitori .Puteti afirma cu siguranta ca exista doua persoane cu acelasi numar de fire de par pe cap ?
-O dreapta l din planul triunghiului ABC nu trece prin nici un virf al acestuia .Demonstrati ca nu poate intersecta toate laturile triughiului.
-Un plan nu trece prin nici un virf al unui tetraedru .Cite muchii poate intersecta?
1)Problema 1.
Fiind date n+1 numere naturale ,atunci cel putin doua dintre ele dau , la impartirea la n acelasi rest
(n )
Solutie : Conform teoremei impartirii cu rest exista n valori posibile pentru rest si anume 0,1,2,......,n-1.Cum avem n+1 numere rezulta ca de cel putin doua ori va rezulta acelasi rest.
Problema 2. Sa se arate ca oricum am alege 7 patrate perfecte distincte exista cel putin doua a caror diferenta este divizibila cu 10.
Solutie :Restul impartirii unui patrat perfect la 10 este 0,1,4,5,6 sau 9 in total 6 resturi distincte si noi avem 7 patrate ,deci cel putin doua au aceeasi ultima cifra iar diferenta lor se termina in 0.
Problema 3. Să se demonstreze că pentru orice număr natural n≥1, există un număr natural format din cifrele 0 şi 5, divizibil prin n.
Soluţie.
Considerăm numerele
a1 = 50, a2 = 5050, …, an =
pe care le repartizăm în cutii numerotate cu numerele 0, 1, … , n-1 (care reprezintă resturile împărţirii la n). Dacă în cutia 0 este un obiect (adică un număr), atunci problema este rezolvată. În caz contrar, n obiecte sunt plasate în n-1 cutii, şi conform principiului lui Dirichlet, există două obiecte plasate în aceeaşi cutie. Deci, există două numere care dau acelaşi rest la împărţirea prin n. Diferenţa lor va fi divizibilă prin n, iar diferenţa lor este un număr format tot din cifrele 0 şi 5.
La rezolvarea unor probleme este util de aplicat principiul Dirichlet generalizat:
“Dacă plasăm pn+1 obiecte în n cutii, atunci cel puţin o cutie va conţine cel puţin p+1 obiecte”.
Problema 4. Într-o şcoală sunt 1100 de elevi. Să se arate că există o zi în care cel puţin 4 elevi îşi sărbătoresc ziua de naştere.
Soluţie.
Un an bisect are 366 zile şi
1100 = 366 ∙ 3 + 2, deci conform principiului lui Dirichlet există o zi în care s-au născut cel puţin 3 + 1 = 4 elevi. Cu atât mai mult dacă anul nu este bisect
Unele probleme (în special ce ţin de geometrie) se rezolvă, utilizând principiul lui Dirichlet în următoarele enunţuri:
a) dacă pe un segment de lungime l sunt situate câteva segmente cu suma lungimilor mai mare ca l, atunci cel puţin două segmente au un punct comun ;
b) dacă în interiorul unei figuri de arie S sunt plasate figuri cu suma ariilor mai mare decât S, atunci există cel puţin două dintre aceste figuri au un punct comun ;
c) dacă figurile F1,F2,…,Fn cu ariile S1,S2,…,Sn respectiv sunt incluse în figura F cu arie S şi S1+S2…+Sn > kS, atunci k+1 din figurile F1,F2…,Fn au un punct comun.
Problema 5. Să se arate că printre oricare 5 puncte situate în interiorul unui triunghi echilateral de latură l există cel puţin două puncte situate la o distanţă mai mică sau egală cu l/2.
Soluţie.
Împărţim triunghiul dat în 4 triunghiuri echilaterale congruente prin trasarea liniilor mijlocii. Laturile acestor triunghiuri având lungimea l/2, putem deduce că două puncte situate în interiorul aceluiaşi triunghi nu se pot afla la o distanţă mai mare de l/2 unul faţă de celălalt. Conform principiului cutiei (deoarece avem 4 triunghiuri şi 5 puncte), două puncte se vor găsi în interiorul aceluiaşi triunghi, deci distanţa dintre ele va fi mai mică sau egală cu
Problema 6. Într-un dreptunghi cu dimensiunile 3 cm şi 4 cm sunt plasate 6 puncte. Să se arate că printre aceste puncte există cel puţin două cu distanţa dintre ele cel mult egală cu cm.
Soluţie.
Împărţim dreptunghiul iniţial în 6 dreptunghiuri mici congruente cu dimensiunile 1 cm şi 2 cm, ale căror diagonale au lungimile egale cu cm şi considerăm unul din cele 6 puncte situat pe una din dreptele care au împărţit dreptunghiul. Distanţa dintre oricare două puncte situate în acelaşi dreptunghi mic este cel mult egală cu cm . Dacă într-unul din cele 6 dreptunghiuri mici în care se află punctul respectiv se mai află încă un punct, atunci problema este rezolvată. În caz contrar, mai rămân 4 dreptunghiuri mici în care sunt distribuite 5 puncte, şi conform principiului cutiei, va exista sigur un dreptunghi mic în care sunt plasate două puncte. Cele două puncte se află la o distanţă mai mică sau egală cu cm.
Problema 7. Fiind date 6 puncte situate în interiorul unui cerc de rază 1, să se arate că există 2 puncte la o distanţă cel mult egală cu 1.
Soluţie.
Trasăm 6 raze, astfel încât să împărţim cercul în 6 sectoare egale şi unul din cele 6 puncte să fie situat pe una din raze. Distanţa dintre două puncte situate în acelaşi sector este cel mult egală cu 1. Dacă într-unul dintre cele două sectoare în care se află punctul respectiv se mai află încă un punct, atunci problema este rezolvată. În caz contrar, mai rămân 4 sectoare în care sunt dispuse 5 puncte şi conform principiului lui Dirichlet, va exista cel puţin un sector în care sunt situate două puncte. Cele două puncte din acelaşi sector se află la o distanţă cel mult egală cu 1.
Abonați-vă la:
Postări (Atom)