Probleme de tăietură

h2(#1).Problema 1:

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

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.

Problema 2:

h2(#2).Problema 2:

Dându-se un număr natural N, se cere numărul maxim de regiuni în care N cercuri pot împărţi planul.
Rezolvare:

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.

Problema 3:

h2(#3). Problema 3:

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: