Principiul lui Dirichlet

Principiul lui Dirichlet

Principiul lui Dirichlet are un enunt simplu si care nu necesita demonstratie:

	Daca m>k n obiecte sunt plasate în n casute, atunci va exista o casuta ce va contine mai mult de k obiecte.

Prezentam în continuare câteva aplicatii ale acestui principiu.

Exemplul 1. Exista un numar de n perechi de pantofi de marimi diferite, dar nearanjati pe perechi. 24124f56y Care este numarul minim de pantofi care trebuie cercetati pentru a forma o pereche ?

Raspunsul este imediat. Folosim câte o cutie (initial goala) pentru fiecare marime. Este evident ca dupa asezarea în cutii a n+1 pantofi, o cutie va contine doi pantofi (m=n+1 k=1

Exemplul 2. Se considera un vector a=(a₁,...,a_n) de numere naturale. Se cauta indicii i<j cu a_i+...+a_j multiplu de n

În continuare, pentru orice numar natural x, vom nota prin x clasa sa de echivalenta modulo n

Consideram sumele s_k=a₁+...+a_k pentru k=1,...,n. Fie s_k clasele de echivalenta corespunzatoare.

Deosebim doua situatii:

daca exista k cu s_k , atunci o solutie este (i,j)=(1,k)

în caz contrar, este clar ca s₁,...,s_n . Conform principiului lui Dirichlet, vor exista indicii k<l cu s_k=s_l. Atunci o solutie este (i,j)=(k+1,l)

Exemplul 3. Pentru un numar natural n dat, caut un multiplu N al sau în a carei scriere obisnuita (în baza 10) apar numai cifrele si

Problema este asemanatoare celei precedente.

Pentru k=1,...,n consider numarul s_k a carui scriere în baza 10 este formata din k de , adica s₁=1 s₂=11 etc.; fie s_k clasa de echivalenta modulo n corespunzatoare.

La fel ca mai sus, deosebim doua situatii:

daca exista k cu s_k , atunci o solutie este chiar s_k

în caz contrar, este clar ca s₁,...,s_n . Conform principiului lui Dirichlet, vor exista indicii k<l cu s_k=s_l. Atunci o solutie este s_l-s_k, adica numarul în a carei scriere apar l-k de urmati de k de

Exemplul 4. Teorema lui Erdös.

Se dau (m-1)(n-1)+1 numere naturale oarecare. Sa se arate ca printre ele exista m care se divid unul pe altul, sau exista n care nu se divid între ele.

Vom aplica tot principiul lui Dirichlet, dar în plan.

Se ordoneaza mai întâi crescator numerele date.

Consider un caroiaj cu n-1 linii si m-1 coloane. Mai consider ca exista si linia imaginara cu numarul de ordine 0, pe care este plasat numarul 1.

Consideram pe rând numerele (în ordine crescatoare). Fiecare numar va fi plasat pe linia i cu i minim si cu proprietatea ca numarul curent se divide cu un numar aflat pe o linie anterioara.

Pentru exemplificare, sa consideram ca m n=4, iar numerele sunt:

x

Dupa plasarea primelor 8 numere, suntem în situatia:

Daca de exemplu x=72, atunci el ar trebui plasat pe a patra linie (inexistenta) si am obtine n=4 numere care se divid unul pe altul (de exemplu 3, 12, 24, 72).

Daca de exemplu x=35, atunci el ar trebui plasat pe a doua linie si am obtine m=5 numere care nu se divid între ele: 9, 12, 15, 33, 35.

Este important de notat ca pe fiecare linie numerele plasate apar în ordine crescatoare. Principiul lui Dirichlet ne asigura ca cel mai târziu dupa plasarea ultimului numar vom iesi din "cutie": aici caroiajul (n-1)×(m-1)

O varianta a principiului lui Dirichlet este urmatoarea:

Fie k1,...kn K=(k1+...+kn)/n si x un numar oarecare. Atunci: daca x<K i cu x<ki daca x>K i cu x>ki

Exemplul 5. Daca vârfurile unui decagon sunt etichetate distinct cu numerele 0,1,...,9 într-o ordine oarecare, atunci exista 3 vârfuri consecutive pentru care suma etichetelor este mai mare decât 13.

Fie x_i eticheta vârfului i, pentru i=1,...,10. Consideram numerele:

k₁=x₁+x₂+x₃

k₂=x₂+x₃+x₄

. . . .

k₉=x₉+x₁₀+x₁

k₁₀=x₁₀+x₁+x₂

Atunci K=(k₁+...+k_n)/n

Conform principiului lui Dirichlet, va exista i cu k_i>13,5>13.

Exemplul 6. Se considera m calculatoare si n imprimante (m>n). Fie a=numarul minim de legaturi calculator imprimanta ce trebuie stabilite, astfel încât daca orice n calculatoare doresc sa scrie simultan, acest lucru sa fie este posibil. Se cere sa se arate ca a n(m-n+1)

Fie k_i numarul de calculatoare legate la imprimanta i. Numarul de legaturi este deci a=(k₁+...+k_n)

Daca a<n(m-n+1), atunci (k₁+...+k_n)/n<m-n+1 Conform variantei principiului lui Dirichlet, exista o imprimanta i legata la cel mult m-n calculatoare, deci care nu este legata la cel putin n calculatoare; daca acestea vor sa scrie simultan, nu vor reusi. Contradictie.

Exercitiu. Sa se descrie o modalitate prin care problema poate fi rezolvata cu exact n(m-n+1) legaturi.