In primul rand felicit toti concurentii, incepand cu cei ce au obtinut
punctajul maxim.
Oricum, cei ce nu au rezolvat problema nu trebuie sa fie prea "mahniti",
pentru ca rezolvarea problemei necesita cunoasterea "Principiului lui
Dirichlet", principiu pe care o sa vi-l prezint cu aceasta ocazie.
Oricum, se pare ca cel putin 2 surse care au obtinut punctaj maxim nu au
folosit acest principiu, dar asta nu inseamna ca nu este foarte folositor
in multe probleme. Una dintre surse este a Irinei Dumitrascu, care a folosit
metoda backtracking (sper sa nu ma fi inselat) iar cealalta este a lui
Cristian Opincaru care a folosit algoritmi probabilisti (aici nu ma insel
sigur, ca prea este random la tot pasul...). Oricum algoritmii probabilisti
sunt o "arma" destul de buna pentru concursurile de programare (folosita si
de mine in cateva ocazii cu mult succes), care te poate ajuta in situatia in
care nu cunosti algoritmul exact de rezolvare (cum este si cazul de fata) sau
care poate fi folosita ca alternativa la backtracking sau euristici. Oricum
daca va intereseaza pot sa postez pe lista un articol despre acest subiect.
Dar sa revenim la oile noastre... Adica ale lui Dirichlet.
In continuare o sa puteti citi un articol despre "Principiul lui Dirichlet",
articol preluat in cea mai mare parte din articolul "Principiul cutiei al lui
Dirichlet" publicat de prof. Horia Georgescu in "Gazeta de Informatica",
Nr.9-10/1994. Tot aici veti gasi si rezolvarea problemei date.
Principiul Cutiei al lui DIRICHLET
----------------------------------
"Principiul Cutiei" sau "Principiul lui Dirichlet" sau mai complet
"Principiul Cutiei al lui Dirichlet" a fost enuntat de matematiceanul
Peter Gustav Lejeune Dirichlet (1805-1859):
"Se considera m obiecte care trebuie plasate in n cutii, precum
si un numar natural k cu m>kn. Atunci pentru orice astfel de
plasare va exista o cutie ce va contine cel putin k+1 obiecte."
Principiul este evident, dar in acelasi timp el este de o importanta
deosebita, servind la rezolvarea multor probleme de ordin matematic.
Voi da exemple in acest articol de mai multe probleme ce se rezolva cu
principiul lui Dirichlet, printre care si problema propusa saptamana asta.
+-------------------------------------------------------------------------+
| Problema 1: Fie n un numar natural. Se cere sa se determine un multiplu |
| al sau format numai din cifre de 0 si 1. |
+-------------------------------------------------------------------------+
Rezolvarea problemei se bazeaza bineinteles pe principiul lui Dirichlet.
Pentru aceasta vom considera numerele formate numai din cifre de 1: 1,11,111,
1111,......., 111.....1
|_______|
|
de n ori
Pentru fiecare din aceste n numere aflam restul impartirii la n.
Daca gasim un astfel de numar care la impartirea cu n sa dea restul 0,
problema este rezolvata, solutia fiind chiar numarul in cauza.
Daca nici un astfel de numar nu da restul 0 prin impartirea la n, atunci,
aplicand "Principiul lui Dirichlet" pentru n obiecte (care vor fi resturile),
n-1 cutii (anume resturile posibil de obtinut, de la 1 la n-1) si k=1, atunci
rezulta faptul ca in cel putin o cutie vom avea 2 obiecte, deci cel putin
2 numere vor da acelasi rest prin impartirea cu n.
Fie aceste numere 11.....1 si 11.....1, cu a<b.
|______| |______|
| |
de a ori de b ori
Atunci numarul de forma 11...100...0 va fi bineinteles divizibil cu n.
|____||____|
| |
de b-a ori de a ori
Rezolvarea arata ca problema are intotdeauna solutie.
Problema se poate generaliza pentru a obtine numere formate numai din
cifre de 0 si de b, b=1,2,...9.
+---------------------------------------------------------------------+
| Problema 2: Fie A o multime de n numere naturale. Sa se gaseasca o |
| o submultime a lui A, astfel incat suma elementelor din |
| submultime sa fie divizibila cu n. |
+---------------------------------------------------------------------+
Rezolvarea se bazeaza tot pe principiul lui Dirichlet, dar foloseste un
mic artificiu si anume construirea sumelor partiale.
Definim s[i]=suma a[j], unde vectorul a reprezinta multimea data, iar
j=1,i vectorul s este sirul sumelor partiale.
Calculam apoi pentru fiecare s[i], i=1,n, restul lui s[i] la n.
In caz ca gasim un s[k] cu s[k] mod n=0, atunci inseamna ca suma primelor
k elemente din multime este divizibila cu n si problema este rezolvata.
In caz contrar, aplicand "Principiul lui Dirichlet" ca si in problema
anterioara, vom avea doua sume partiale s[a], s[b] (pp. a<b) care vor da
acelasi rest la impartirea cu n. In acest caz suma numerelor de la i+1 la j
va fi divizibila cu n si problema este rezolvata total.
Si aceasta problema are intotdeauna solutie.
+-------------------------------------+
| Problema 3: "In vreme de razboi... |
+-------------------------------------+
Cine a rezolvat problema, si-a dat seama imediat ca aceasta problema este
chiar problema 2 de mai sus.
Pentru a crea bastionul 1, trebuie sa alegem din cei n soldati, un grup de
b1 soldati a caror "suma" sa fie divizibila cu n, deci chiar problema 2 de
mai sus.
Pentru a crea bastionul 2 trebuie sa alegem din cei n-b1 soldati ramasi,
un grup de b2 soldati a caror "suma" sa fie divizibila cu cei n-b1 soldati
ramasi, deci chiar problema 2 de mai sus aplicata pentru n=n-b1.
In acelasi mod se vor crea si celelalte bastioane.
+--------------------------------------------------------------------------+
| Problema 4: Un candidat la presedintie aflat in turneu electoral are |
| de vizitat un numar de l localitati intr-un numar de z zile. |
| Stiind ca in fiecare zi viziteaza cel putin o localitate, se |
| cere sa se arate ca exista un interval de zile consecutive |
| in care viziteaza exact 2z-l-1 localitati. (2z-l-1>0). |
+--------------------------------------------------------------------------+
Pentru fiecare i=1,z fie Ni numarul de localitati vizitate in primele i
zile.
Problema cere deci gasirea a doi indici i<j a.i. Ni+2z-l-1=Nj.
Acesti doi indici odata gasiti, solutia problemei va fi succesiunea de
zile i+1,i+2,....,j.
Pentru aceasta consideram 2 siruri de numere:
0<N1<N2<.....<Nz=l cu semnificatia descrisa mai sus si
N1+2z-l-1<N2+2z-l-1<...........<Nz+2z-l-1=l+2z-l-1=2z-1
In cele 2 siruri avem un numar de 2z numere naturale care se gasesc in
intervalul [1,2z-1]. Conform "Principiului lui Dirichlet" cel putin 2 din
aceste 2z numere sunt egale. Cum nu se poate ca ambele numere sa apartina
aceluiasi sir (datorita strictei egalitati), rezulta ca exista 2 indici i<j
a.i. Ni+2z-l-1=Nj si problema este rezolvata.
+--------------------------------------------------------------------+
| Problema 5: Se dau (m-1)(n-1)+1 numere naturale distincte. Sa sa |
| arate ca exista cel putin m dintre aceste numere care |
| se divid succesiv unul pe altul sau exista cel putin n |
| dintre aceste numere care nu se divid intre ele. |
| Se cere si succesiunea de numere ce constituie o solu- |
| tie a problemei. |
+--------------------------------------------------------------------+
Rezolvarea problemei presupune aplicarea principiului cutiei in 2
dimensiuni. Se incepe cu ordonarea crescatoare a celor (m-1)(n-1)+1 numere.
Se foloseste o matrice cu (m-1) linii si (n-1) coloane.
Numerele se vor scrie in matrice astfel:
- inscrierea unui numar pe o linie se face pe prima pozitie libera
- se considera ca exista si linia 0 pe care este inscris numarul 1, dar
pe care nu se pot inscrie numerele date
- numarul este inscris pe linia i daca i este cea mai mare valoare pentru
care numarul considerat se divide prin cel putin unul dintre numerele
de pe linia i+1.
Se remarca ca in orice moment numerele de pe aceasi coloana nu se divid
unul pe altul, iar pentru orice numar de pe linia i, exista o succesiune de
i numere care se divid unul pe altul. Cum in matrice pot fi inscrise doar
(m-1)(n-1) numere, iar noi avem (m-1)(n-1)+1 numere, rezulta din principiul
cutiei rezultatul din enuntul problemei.
Cristian Cadar
Bibliografie: Gazeta de Informatica Nr.9-10/1994,
____________ prof. Horia Georgescu, "Principiul cutiei al lui Dirichlet"
Sper ca articolul a fost de folos celor care nu stiau (sau nu stiau prea
multe) despre "Principiul lui Dirichlet". In caz ca aveti intrebari referi-
toare la acest articol puteti sa mi le adresati prin e-mail. De asemenea
daca v-a placut o problema in mod special puteti sa-mi trimiteti sursa pentru
evaluare. De asemenea recomand celor care pot face rost de Gazeta de Informa-
tica 9-10/1994, sa citeasca articolul respectiv, care este foarte interesant.
|
|
