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.
!probleme-de-taietura?poza-1.bmp!

Rezolvare:

h3. Rezolvare:
 

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.

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!

Rezolvare:

h3. Rezolvare:
 

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.

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 !!]

Rezolvare:

h3. Rezolvare:
 

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.
h2(#4). Problema 4:

!probleme-de-taietura?poza-6.bmp!

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.

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!

Rezolvare:

h3. Rezolvare:
 

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!
h2(#6). Problema 6:
Pentru N plane determinaţi numărul maxim de zone în care poate fi împărţit spaţiul cu acestea.

Rezolvare:

h3. Rezolvare:
 

Î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ă.

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]]

Rezolvare:

h3. Rezolvare:
 

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
h2(#8). Problema 8:
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]]

Rezolvare:

h3. Rezolvare:
 

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.

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]]

Rezolvare:

 
h3. Rezolvare:
 

Î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).
h2(#10). Problema 10:

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]]

Rezolvare:

h3. Rezolvare:
 

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.

CERCURI.OUT
11
[Algoritmus, Cercuri[6]]

Rezolvare:

h3. Rezolvare:
 

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.