h3. Rezolvare
Pentru un dreptunghi cu laturile paralele cu axele de coordonate de lungime $M$ şi lăţime $N$ avem că numărul de puncte situate strict în interiorul dreptunghiului este $(M – 1) x (N – 1)$, iar numărul de puncte situate pe laturile poligonului este $2 * M + 2 * N$. Dacă notăm cu $B$ numărul de puncte de pe laturi, cu $I$ numărul de puncte situate strict în interiorul unui dreptunghi şi cu $A$ aria dreptunghiului, observăm că
$I + B/2 – 1 = (M – 1) x (N – 1) + M + N – 1 = M x N = A$.
În cazul triunghiurilor dreptunghice ce au două catete vom vedea că această formulă se păstrează. Evident avem că $A = (M x N) / 2$. Pe ipotenuza triunghiului vom avea $D$ puncte $(D = cmmdc(M, N) + 1$, dar aceasta nu ne interesează pe moment), deci numărul de puncte de pe laturile triunghiului este $B = M + N + D – 1$.Numărul de puncte $I$ din interiorul triunghiului este numărul de puncte din interiorul dreptunghiului $(M - 1) x (N - 1)$ din care se scad punctele interioare de pe diagonala $D – 2$, rezultatul împărţindu-se apoi la $2$, de aici avem
$I = ((M - 1) x (N - 1) – D + 2) / 2$.
Pentru un dreptunghi cu laturile paralele cu axele de coordonate de lungime $M$ şi lăţime $N$ avem că numărul de puncte situate strict în interiorul dreptunghiului este $(M – 1) × (N – 1)$, iar numărul de puncte situate pe laturile poligonului este $2 * M + 2 * N$. Dacă notăm cu $B$ numărul de puncte de pe laturi, cu $I$ numărul de puncte situate strict în interiorul unui dreptunghi şi cu $A$ aria dreptunghiului, observăm că
$I + B/2 – 1 = (M – 1) × (N – 1) + M + N – 1 = M × N = A$.
În cazul triunghiurilor dreptunghice ce au două catete vom vedea că această formulă se păstrează. Evident avem că $A = (M × N) / 2$. Pe ipotenuza triunghiului vom avea $D$ puncte $(D = cmmdc(M, N) + 1$, dar aceasta nu ne interesează pe moment), deci numărul de puncte de pe laturile triunghiului este $B = M + N + D – 1$.Numărul de puncte $I$ din interiorul triunghiului este numărul de puncte din interiorul dreptunghiului $(M - 1) × (N - 1)$ din care se scad punctele interioare de pe diagonala $D – 2$, rezultatul împărţindu-se apoi la $2$, de aici avem
$I = ((M - 1) × (N - 1) – D + 2) / 2$.
Verificăm formula:
$I + B/2 – 1 = (M - 1) x (N - 1) / 2 – D/2 + 1 + M/2 + N/2 + D/2 + 1/2 = (M x N) / 2$.
$I + B/2 – 1 = (M - 1) × (N - 1) / 2 – D/2 + 1 + M/2 + N/2 + D/2 + 1/2 = (M × N) / 2$.
Deci formula se verifică şi pe astfel de triunghiuri.
Acum ne uităm la cel mai mic dreptunghi ce conţine un triunghi oarecare, acest dreptunghi poate fi împărţit în patru triunghiuri din care unul este cel iniţial, iar celelalte sunt trei triunghiuri dreptunghice pentru care catetele merg de-a lungul liniilor laticiale. Vom vedea că formula noastră se verifică şi pentru triunghiuri oarecare. Notăm cu $I{~d~}$ numărul de puncte înterioare dreptunghiului, $A{~d~}$ aria dreptunghiului şi $B{~d~}$ numărul de puncte de pe laturile dreptunghiului, cu $I{~1~}$, $I{~2~}$, $I{~3~}$ numărul de puncte din interiorul celor trei triunghiuri dreptunghice, $B{~1~}$, $B{~2~}$, $B{~3~}$ numărul de puncte de pe laturile celor trei triunghiuri, iar $A{~1~}$, $A{~2~}$ şi $A{~3~}$ ariile celor trei triunghiuri. Avem că $I = I{~d~} – I{~1~} – I{~2~} – I{~3~} – B + 3$ (trebuie să eliminăm punctele de pe laturile triunghiului interior şi să avem grijă de vârfurile acestui triunghi), $B = B{~1~} + B{~2~} + B{~3~} – B{~d~}$ iar $A = A{~d~} – A{~1~} – A{~2~} – A{~3~}$. De aici avem că $I + B/2 – 1 = I{~d~} – I{~1~} – I{~2~} – I{~3~} - B{~1~}/2 - B{~2~}/2 - B{~3~}/2 + B{~d~}/2 – 1 + 3 = (I{~d~} + B{~d~}/2 – 1) – (I{~1~} + B{~1~}/2 – 1) - (I{~1~} + B{~1~}/2 – 1) - (I{~1~} + B{~1~}/2 – 1) = A{~d~} – A{~1~} – A{~2~} – A{~3~} = A$, deci egalitarea este valabilă şi pentru triunghiuri oarecare.
---------------------------------------------
Acum aria triunghiului cu vârfurile (x1, y1), (x2, y2), (x3, y3) o putem afla uşor folosind formula lui Heron sau folosind
½ x abs( determinat( (x1, y1, 1), (x2, y2, 1), (x3, y3, 1)).
Numărul de puncte de pe laturile triunghiului poate fi determinat uşor folosind formula demonstrată în problema anterioară. Acum folosind formula I + B/2 – 1 = A putem afla numărul I şi problema e rezolvată prin întoarcerea numărului I + B. Complexitatea rezolvării este O(log N) unde N este valoarea maximă a coordonatelor.
Acum aria triunghiului cu vârfurile $(x1, y1)$, $(x2, y2)$, $(x3, y3)$ o putem afla uşor folosind formula lui Heron sau folosind
<tex> \frac {1} {2} \cdot | \left| \begin{array}{ccc}
x1 & y1 & 1 \\
x2 & y2 & 1 \\
x3 & y3 & 1 \end{array} \right| |. </tex>
Numărul de puncte de pe laturile triunghiului poate fi determinat uşor folosind formula demonstrată în problema anterioară. Acum folosind formula $I + B/2 – 1 = A$ putem afla numărul $I$ şi problema e rezolvată prin întoarcerea numărului $I + B$. Complexitatea rezolvării este $O(log N)$ unde $N$ este valoarea maximă a coordonatelor.
h2(#problema3). Problema 3 'Copaci':problema/copaci (infoarena)
Macarie, după ce a muncit o viaţă întreagă, se decide la bătrâneţe să se retragă pe o insulă pentru a-şi găsi liniştea interioară şi a se dedica naturii. Astfel el cumpără o insula pe care cultivă pomi fructiferi. Insula poate fi reprezentată ca un poligon (nu neaparat convex) într-un sistem de axe de coordonate pozitive. Pomii sunt plantaţi doar la coordonate naturale.
bq. Macarie, după ce a muncit o viaţă întreagă, se decide la bătrâneţe să se retragă pe o insulă pentru a-şi găsi liniştea interioară şi a se dedica naturii. Astfel el cumpără o insula pe care cultivă pomi fructiferi. Insula poate fi reprezentată ca un poligon (nu neaparat convex) într-un sistem de axe de coordonate pozitive. Pomii sunt plantaţi doar la coordonate naturale.
Macarie este interesat de numărul de copaci pe care îl poate planta strict in interiorul insulei. În acest scop el va furnizează copacii care determina insula (vârfurile poligonului).
De exemplu pentru poligonul dat prin vârfurile (0, 4), (0, 5), (2, 7), (2, 4), (6, 6) şi (4, 0) avem 12 puncte de coordinate întregi situate strict în interiorul poligonului.
De exemplu pentru poligonul dat prin vârfurile $(0, 4)$, $(0, 5)$, $(2, 7)$, $(2, 4)$, $(6, 6)$ şi $(4, 0)$ avem $12$ puncte de coordinate întregi situate strict în interiorul poligonului.
h3. Rezolvare
Formula I + B/2 – 1 = A prezentată mai sus se numeşte “Teorema lui Pick”, iar ea este valabilă şi pentru poligoane oarecare. Acest fapt este adevărat pentru că orice poligon are o diagonala înterioară, această diagonală îl împarte ăn două poligoane distincte, dacă notăm I1 şi I2 punctele interioare celor două poligoane, B1 şi B2 punctele de pe laturile celor două poligoane, A1 şi A2 laturile celor două poligoane şi D numărul de puncte de cooronate întregi de pe diagonală atunci dacă egalitatea ar fi fost satisfăcută pentru cele două poligoane atunci avem că B1 + B2 = B + 2D - 2, I = I1 + I2 + D – 2. De aici avem A = A1 + A2 = I1 + B1/2 – 1 + I2 + B2/2 – 1 = I1 + I2 + B/2 + D – 1 – 2 = I + B/2 – 1. Astfel putem demonstra prin inducţie că relaţia este satisfăcută pentru orice poligon.
Aria unui poligon poate fi calculată uşor folosind următoarea formulă A = suma xi yi+1 – xi+1 yi, unde punctul de indice n+1 este primul punct. Astfel obţinem un algoritm de complexitate O(N log (MaxX + MaxY)).
Formula $I + B/2 – 1 = A$ prezentată mai sus se numeşte 'Teorema lui Pick':http://en.wikipedia.org/wiki/Pick%27s_theorem, iar ea este valabilă şi pentru poligoane oarecare. Acest fapt este adevărat pentru că orice poligon are o diagonală înterioară, această diagonală îl împarte în două poligoane distincte, dacă notăm $I{~1~}$ şi $I{~2~}$ punctele interioare celor două poligoane, $B{~1~}$ şi $B{~2~}$ punctele de pe laturile celor două poligoane, $A{~1~}$ şi $A{~2~}$ laturile celor două poligoane şi $D$ numărul de puncte de cooronate întregi de pe diagonală atunci dacă egalitatea ar fi fost satisfăcută pentru cele două poligoane atunci avem că $B{~1~} + B{~2~} = B + 2 * D - 2$, $I = I{~1~} + I{~2~} + D – 2$. De aici avem $A = A{~1~} + A{~2~} = I{~1~} + B{~1~}/2 – 1 + I{~2~} + B{~2~}/2 – 1 = I{~1~} + I{~2~} + B/2 + D – 1 – 2 = I + B/2 – 1$. Astfel putem demonstra prin inducţie că relaţia este satisfăcută pentru orice poligon.
Aria unui poligon poate fi calculată uşor folosind următoarea formulă
<tex> A = \sum (x_i \cdot y_{i+1}-x_{i+1} \cdot y_i) </tex>, unde punctul de indice $n+1$ este primul punct. Astfel obţinem un algoritm de complexitate $O(N log (MaxX + MaxY))$.
h2(#problema4). Problema 4 (Marele Premiu Paco 2000)
Se dă o grilă de puncte laticeale de dimensiuni NxN, se cere să se determine numărul de pătrate care se pot forma astfel ca vârfurile lor să aparţină punctelor din grilă.
De exemplu pe o grilă de dimensiuni 3x3 există 6 pătrate.
Se dă o grilă de puncte laticeale de dimensiuni $N × N$, se cere să se determine numărul de pătrate care se pot forma astfel ca vârfurile lor să aparţină punctelor din grilă.
De exemplu pe o grilă de dimensiuni $3 × 3$ există $6$ pătrate.
h3. Rezolvare:
Un pătrat cu latura ce conţine L puncte, ce are laturile paralele cu axele de coordonate poate fi translatat în (N – L + 1) x (N – L + 1) poziţii diferite pe grila noastră.
Un pătrat cu latură ce conţine $L$ puncte, ce are laturile paralele cu axele de coordonate poate fi translatat în $(N – L + 1) × (N – L + 1)$ poziţii diferite pe grila noastră.
-------------------------------------------
Considerăm pentru un pătrat din mulţimea soluţiilor, dreptunghiul minim cu laturile paralele cu axele de coordonate ce conţine acest pătrat. Este uşor să vedem că acest dreptunghi este de fapt un pătrat. Într-un pătrat ce are L puncte pe latura înscrie L – 2 pătrate care nu au laturile paralele cu axele de coordonate.
Considerăm pentru un pătrat din mulţimea soluţiilor, dreptunghiul minim cu laturile paralele cu axele de coordonate ce conţine acest pătrat. Este uşor să vedem că acest dreptunghi este de fapt un pătrat. Într-un pătrat ce are $L$ puncte pe latura înscrie $L – 2$ pătrate care nu au laturile paralele cu axele de coordonate.
-------------------------------------------
Astfel vedem că numărul total de pătrate pe o grilă N x M este:
Astfel vedem că numărul total de pătrate pe o grilă $N × M$ este:
<tex> \[\sum_{L=2}^{N} {(N-L+1) \cdot (N-L+1) \cdot (L-1)}\] = \[\sum_{L=1}^{N-1} {(N-L) \cdot (N-L) \cdot L}\] = \[\sum_{L=1}^{N-1} {L \cdot N^2 - 2N \cdot L^2 + L^3}\] = N^2 \cdot \[\sum_{L=1}^{N-1} {L}\] - 2N \cdot \[\sum_{L=1}^N-1 {L^2}\] + \[\sum_{L=1}^{N-1} {L^3}\] = N^2 \cdot \frac {N(N-1)} {2} - 2N \cdot \frac {N(N+1)(2N+1)} {6} + {\frac {N(N+1)} {2}}^2 </tex>
Sumă după L de la 2 la N de (N–L + 1) x (N–L + 1) x (L–1) =
suma L de la 1 la N-1 de (N–L) x (N–L) x L = suma cu L de la 1 la N–1 de LN^2–2 NL^2 + L^3 = N^2 x suma L de la 1 la N-1-2N suma L de la 1 la N–1 de L^2 + suma de L de la 1 la N–1 de L^3 = N^2 x N(N-1)/2-2N n(n-1)(2n-1)/6 + [n(n-1)/2]^2.
Sumă după L de la 2 la N de (N – L + 1) × (N–L + 1) × (L–1) =
suma L de la 1 la N-1 de (N–L) × (N–L) × L = suma cu L de la 1 la N–1 de LN^2–2 NL^2 + L^3 = N^2 × suma L de la 1 la N-1-2N suma L de la 1 la N–1 de L^2 + suma de L de la 1 la N–1 de L^3 = N^2 × N(N-1)/2-2N n(n-1)(2n-1)/6 + [n(n-1)/2]^2.
Am folosit formulele cunoscute din manualul de clasa a 10-a:
<tex> \sum_{k=1}^n k = \frac {n(n+1)} {2} </tex>
<tex> \sum_{k=1}^n k^2 = \frac {n(n+1)(2n+1)} {6} </tex>
<tex> \sum_{k=1}^n k^3 = {\frac {n(n+1)} {2}}^2 </tex>
Suma cu I de la 1 la N de I = n(n+1)/2
Suma cu I de la 1 la N de I^2 = n(n+1)(2n+1)/6
Suma cu I de la 1 la N de I^3 = [n(n+1)/2]^2
