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.
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ă.
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(#aplicatia-7). Aplicaţia 7 (Bursele Agora, 2001)
h2(#aplicatia-7). Aplicaţia #7 (Bursele Agora, 2001)
bq. 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.
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.
h3. Rezolvare
Pornind asemănător ca în problema anterioară, impunem condiţiile că 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 în aplicaţia 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$, de unde $s(n) = n(n^2^ - 3n + 8) / 3$.
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ă.
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(#aplicatia-8). Aplicaţia 8: 'Thinking Backward':http://uva.onlinejudge.org/external/106/10623.html (UVA)
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>.
bq. 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$.
Restricţii: $n$ întreg fără semn reprezentabil pe $32$ biţi; $0 ≤ m < 100$; $0 ≤ n < 20 000$; $0 ≤ p < 100$.
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$.
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 $e(m) = 2m(m-1) + 2$ 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 $ec(m , n)$. Dacă valoarea $e(m, n-1)$ 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 $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ă valoarea $ect(m, n, p - 1)$ 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. 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$.
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.
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 $f(n) = An^3^ + Bn^2^ + Cn + D$ . 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.
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>.
h2(#aplicatia-9). Aplicaţia 9: 'Internet Problem Solving Contest, 2000':http://plg1.cs.uwaterloo.ca/~acm00/ipsc/
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ă ajunge 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 debine $O(k)$. Dacă numărul de puncte distincte este egal cu $l$, atunci numărul total de zone va creşte cu $l$. Astfel, algoritmul are complexitatea $O(n^2^ log n)$ dacă folosim sortarea sau $O(n^2^)$ dacă folosim tabela de dispersie.
Î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)
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ăţ 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.
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!
