(toc){width: 25em}*{text-align:center} *Conţinut:*
* 'Problema 1':probleme-de-taietura#problema-1
* 'Problema 2':probleme-de-taietura#problema-2
* 'Problema 3':probleme-de-taietura#problema-3
* 'Problema 4':probleme-de-taietura#problema-4
* 'Problema 5':probleme-de-taietura#problema-5
* 'Problema 6':probleme-de-taietura#problema-6
* 'Problema 7':probleme-de-taietura#problema-7
* 'Problema 8':probleme-de-taietura#problema-8
* 'Problema 9':probleme-de-taietura#problema-9
* 'Problema 10':probleme-de-taietura#problema-10
* 'Problema 11':probleme-de-taietura#problema-11
* 'Problema 12':probleme-de-taietura#problema-12
* 'Aplicaţia 1':probleme-de-taietura#aplicatia-1
* 'Aplicaţia 2':probleme-de-taietura#aplicatia-2
* 'Aplicaţia 3 Really Strange':probleme-de-taietura#aplicatia-3
* 'Aplicaţia 4':probleme-de-taietura#aplicatia-4
* 'Aplicaţia 5':probleme-de-taietura#aplicatia-5
* 'Aplicaţia 6':probleme-de-taietura#aplicatia-6
* 'Aplicaţia 7 Bursele Agora 2001':probleme-de-taietura#aplicatia-7
* 'Aplicaţia 8 Thinking Backward':probleme-de-taietura#aplicatia-8
* 'Aplicaţia 9 Internet Problem Solving Contest 2000':probleme-de-taietura#aplicatia-9
* 'Aplicaţia 10 The partition of a cake':probleme-de-taietura#aplicatia-10
* 'Aplicaţia 11 Count the faces':probleme-de-taietura#aplicatia-11
* 'Aplicaţia 12 Cercuri,Algoritmus':probleme-de-taietura#aplicatia-12
* 'Bibliografie':probleme-de-taietura#bibliografie
În cadrul acestui articol vom prezenta câteva enunţuri, împreună cu soluţiile corespunzătoare, reprezentative pentru clasa problemelor de tăietură.
h2(#problema-1). Problema 1:
h2(#aplicatia-1). Aplicaţia #1
Pentru un număr natural N dat, se cere numărul maxim de regiuni în care se poate împărţi planul folosind N drepte.
p.,!probleme-de-taietura?poza-1.bmp!
bq. Pentru un număr natural $n$ dat, se cere numărul maxim de regiuni în care se poate împărţi planul folosind $n$ drepte.
h3. Rezolvare:
p=. !probleme-de-taietura?poza-1.bmp!
Mai întâi facem vom face două observaţii:
În configuraţia cu număr maxim de regiuni nu vom avea două drepte paralele, pentru că două drepte care se intersectează formează în plan patru regiuni, în timp ce două drepte paralele formează în plan doar trei regiuni.
De asemenea pentru a obţine un număr maxim de regiuni, nu vor exista trei drepte care să se intersecteze intr-un punct pentru că astfel am pierde o regiune triunghiulară formată din punctele de intersecţie ale celor trei drepte.
Dacă aceste două condiţii sunt îndeplinite vom vedea în continuare că orice configuraţie de N drepte împarte planul în acelaţi număr de regiuni. Notăm cu d(n) acest număr. Presupunem ca ştim pe d(n), să vedem acum ce se întâmplă dacă mai adaugăm o dreaptă.
Această nouă dreaptă va fi intersectată de celelalte drepte în n puncte distincte. Fiecare segment de dreaptă şi semidreaptă în care este împărţită a n+1-a taie o regiune veche in două regiuni noi. De aici tragem concluzia că d(n+1) = d(n) + n + 1. Deci d(n) = n + n – 1 + n – 2 + … + 2 + d(1). Astfel folosind indentitatea 1 + 2 + 3 + … + n = n(n+1)/2 obţinem d(n) = n(n + 1) / 2 + 1.
Menţionăm că problemele în care se cere maximizarea numărului de regiuni în care un pătrat, un triunghi sau un cerc este împărţit de n drepte, au aceiaşi soluţie.
!probleme-de-taietura?poza-2.bmp!
h3. Rezolvare
h2(#problema-2). Problema 2:
Mai întâi vom prezenta două observaţii:
Dându-se un număr natural N, se cere numărul maxim de regiuni în care N cercuri pot împărţi planul.
!probleme-de-taietura?poza-4.bmp!
# în configuraţia cu număr maxim de regiuni nu vom avea două drepte paralele, deoarece două drepte care se intersectează formează în plan patru regiuni, în timp ce două drepte paralele formează în plan doar trei regiuni;
# pentru a obţine un număr maxim de regiuni nu vor exista trei drepte care să se intersecteze într-un punct deoarece astfel am „pierde” o regiune triunghiulară formată din punctele de intersecţie ale celor trei drepte.
h3. Rezolvare:
Dacă aceste două condiţii sunt îndeplinite, vom vedea în continuare că orice configuraţie de $n$ drepte împarte planul în acelaşi număr de regiuni. Notăm cu <tex> d_{n} </tex> acest număr.
Este clar că oricare două cercuri trebuie să se intersecteze in exact două puncte, nu să fie tangente sau să nu se intersecteze deloc pentru că astfel am pierde o regiune, iar oricare trei cercuri nu se intersectează într-un punct.
Orice configuraţie care satisface această cerinţă va împărţi planul într-un număr maxim de regiuni.Vom nota cu c(n) numărul maxim de regiuni în care este împărţit planul de n cercuri. Să vedem ce se întîmplă când adăugăm un nou cerc la această configuraţie. Cercul nou va fi intersectat de cele n cercuri în 2n puncte distincte, şi astfel va fi împărţit în 2n arce. Fiecare dintre aceste arce împarte o zonă veche în două zone noi. De aici tragem concluzia că c(n + 1) = 2n + c(n). Astfel putem să îl scriem pe c(n) ca 2(n – 1) + 2(n – 2) + … + 2 + c(1). De aici folosind din nou identitatea 1 + 2 + … + n = n(n+1)/2 avem că c(n) = n(n-1) + 2.
Este evident că şi problema în care se cere maximizarea numărului de regiuni în care este împărţită suprafaţa unei sfere de n cercuri are aceiaşi soluţie.
!probleme-de-taietura?poza-5.bmp!
Presupunem că valoarea <tex> d_{n} </tex> este cunoscută; să vedem acum ce se întâmplă dacă mai adăugăm o dreaptă.
h2(#problema-3). Problema 3:
Această nouă dreaptă va fi intersectată de celelalte drepte în $n$ puncte distincte. Fiecare segment de dreaptă şi semidreaptă în care este împărţită a $(n + 1)$-a dreaptă taie o regiune veche în două regiuni noi. De aici obţinem că <tex> d_{n+1} = d_{n} + n + 1 </tex>.
Se dau n cercuri care se intersectează oricare două în două puncte şi nu există trei care se intersectează într-un punct, se cere să se determine numărul de zone în care este împarţit planul de aceste n cercuri. ( n <= 10^100)
[acm.uva.es 10519 !! Really Strange !!]
Aşadar, vom avea <tex> d_{n} = n + (n - 1) + (n - 2) + \ldots + 2 + d_{1} </tex>. Astfel, folosind identitatea <tex> 1 + 2 + 3 + \ldots + n = \dfrac{n(n+1)}{2} </tex>, obţinem <tex> d_{n} = \dfrac{n(n + 1)}{2} + 1 </tex>.
h3. Rezolvare:
Menţionăm că problemele în care se cere maximizarea numărului de regiuni în care un pătrat, un triunghi sau un cerc este împărţit de $n$ drepte, au aceeaşi soluţie.
Observăm ca sunt indeplinite condiţiile de maximalitate cerute mai sus, deci rezultatul e c(n), singura problema ce rămâne este aceea de implementare a operaţiilor cu numere mari.
p=. !probleme-de-taietura?poza-2.bmp!
h2(#problema-4). Problema 4:
h2(#aplicatia-2). Aplicaţia #2
Avem un număr natural N, vrem să determinăm numărul maxim de regiuni în care poate fi împărţit un plan de elipse.
bq. Dându-se un număr natural $n$, se cere numărul maxim de regiuni în care $n$ cercuri pot împărţi planul.
!probleme-de-taietura?poza-6.bmp!
p=. !probleme-de-taietura?poza-4.bmp!
h3. Rezolvare:
h3. Rezolvare
La fel ca şi la cercuri nici aici nu trebuie să avem elipse tangente, sau elipse care să nu se intersecteze, nu vor exista nici aici trei elipse care să se intersecteze într-un punct, aici elipsele trebuie să se intersecteze în patru puncte, dacă s-ar intersecta numai în două puncte atunci configuraţia nu ar avea număr maxim de regiuni.
Notăm cu e(n) numărul de care suntem interesaţi. Câte regiuni noi apar cand adăugam o nouă elipsă? Păi o nouă elipsă va fi intersectată de celelalte elipse ăn patru puncte de fiecare, deci e(n + 1) = 4n + e(n). De aici tragem concluzia că e(n) = 2 n(n - 1) + 2.
Este evident că oricare două cercuri trebuie să se intersecteze în exact două puncte, nu să fie tangente sau să nu se intersecteze deloc pentru că astfel am „pierde” o regiune, iar oricare trei cercuri nu au niciun punct comun.
!probleme-de-taietura?poza-7.bmp!
Orice configuraţie care satisface această cerinţă va împărţi planul într-un număr maxim de regiuni. Vom nota cu <tex> c_{n} </tex> numărul maxim de regiuni în care este împărţit planul de $n$ cercuri.
h2(#problema-5). Problema 5:
Să vedem ce se întîmplă când adăugăm un nou cerc la această configuraţie. Cercul nou va fi intersectat de cele $n$ cercuri în $2n$ puncte distincte, şi astfel va fi împărţit în $2n$ arce.
Dându-se un număr natural N, se cere numărul maxim de regiuni în care N triunghiuri pot împărţi planul.
!probleme-de-taietura?poza-8.bmp!
Fiecare dintre aceste arce împarte o zonă veche în două zone noi. De aici tragem concluzia că <tex> c_{n+1} = 2n + c_{n} </tex>.
h3. Rezolvare:
Astfel, putem să scriem valoarea <tex> c_{n} </tex> ca <tex> 2(n-1) + 2(n-2) + \ldots + 2 + c_{1} </tex>.
Repetând raţionamentul de la problemele anterioareavem că t(n+1) = 6n + t(n) => t(n) = 3n(n-1) + 2.
!probleme-de-taietura?poza-9.bmp!
De aici, folosind din nou identitatea <tex> 1 + 2 + \ldots + n = \dfrac{n(n+1)}{2} </tex>, avem că <tex> c_{n} = n(n-1) + 2 </tex>.
h2(#problema-6). Problema 6:
Este evident că şi problema în care se cere maximizarea numărului de regiuni în care este împărţită suprafaţa unei sfere de $n$ cercuri are aceeaşi soluţie.
Pentru N plane determinaţi numărul maxim de zone în care poate fi împărţit spaţiul cu acestea.
p=. !probleme-de-taietura?poza-5.bmp!
h3. Rezolvare:
h2(#aplicatia-3). Aplicaţia #3: '!! Really Strange !!':http://online-judge.uva.es/p/v105/10519.html (UVA)
În această problemă urmăm raţionamentul de până acum. Este evident că trebuie ca fiecare plan să se intersecteze cu fiecare, că oricare trei plane trebuie să nu se intersecteze într-o dreaptă, oricare trei plane nu trebuie să fie paralele cu o dreaptă şi oricare patru plane nu trebuie să se intersecteze într-un punct. Notăm p(n) numărul maxim de zone în care n plane împart spatiul. Când adaugăm un nou plan acesta va fi intersectat de celelalte plane în n drepte, drepte care după restrictiile care le-am pus nu vor fi două paralele sau trei care să se intersecteze într-un punct. Acest plan va fi împărţit în d(n) regiuni de aceste drepte din cauza restricţiilor impuse. Fiecare regiune din plan taie o zonă din spaţiu în două noi zone, de aici tragem concluzia că p(n + 1) = d(n) + p(n). Astfel avem p(n) = n(n-1)/2 + 1 + (n-1)(n-2)/2 + 1 + ...+2 * 1 / 2 + 1 + p(1) = ( n^2^ – n + (n-1)^2^ – (n-1)+... + 2^2^ – 2 + 1 – 1 + (n – 1) )/2+ 2 = ( n(n+1)(2n + 1)/6 – n(n+1)/2 + (n-1))/2 + 2 = (n^3^/3 + n^2^/2 + n/6 – n^2^/2 – n/2 )/2 + n + 1 = n^3^/ 6 + 5n/6 + 1. Am folosit identităţile 1 + 2 + … + n = n(n+1)/2 şi 1 + 2^2^ + 3^2^ + … + n^2^ = n(n+1)(2n+1)/6 care se pot demonstra uşor prin inducţie.
Menţionăm că dacă vrem să împărţim un cub, un cilindru o sfera etc în număr maxim de regiuni folosind n plane, formula se păstrează.
bq. Se dau $n$ cercuri care se intersectează oricare două în două puncte şi nu există trei care se intersectează într-un punct; se cere să se determine numărul zonelor în care este împarţit planul de aceste $n$ cercuri.
Restricţii: $n ≤ 10^100^$.
h2(#problema-7). Problema 7:
h3. Rezolvare
Dându-se un număr natural N, să se determine numărul maxim de zone în care pot împărţi spaţiul N sfere.
[Bursele Agora 2001[3]]
Observăm ca sunt indeplinite condiţiile de maximalitate cerute mai sus (vezi aplicaţia '#2':probleme-de-taietura#aplicatia-2), deci rezultatul este <tex> c_{n} </tex>. Singura problemă care rămâne este implementarea operaţiilor cu numere mari (dacă soluţia nu este implementată în _Java_).
h3. Rezolvare:
h2(#aplicatia-4). Aplicaţia #4
Pornim la fel ca la problema anterioară, oricare două sfere se vor intersecta şi nu vor exista trei sfere care să se intersecteze în acelaşi punct. Vom nota cu s(n) numărul maxim de regiuni în care poate fi împărţit spaţiul cu n sfere. Să vedem ce se întâmplă când adăugăm o sferă. Această sferă va fi intersectată de toate celelalte n sfere în n cercuri, pentru ca numărul de regiuni noi să fie maxim aceste cercuri vor împărţi sfera într-un număr maxim de regiuni, acest număr este c(n) aşa cum am discutat la problema 2. Obţinem astfel s(n + 1) = c(n) + s(n) = c(n) + c(n-1) + ... + c(1) = n(n-1) + 2 + (n-1)(n-2) + 2 + ... + 2 = 1 + 2^2 + .. + n^2 – 1 – 2 – 3 - .... – n + 2n => s(n) = n(n^2 – 3n + 8) / 3
bq. Avem un număr natural $n$. Vrem să determinăm numărul maxim de regiuni în care $n$ elipse pot împărţi planul.
h2(#problema-8). Problema 8:
p=. !probleme-de-taietura?poza-6.bmp!
Se dă un număr N care este numărul maxim în care poate fi împărţit planul de m elipse, n cercuri şi p triunghiuri. Se cere ştiind N să se determine toate valorile posibile pentru m, n şi p. (N întreg făra semn reprezentabil pe 32 de biţi, 0<=m<100, 0<=n<20000 şi 0<=p<100)
[10623 Thinking Backward [4]]
h3. Rezolvare
h3. Rezolvare:
La fel ca şi în cazul cercurilor, nici aici nu trebuie să avem elipse tangente, elipse care să nu se intersecteze sau trei elipse care să se intersecteze într-un acelaşi punct. Elipsele trebuie să se intersecteze în patru puncte; dacă s-ar intersecta numai în două puncte, atunci configuraţia nu ar avea număr maxim de regiuni.
Dacă am ştii pentru trei parametrii m, n şi p care este numarul maxim de părţi în care poate fi împărţit planul de m elipse, n cercuri şi p triunghiuri, atunci am putea incerca toate posibilitaţile pentru m, n şi p şi am găsi tripletele pentru rezultatul ar fie gal cu N, chiar am putea optimiza puţin acest algoritm iteram pe toate valorile de m şi p, astfel vom obţine o ecuaţie cu necunoscuta n astfel vom face doar 10000 de rezolvări de ecuaţii în loc de 200 000 000 de comparaţii.
Să vedem cum găsim numărul maxim de zone. Din nou oricare două figuri se intersectează în număr maxim de intersecţii, un cerc cu o elipsă în patru puncte, un cerc sau o elipsă cu un triunghi în şase puncte. Mai întâi punem cele m elipse in plan, ele vor împărţi planul în e(m) regiuni adică 2 m(m - 1) + 2. După aceea adaugăm cercurile. Să notam numarul maxim de zone în care n cercuri şi m elipse pot împărţi planul cu ec(m , n). Dacă ştim cât este e(m, n-1) atunci când adaugăm un nou cerc, acesta va fi intersectat de m elipse in 4m puncte şi de n-1 cercuri in 2(n – 1) puncte deci cercul va fi împărţit în 4m + 2(n-1) arce care vor împărţi tot atâtea regiuni care existau deja in câte două regiuni noi. Deci ec(m, n) = 4m + 2(n-1) + ec(m, n-1) = 4m + 2(n-1) + 4m + 2(n-2) + … + 4m + 2 + ec(m, 0) = 4m(n-1) + n (n-1) + 2m(m-1) + 2. Să vedem ce se întâmplă când adăugăm triunghiurile. Vom nota ect(m, n, p) numărul maxim de zone în care poate fi împărţit planul de m elipse, n cercuri şi p triunghiuri. Dacă ştim cu cat e egal ect(m, n, p - 1) , atunci când vom adăuga un nou triunghi acesta va intersecta cele m cercuri în 6m puncte, cele n elipse în 6n puncte şi cele p – 1 triunghiuri în 6(p – 1) puncte, astfel se vor forma 6m + 6n + 6(p-1) noi zone. Deci ect(m, n, p) = 6(m + n + p – 1) + ect(m, n, p – 1) = 6 (m + n + p – 1 + m + n + p – 2 + … m + n + 1) + ect(n, m, 0) = 6 (p-1)(m+n) + 3p(p-1) + 4m(n-1) + n(n-1) + 2m(m-1) + 2.
Notăm cu <tex> e_{n} </tex> numărul pe care îl căutăm. Câte regiuni noi apar cand adăugăm o nouă elipsă? O nouă elipsă va fi intersectată de fiecare dintre celelalte elipse în patru puncte, deci <tex> e_{n+1} = 4n + e_{n} </tex>. De aici obţinem că <tex> e_{n} = 2n(n-1) + 2 </tex>.
Problemele anterioare au fost cam matematice şi ele sunt numite de obicei de olimpici peiorativ ca “probleme de formulă”, majoritatea olimpicilor la informatică participă aici pentru că matematica nu le place aşa tare şi deci nici apariţia unor probleme ca cele de mai sus care sunt mai mult de mate decât de info nu îi prea încântă. Cum poate fi rezolvată o problemă de formulă fără să avem intuiţia matematică sau cunoţinţele matematice necesare? Păi câteodată elevii apelează la următorul truc: află primele câteva valori de mâna sau cu ajutorul unor algoritmi brute force şi apoi speră ca formula să fie de o anumită formă, de exemplu ar putea fi un polinom de un grad mic. Atunci avem ca f(N) = An^3 + Bn^2 + Cn + D. Afland primele câteva valori vom ştii valorile f(1), f(2), f(3), f(4). Dând lui n pe rand valorile 1, 2, 3 şi 4 putem face un sistem cu necunoscutele A, B, C şi D. Sau putem încerca să vedem cum se comportă şirul de numere, are o creştere polinomială sau exponenţială, apar valorile lui în triunghiul lui Pascal. Iar dacă rezolvăm problemele de acasă putem căuta valorile din şirul de soluţii pe internet pe pagina Eciclopedia Online a şirurilor de întregi [7] care este o resursă foarte utilă în cazul problemelor de acest gen .
p=. !probleme-de-taietura?poza-7.bmp!
h2(#problema-9). Problema 9:
h2(#aplicatia-5). Aplicaţia #5
Se dau N drepte în plan, fiecare dreaptă este dată prin două puncte prin care trece. Se cere să se determine pentru această configuraţie în câte zone este împărţit planul. (n <= 1000)
[Internet Problem Solving Contest 2000 [5]]
bq. Dându-se un număr natural $n$, se cere numărul maxim de regiuni în care $n$ triunghiuri pot împărţi planul.
h3. Rezolvare:
p=. !probleme-de-taietura?poza-9.bmp!
În sfârşit o problemă în care avem nevoie să folosim calculatorul şi talentul nostru de programatori . Vom folosi aceeaşi idee ce a apărut şi în celelalte probleme, adică numărăm pe rând în câte zone este împărţit planul de primele o dreaptă, doua drepte respectiv n drepte. Deci vom adăuga în ordine dreptele la configuraţia noastră. Când adăugăm o dreaptă ea va fi intersectată de dreptele deja adăugate în k puncte nu neapărat distincte, pe noi ne intereseaza punctele distincte, ca să facem acest lucru putem sorta punctele în O(k log k) sau să folosim o tabelă de dispersie şi astfel să aflăm în O(k) numărul de puncte distincte, daca acest număr e egal cu L atunci la numărul curent de zone vom adăuga L. Astfel algoritmul are complexitatea O(n^2 log n), sau dacă folosim tabele de dispersie O(n^2).
h3. Rezolvare
h2(#problema-10). Problema 10:
Repetând raţionamentul de la problemele anterioare avem <tex> t_{n+1} = 6n + t_{n} </tex>, de unde <tex> t_{n} = 3n(n-1) + 2 </tex>.
!probleme-de-taietura?poza-10.bmp!
h2(#aplicatia-6). Aplicaţia #6
Avem un tort în formă de pătrat de dimensiune 1000 x 1000. Folosim un cuţit pentru a tăoa tortul. Întrebarea este după o serie de tăieturi, în căte bucăţi am patriţionat tortul. Restricţii: Numărul de tăieturi nu va fi mai mare de 8. După tăieturi, lungimea oricărei laturi a partiţiei nu va fi mai mică decât unu. Coordonatele vârfurilor tortului vor fi (0,0)(0,1000)(1000,1000) (1000,0). Tăieturile se vor intersecta în două puncte cu marginile tortului. Următoarea imagine e un tort tăiat în zece bucăţi.
[acm.uva.es 527 The partition of a cake]
bq. Pentru $n$ plane determinaţi numărul maxim de zone în care poate fi împărţit spaţiul folosind aceste plane.
h3. Rezolvarea:
h3. Rezolvare
Este analoaga cu cea a problemei anterioare, datele sunt foarte mici în problema aceasta, probabil că autorii au vrut să facă problema accesibilă şi altor idei care folosesc împărţiri efective în poligoane a pătratului.
Şi în această problemă urmăm acelaşi raţionament. Este evident că trebuie ca fiecare plan să se intersecteze cu toate celelalte, că oricare trei plane trebuie să nu aibă nicio dreaptă comună, că oricare trei plane nu trebuie să fie paralele cu nicio dreaptă şi oricare patru plane nu trebuie să aibă niciun punct comun.
h2(#problema-11). Problema 11:
Notăm <tex> p_{n} </tex> numărul maxim de zone în care $n$ plane împart spaţiul. Dacă adăugăm un nou plan, acesta va fi intersectat de celelalte plane în $n$ drepte, drepte printre care, datorită restricţiilor pe care le-am pus, nu vom avea două paralele sau trei care să se intersecteze într-un punct.
!probleme-de-taietura?poza-12.bmp!
Acest plan va fi împărţit în <tex> d_{n} </tex> regiuni de aceste drepte datorită restricţiilor impuse. Fiecare regiune din plan taie o zonă din spaţiu în două noi zone, de unde <tex> p_{n+1} = d_{n} + p_{n} </tex>.
Se dă un graf planar prin noduri şi muchii, un graf este planar dacă există o modalitate de a îl desena în plan făra ca muchiile să se intersecteze decăt la capete. Se cere să se determine în căte regiuni împarte planul graful dat la intrare. Mai jos avem un exemplu de graf în care feţele sunt numerotate.
[10178 Count the faces [4]]
Astfel avem:
<tex> p_{n} = \dfrac{n(n-1)}{2} + 1 + \dfrac{(n-1)(n-2)}{2} + 1 + \ldots + \dfrac{2*1}{2} + 1 + p_{1} </tex>
<tex> p_{n} = \dfrac{n^2 - n + (n-1)^2 - (n-1) + \ldots + 2^2 - 2 + 1 - 1 + (n-1)}{2} + 2 </tex>
<tex> p_{n} = \dfrac{ \dfrac{n(n+1)(2n+1)}{6} - \dfrac{n(n+1)}{2} + (n-1)}{2} + 2 </tex>
<tex> p_{n} = \dfrac{ \dfrac{n^3}{3} + \dfrac{n^2}{2} + \dfrac{n}{6} - \dfrac{n^2}{2} - \dfrac{n}{2} }{2} + n + 1 </tex>
<tex> p_{n} = \dfrac{n^3}{6} + \dfrac{5n}{6} + 1 </tex>.
h3. Rezolvare:
Am folosit identităţile <tex> 1 + 2 + \ldots + n = \dfrac{n(n+1)}{2} </tex> şi <tex> 1 + 2^2 + 3^2 + \ldots + n^2 = \dfrac{n(n+1)(2n+1)}{6} </tex>, identităţi care se pot demonstra uşor prin inducţie.
Este interesant faptul că în această problemă nu ne este dată configuraţia în plan a grafului ci doar structura lui. Un graf il putem reprezenta în mai multe moduri în plan, astfel suntem duşi înspre ideea că există ceva formulă care rezolvă problema. O formulă întradevăr există şi se numeşte formula lui Euler pentru grafurile planare. Formula arată aşa f - m + n = 2, unde prin f am notat numărul de feţe, m numărul de muchii şi n numărul de vârfuri., dacă graful nostru e conex (formula include faţa exterioară). Această formulă poate fi demonstrată în foarte multe moduri. Dacă vreţi să vedeţi 19 metode de demonstrare puteţi să vizitaţi adresa [8]. O demonstraţie simplă ar fi prin inducţie pornind de la un arbore şi adăugând pe rând câte o muchie. La început avem o singură faţă, cea infinită, 1 – (n – 1) + n = 2 se verifică. Fiecare muchie adăugată împarte o faţă în două deci dacă aveam inainte f – m + n = 2 acum vom avea f1 – m1 + n = 2 unde f1 = f + 1 şi m1 = m + 1. Deci am demonstrate formula şi putem foarte uşor să rezolvăm problema, mai trebuie numai să avem grijă ca pentru fiecare componentă conexă număram faţa infinită.
Această formulă este adevarată şi în spaţiu pentru poliedre.
Menţionăm că dacă vrem să împărţim un cub, un cilindru, o sferă etc. în număr maxim de regiuni folosind $n$ plane, formula se păstrează.
h2(#problema-12). Problema 12:
h2(#aplicatia-7). Aplicaţia #7 (Bursele Agora, 2001)
!probleme-de-taietura?poza-13.bmp!
bq. Dându-se un număr natural $n$, să se determine numărul maxim de zone în care $n$ sfere pot împărţi spaţiul.
Se considera N cercuri in plan. Se cere să se determine numărul de zone finite în care cercurile date împart planul.
Exemplu
CERCURI.IN
4
90 110 50
130 70 30
155 45 15
165 115 65
CERCURI.OUT
11
[Algoritmus, Cercuri[6]]
h3. Rezolvare
h3. Rezolvare:
Pornim la fel ca în cazul problemei anterioare; oricare două sfere se vor intersecta şi nu vor exista trei sfere care să se intersecteze în acelaşi punct. Vom nota cu <tex> s_{n} </tex> numărul maxim de regiuni în care poate fi împărţit spaţiul cu $n$ sfere. Să vedem ce se întâmplă când adăugăm o sferă.
Contraexemple rezolvare normala
O rezolvare folosind geometria computaţională pare foarte grea, lucrurile simplificându-se mult daca abordam problema prin prisma unor noţiuni de teoria grafurilor.
Fiecare punct de intersectie va fi considerat un nod. Două noduri vor fi legate prin o muchie dacă există un cerc pe care sa se afle amândouă iar între ele să nu existe nici un alt punct de intersectie.
Acum vom folosi identitatea lui Euler: prezentată în problema anterioară. În problema noastră nu trebuie să numărăm şi faţa exterioară, deci formula folosita va fi F=M-V+1. Această formulă este adevarată doar in cazul unei singure componente conexe. Pentru mai multe componente, formula devine F=M-V+C, unde C este numărul de componente conexe.
O atenţie deosebită trebuie acordată punctelor de intersecţie prin care trec mai mult de două cercuri, pentru a nu le număra de mai multe ori. Putem rezolva aceasta problema prin sortarea punctelor de intersecţie ale unui cerc cu toate celelalte cercuri.
Deasemenea, este necesara eliminarea cercurilor identice (cu acelaşi centru şi raze egale). Din orice mulţime cu astfel de cercuri este păstrat doar un singur element.
Deoarece pentru fiecare cerc este necesara o sortare a punctelor de intersectie, complexitatea generala a algoritmului va fi O(N2*log(N))
Această sferă va fi intersectată de toate celelalte $n$ sfere în $n$ cercuri; pentru ca numărul de regiuni noi să fie maxim aceste cercuri vor împărţi sfera într-un număr maxim de regiuni; acest număr este <tex> c_{n} </tex> aşa cum am discutat în aplicaţia '#2':probleme-de-taietura#aplicatia-2.
h2(#bibliografie). Bibliografie:
Obţinem astfel:
<tex> s_{n+1} = c_{n} + s_{n} </tex>
<tex> s_{n+1} = c_{n} + c_{n-1} + \ldots + c_{1} </tex>
<tex> s_{n+1} = n(n-1) + 2 + (n-1)(n-2) + 2 + \ldots + 2 </tex>
<tex> s_{n+1} = 1 + 2^2 + \ldots + n^2 - 1 - 2 - 3 - \ldots - n + 2n </tex>, de unde <tex> s_{n} = \dfrac{n(n^2 - 3n + 8)}{3} </tex>.
# A.M. Iaglom, I. M. Iaglom, Probleme neelementare tratate elementat. Ed tehnică, Bucureşti, 1962
# I. Tomescu, Probleme de combinatorică şi teoria grafurilor, ed didactică şi pedagogică. Bucureşti, 1981
# Colecţia Ginfo
# acm.uva.es
# ipsc.ksp.sk
# algoritmus.org/index.php
# http://www.research.att.com/~njas/sequences/
# http://www.ics.uci.edu/~eppstein/junkyard/euler/
h2(#aplicatia-8). Aplicaţia #8: 'Thinking Backward':http://uva.onlinejudge.org/external/106/10623.html (UVA)
bq. Se consideră un număr $N$ care reprezintă numărul maxim de regiuni în care poate fi împărţit planul de către $m$ elipse, $n$ cercuri şi $p$ triunghiuri. Se cere să se determine toate valorile posibile pentru $m$, $n$ şi $p$.
Restricţii: $N$ întreg, fără semn, reprezentabil pe $32$ biţi; $0 ≤ m < 100$; $0 ≤ n < 20 000$; $0 ≤ p < 100$.
h3. Rezolvare
Dacă am cunoaşte pentru trei parametri $m$, $n$ şi $p$ care este numărul maxim de părţi în care poate fi împărţit planul de către $m$ elipse, $n$ cercuri şi $p$ triunghiuri, atunci am putea încerca toate posibilităţile pentru $m$, $n$ şi $p$ şi am găsi şi tripletele pentru care rezultatul ar fi egal cu $N$.
Am putea optimiza puţin acest algoritm iterând doar pe toate valorile $m$ şi $p$; astfel vom obţine o ecuaţie cu necunoscuta $n$ şi vom efectua $10 000$ de rezolvări de ecuaţii în loc de $200 000 000$ de comparaţii.
Să vedem cum găsim numărul maxim de zone. Din nou, oricare două figuri se intersectează în număr maxim de intersecţii, un cerc cu o elipsă în patru puncte, un cerc sau o elipsă cu un triunghi în şase puncte.
Mai întâi punem cele $m$ elipse în plan; ele vor împărţi planul în <tex> e_{m} = 2m(m-1) + 2 </tex> regiuni.
În continuare adăugăm cercurile. Să notăm numărul maxim de zone în care $n$ cercuri şi $m$ elipse pot împărţi planul prin <tex> ec_{m ,n} </tex>. Dacă valoarea <tex> e(m,n-1) </tex> este cunoscută, atunci, în momentul în care adăugăm un nou cerc, acesta va fi intersectat de $m$ elipse în $4m$ puncte şi de $n-1$ cercuri în $2(n-1)$ puncte, deci cercul va fi împărţit în $4m + 2(n-1)$ arce care vor împărţi tot atâtea regiuni care existau deja în câte două regiuni noi.
Aşadar, avem:
<tex> ec_{m,n} = 4m + 2(n-1) + ec_{m,n-1} </tex>
<tex> ec_{m,n} = 4m + 2(n-1) + 4m + 2(n-2) + \ldots + 4m + 2 + ec_{m,0} </tex>
<tex> ec_{m,n} = 4m(n-1) + n (n-1) + 2m(m-1) + 2 </tex>.
Să vedem ce se întâmplă când adăugăm triunghiurile. Vom nota prin <tex> ect_{m, n, p} </tex> numărul maxim de zone în care poate fi împărţit planul de $m$ elipse, $n$ cercuri şi $p$ triunghiuri.
Dacă valoarea <tex> ect_{m, n, p - 1} </tex> este cunoscută, atunci, în momentul în care vom adăuga un nou triunghi acesta va intersecta cele $m$ cercuri în $6m$ puncte, cele $n$ elipse în $6n$ puncte şi cele $p-1$ triunghiuri în $6(p-1)$ puncte, formându-se $6m + 6n + 6(p-1)$ noi zone.
Aşadar, obţinem:
<tex> ect_{m, n, p} = 6(m + n + p - 1) + ect_{m, n, p - 1} </tex>
<tex> ect_{m, n, p} = 6(m + n + p - 1 + m + n + p - 2 + \ldots + m + n + 1) + ect_{n, m, 0} </tex>
<tex> ect_{m, n, p} = 6(p-1)(m+n) + 3p(p-1) + 4m(n-1) + n(n-1) + 2m(m-1) + 2 </tex>.
Problemele anterioare au fost cam matematice şi ele sunt numite de obicei de olimpici peiorativ ca „probleme de formulă”. Majoritatea olimpicilor la informatică participă aici pentru că matematica nu le „place atât de mult” şi, deci, nici apariţia unor probleme ca cele de mai sus care sunt „mai mult de mate decât de info” nu îi prea încântă.
Cum poate fi rezolvată o problemă de formulă fără să avem intuiţia matematică sau cunoţinţele matematice necesare?
Uneori elevii apelează la următorul truc: determină primele câteva valori manual sau cu ajutorul unor algoritmi _brute force_ şi apoi speră ca formula să fie de o anumită formă; de exemplu ar putea fi un polinom de un grad mic. De exemplu, am putea presupune că formula este de forma <tex> f(n) = An^3 + Bn^2 + Cn + D </tex>. Calculând primele patru valori, vom cunoaşte valorile $f(1)$, $f(2)$, $f(3)$, $f(4)$. Atribuind pe rând lui $n$ valorile $1$, $2$, $3$ şi $4$ putem obţine un sistem de ecuaţii cu necunoscutele $A$, $B$, $C$ şi $D$.
O altă posibilitate este să încercăm să vedem cum se comportă şirul de numere: are o creştere polinomială sau exponenţială, apar valorile lui în triunghiul lui _Pascal_ etc. Dacă aveţi la dispoziţie o conexiune la internet (participaţi la un concurs online sau vă antrenaţi), puteţi căuta valorile din şirul de soluţii la '_Eciclopedia Online a şirurilor de întregi_':http://www.research.att.com/~njas/sequences/ care este o resursă foarte utilă în cazul problemelor de acest gen.
h2(#aplicatia-9). Aplicaţia #9: 'Internet Problem Solving Contest, 2000':http://plg1.cs.uwaterloo.ca/~acm00/ipsc/
bq. Se consideră $n$ drepte în plan, fiecare dreaptă este descrisă prin două puncte distincte aflate pe acea dreaptă. Se cere să se determine pentru această configuraţie în câte zone este împărţit planul.
Restricţii: $n ≤ 1000$.
h3. Rezolvare
În sfârşit o problemă în care avem nevoie să folosim calculatorul şi talentul de programator... Vom folosi aceeaşi idee ca şi în cazul celorlalte probleme, adică numărăm pe rând în câte zone este împărţit planul de prima dreaptă, primele două drepte până ajungem la toate cele $n$ drepte. Aşadar, vom adăuga în ordine dreptele la configuraţia noastră.
Când adăugăm o dreaptă, aceasta va fi intersectată de dreptele deja adăugate în $k$ puncte nu neapărat distincte; pe noi ne intereseaza punctele distincte şi, pentru a le număra, putem sorta punctele (în complexitate $O(k log k)$) sau putem folosi o tabelă de dispersie, caz în care timpul necesar devine $O(k)$.
Dacă numărul de puncte distincte este egal cu $m$, atunci numărul total de zone va creşte cu $m$.
Astfel, algoritmul are complexitatea $O(n^2^ log n)$ dacă folosim sortarea sau $O(n^2^)$ dacă folosim tabela de dispersie.
h2(#aplicatia-10). Aplicaţia #10: 'The partition of a cake':http://uva.onlinejudge.org/external/5/527.html (UVA)
bq. Avem un tort în formă pătratică; dimensiunea acestuia este $1000 x 1000$. Folosim un cuţit pentru a tăia tortul. Va trebui să determinăm în câte bucăţi a fost împărţit tortul după o serie de tăieturi. Numărul tăieturilor nu va fi mai mare de $8$. După tăiere, lungimea oricărei laturi a partiţiei nu va fi mai mică decât unu. Coordonatele vârfurilor tortului vor fi $(0,0) (0,1000) (1000,1000) (1000,0)$. Tăieturile se vor intersecta în două puncte cu marginile tortului. În imagine este prezentat un tort tăiat în zece bucăţi.
p=. !probleme-de-taietura?poza-10.bmp!
h3. Rezolvare
Soluţia este asemănătoare celei pentru problema anterioară. Dimensiunile datelor de intrare sunt foarte mici pentru problema aceasta; este posibil ca autorii să fi vrut ca problema să fie rezolvabilă şi folosind împărţiri efective în poligoane a pătratului.
h2(#aplicatia-11). Aplicaţia #11: 'Count the faces':http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=44&page=show_problem&problem=1119 (UVA):
bq. Se dă un graf planar descris prin noduri şi muchii (un graf este planar dacă există o modalitate de a-l desena în plan fără ca muchiile să se intersecteze decât în noduri). Se cere să se determine în câte regiuni împarte planul graful dat. În imagine este prezentat un graf în care feţele sunt numerotate.
p=. !probleme-de-taietura?poza-12.bmp!
h3. Rezolvare
Este interesant faptul că în această problemă nu este dată configuraţia în plan a grafului, ci doar structura lui. Un graf poate fi reprezentat în mai multe moduri în plan, ceea ce ne poate face să credem că ar exista o formulă pentru rezolvarea problemei.
Există într-adevăr o astfel de formulă care poartă denumirea de _formula lui Euler pentru grafurile planare_. Dacă graful este conex, această formulă este $f - m + n = 2$, unde prin $f$ am notat numărul de feţe, prin $m$ numărul de muchii şi prin $n$ numărul de vârfuri. Formula include faţa exterioară. Această formulă poate fi demonstrată în foarte multe moduri. Dacă doriţi să vedeţi 19 metode de demonstrare puteţi să vizitaţi '_Nouăsprezece demonstraţii ale formulei lui Euler: V-E+F=2_':http://www.ics.uci.edu/~eppstein/junkyard/euler/.
O demonstraţie simplă se bazează metoda inducţie matematice pornind de la un arbore şi adăugând pe rând câte o muchie. La început avem o singură faţă, cea infinită, deci ipoteza de inducţie se verifică: $1 - (n - 1) + n = 2$. Fiecare muchie adăugată împarte o faţă în două, deci, dacă inainte aveam $f - m + n = 2$, acum vom avea $f{~1~} - m{~1~} + n = 2$, unde $f{~1~} = f + 1$ şi $m{~1~} = m + 1$. Aşadar, am demonstrat formula şi putem foarte uşor să rezolvăm problema. Mai trebuie numai să avem grijă ca pentru fiecare componentă conexă să numărăm faţa infinită. Această formulă este adevarată şi în spaţiu pentru poliedre.
h2(#aplicatia-12). Aplicaţia 12: Cercuri (Algoritmus)
bq. Se consideră $n$ cercuri în plan. Se cere să se determine numărul zonelor finite în care cercurile date împart planul. Cercurile sunt date prin coordonatele centrului şi rază. În figură este prezentat un exemplu. Numărul căutat al zonelor este 11.
p=. !probleme-de-taietura?poza-13.bmp!
h3. Rezolvare
Problema nu poate fi rezolvată folosind aceleaşi idei deoarece aici apar cazuri speciale, cum ar fi punctele de tangenţă, faptul că nu toate cercurile trebuie să se intersecteze între ele (ceea ce duce la apariţia unor zone ca rezultat al unui ciclu de cercuri, aceste zone neputând fi numărate prin procedeul folosit).
O altă idee ar fi folosirea geometriei computaţionale, dar aceasta pare destul de anevoioasă; lucrurile se simplifică mult dacă abordăm problema prin prisma unor noţiuni de teoria grafurilor.
Fiecare punct de intersecţie va fi considerat un nod. Două noduri vor fi legate printr-o muchie dacă există un cerc pe care să se afle amândouă, iar între ele să nu existe niciun alt punct de intersecţie. Acum vom folosi identitatea lui _Euler_, prezentată în cadrul soluţiei problemei anterioare.
Pentru această problemă nu trebuie să numărăm şi faţa exterioară, deci formula folosită va fi $F = M - V + 1$. Această formulă este adevărată doar în cazul unei singure componente conexe. Pentru mai multe componente, formula devine $F = M - V + C$, unde $C$ este numărul de componente conexe.
O atenţie deosebită trebuie acordată punctelor de intersecţie prin care trec mai mult de două cercuri, pentru a nu le număra de mai multe ori. Putem rezolva această problemă prin sortarea punctelor de intersecţie ale unui cerc cu toate celelalte cercuri.
De asemenea, este necesară eliminarea cercurilor identice (cu acelaşi centru şi raze egale). Din orice mulţime formată din astfel de cercuri este păstrat doar un singur element.
Deoarece pentru fiecare cerc este necesară o sortare a punctelor de intersecţie, complexitatea algoritmului va fi $O(n^2^ log n)$.
h2(#bibliografie). Bibliografie
# A.M. Iaglom, I. M. Iaglom, _Probleme neelementare tratate elementar_, Editura Tehnică, Bucureşti, 1962;
# I. Tomescu, _Probleme de combinatorică şi teoria grafurilor_, Editura Didactică şi Pedagogică. Bucureşti, 1981;
# _Colecţia GInfo_;
