Documente online.
Zona de administrare documente. Fisierele tale
Am uitat parola x Creaza cont nou
 HomeExploreaza
upload
Upload




Principiul lui Dirichlet

Matematica


ALTE DOCUMENTE

Modelarea matematica in cercetarea operationala
Ecuatii si inecuatii logaritmice
Testul Kolmogorov-Smirnov
PLAN DE LECŢIE - Media aritmetica a doua sau mai multe numere
ECUATIA CURBEI PROGRESIVE DEDUCEREA ECUATIE
Var 99 SIII 2
FUNCŢIA DE GRADUL I
7 CRITERII DE DIVIZIBILITATE CU 7
PROBLEME CU MATRICE

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=(a1,...,an) de numere naturale. Se cauta indicii i<j cu ai+...+aj multiplu de n

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

Consideram sumele sk=a1+...+ak pentru k=1,...,n. Fie sk clasele de echivalenta corespunzatoare.

Deosebim doua situatii:

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

în caz contrar, este clar ca s1,...,sn . Conform principiului lui Dirichlet, vor exista indicii k<l cu sk=sl. 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 sk a carui scriere în baza 10 este formata din k de , adica s1=1 s2=11 etc.; fie sk clasa de echivalenta modulo n corespunzatoare.

La fel ca mai sus, deosebim doua situatii:

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

în caz contrar, este clar ca s1,...,sn . Conform principiului lui Dirichlet, vor exista indicii k<l cu sk=sl. Atunci o solutie este sl-sk, 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 xi eticheta vârfului i, pentru i=1,...,10. Consideram numerele:

k1=x1+x2+x3

k2=x2+x3+x4

. . . .

k9=x9+x10+x1

k10=x10+x1+x2

Atunci K=(k1+...+kn)/n

Conform principiului lui Dirichlet, va exista i cu ki>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 ki numarul de calculatoare legate la imprimanta i. Numarul de legaturi este deci a=(k1+...+kn)

Daca a<n(m-n+1), atunci (k1+...+kn)/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.


Document Info


Accesari: 3769
Apreciat: hand-up

Comenteaza documentul:

Nu esti inregistrat
Trebuie sa fii utilizator inregistrat pentru a putea comenta


Creaza cont nou

A fost util?

Daca documentul a fost util si crezi ca merita
sa adaugi un link catre el la tine in site


in pagina web a site-ului tau.




eCoduri.com - coduri postale, contabile, CAEN sau bancare

Politica de confidentialitate | Termenii si conditii de utilizare




Copyright © Contact (SCRIGROUP Int. 2024 )