Vom prezenta acum soluția problemei propuse în luna iunie. Pentru început să o reformulăm: practic, dorim să determinăm numărul punctelor cu coordonate întregi aflate în interiorul, pe laturile sau în vârfurile unui triunghi ale cărui vârfuri au și ele coordonate întregi. Punctele care au coordonate întregi se mai numesc puncte laticeale.
Să începem cu punctele de pe laturile triunghiului. Avem trei segmente și dorim să numărăm punctele laticeale de pe ele. Vom număra pentru fiecare segment în parte și vom scădea 3 (fiindcă fiecare vârf apare în două segmente, dar trebuie luat în considerare o singură dată când numărăm punctele de pe contur).
Orice segment poate fi translatat astfel încât una dintre extremitățile sale să fie în origine. Putem spune că numărul punctelor laticeale de pe segmentul delimitat de punctele (x1, y1) și (x2, y2) este identic cu numărul punctelor laticiale de pe segmentul delimitat de punctele (0, 0) și (x1 - x2, y1 - y2).
De asemenea, putem oglindi segmentul și numărul punctelor laticiale nu se modifică; astfel vom lucra doar cu numere pozitive. Segmentul va fi delimitat de punctele(0, 0) și (|x1 - x2|, |y1 - y2|). Pentru simplitate vom nota |x1 - x2| cu M și |y1 - y2| cu N. Avem acum problema simplificată de a determina numărul punctelor laticiale de pe un segment delimitat de origine și de un punct de coordonate pozitive (nu neapărat strict pozitive).
Mai putem executa o operație fără a modifica numărul punctelor laticeale. Numărul punctelor laticeale de pe segmentul delimitat de (0, 0) și (M, N) este egal cu cel al punctelor laticeale de pe segmentul delimitat de (0, 0) și (N, M). Așadar, putem considera că M este întotdeauna cel mult egal cu N.
Scăpăm repede de cazul în care M sau N este 0. În această situație, segmentul este orizontal sau vertical, iar numărul punctelor laticeale de pe el este N + 1 dacă M este 0, respectiv M + 1 dacă N este 0. Enunțul garantează că cele trei puncte nu sunt coliniare, ceea ce implică faptul că oricare două nu sunt identice, deci nu putem avea niciodată M = N = 0.
Fiecare punct (x, y) de pe segment satisface ecuația y = x · (N / M). Ne interesează doar punctele laticeale, deci cele pentru care x · N se divide cu M. Avem imediat două soluții posibile: x = 0 și x = M; ele corespund extremităților segmentului, dar mai pot fi și altele.
Să considerăm cel mai mare divizor comun D al numerelor M și N. Dacă x · N se divide cu M, atunci x trebuie să fie multiplu al lui M / D, deci să aibă forma k · (M / D). Putem verifica destul de ușor că dacă x are această formă, y este număr întreg.
y = x · (N / M)
y = k · (M / D) · (N / M)
y = k · (N / D)
Cum D este divizor al lui N, y este întreg. De asemenea, y trebuie să fie cuprins între 0 și N; ca urmare, valoarea maximă pentru k este D. Ca urmare, numărul variantelor pe care le avem la dispoziția este D + 1. Concluzionăm că numărul punctelor laticiale de pe un segment delimitat de origine și un punct (M, N) este dat de cel mai mare divizor comun al numerelor M și N, la care se adaugă 1.
Avem trei segmente pe conturul triunghiului. Luând în considerare translatările necesare, numărul total al punctelor laticeale de pe contur este:
cmmdc(|x1 - x2|, |y1 - y2|) + cmmdc(|x1 - x3|, |y1 - y3|) + cmmdc(|x2 - x3|, |y2 - y3|).
Pe fiecare latură avem un punct în plus față de valoarea celui mai mic divizor comun. Dar, acesta se "compensează" cu faptul că extremitățile apar în două segmente. Ar trebui să adăugăm și apoi să eliminăm trei puncte.
Să trecem acum la punctele din interiorul triunghiului. Pornim de la un dreptunghi ale cărui vârfuri sunt puncte laticeale și ale cărui laturi cu paralele cu axele de coordonate. Îl putem translata astfel încât să aibă un colț în origine și colțul opus să aibă coordonatele (M, N).
E foarte simplu să numărăm punctele de pe laturi; avem câte M + 1 puncte pe laturile orizontale și câte N + 1 pe cele verticale. Punctele din colțuri apar pe două laturi, deci numărul total al punctelor de pe conturul dreptunghiului este 2M + 2N.
În interior avem N - 1 linii a câte M - 1 puncte, (M - 1) · (N - 1) în total. Numărul total al punctelor ar fi (M - 1) · (N - 1) + 2M + 2N, adică MN - M - N + 1 + 2M + 2N = MN + M + N + 1. Observăm că MN este aria dreptunghiului; dacă notăm cu A această arie, cu C numărul punctelor de pe contur și cu I numărul punctelor din interior, atunci putem transforma formula anterioară:
I + C = A + C / 2 + 1
A = I + C / 2 - 1
Vom demonstra că această formulă se păstrează și pentru un triunghi ale cărui vârfuri sunt puncte laticeale.
Pasul următor este trecerea la un triunghi dreptunghic. Putem "tăia" dreptunghiul de la pasul anterior pe o diagonală. Această diagonală va fi ipotenuza dreptunghiului și va conține D + 1 puncte laticiale, unde D = cmmdc(M, N). Numărul punctelor de pe conturul triunghiului dreptunghic va fi C = M + N + D.
Numărul punctelor din interiorul triunghiului dreptunghic reprezintă jumătate din valoarea obținută scăzând din numărul punctelor din interiorul dreptunghiului, numărul punctelor de pe diagonală (ipotenuza triunghiului); pe ipotenuză avem D - 1 puncte (extremitățile nu se iau în considerare fiindcă sunt pe conturul triunghiului). Ajungem astfel la formula I = ((M - 1) · (N - 1) - D + 1) / 2.
Aria triunghiului dreptunghic este A = MN / 2. Verificăm acum dacă se păstrează formula A = I + C / 2 - 1. Avem:
A = I + C / 2 - 1
MN / 2 = ((M - 1) · (N - 1) - D + 1) / 2 + (M + N + D) / 2 - 1
MN / 2 = (MN - M - N + 1 - D + 1) / 2 + (M + N + D) / 2 - 1
MN / 2 = (MN - M - N - D + 2) / 2 + (M + N + D) / 2 - 1
MN / 2 = (MN - (M + N + D) + 2) / 2 + (M + N + D) / 2 - 1
MN / 2 = MN / 2 - (M + N + D) / 2 + 2 / 2 + (M + N + D) / 2 - 1
MN / 2 = MN / 2 - (M + N + D) / 2 + 1 + (M + N + D) / 2 - 1
MN / 2 = MN / 2 + 1 - 1
MN / 2 = MN / 2
Să trecem acum la un triunghi oarecare (ale cărui vârfuri sunt încă puncte laticeale). El poate fi înscris într-un dreptunghi. Acest dreptunghi este împărțit în patru triunghiuri (unele dintre acestea ar putea fi degenerate dacă triunghiul nostru are una sau două laturi paralele cu axele).
Unul dintre cele patru triunghiuri este cel dat inițial, iar celelalte trei sunt dreptunghice. Vom arăta acum că formula se păstrează. Vom nota cu AD, CD și ID aria dreptunghiului, numărul punctelor de pe conturul dreptunghiului, respectiv numărul punctelor din interiorul dreptunghiului, cu A1, A2 și A3 ariile celor trei triunghiuri, cu C1, C2 și C3 numărul punctelor de pe conturile lor, iar cu I1, I2 și I3 numărul punctelor din interiorul lor. Aria triunghiului inițial, numărul punctelor de pe conturul său și numărul punctelor din interior vor fi notate cu A, C și I.
Observăm imediat următoarele relații:
AD = A1 + A2 + A3 + A
CD + C = C1 + C2 + C3
ID = I1 + I2 + I3 + I + C - 3
Acestea spun că aria dreptunghiului este suma ariilor celor patru triunghiuri, că numărul punctelor de pe contururile celor trei triunghiuri dreptunghice este dat de suma punctelor de pe contururile dreptunghiului și ale triunghiului dat și că numărul punctelor din interiorul dreptunghiului este dat de numărul punctelor din interioarele celor patru triunghiuri la care se adaugă numărul punctelor de pe conturul triunghiului dat și din care se scade 3 (corespunzător celor trei vârfuri ale triunghiului dat care se află pe conturul triunghiului, dar și pe conturul dreptunghiului, nu în interiorul acestuia din urmă).
Relațiile pot fi rescrise astfel:
A = AD - A1 - A2 - A3
C = C1 + C2 + C3 - CD
I = ID - I1 - I2 - I3 - C + 3
Să verificăm acum formula:
A = I + C / 2 - 1
A = ID - I1 - I2 - I3 - C + 3 + C / 2 - 1
A = ID - I1 - I2 - I3 + 3 - C / 2 - 1
A = ID - I1 - I2 - I3 + 3 - (C1 + C2 + C3 - CD) / 2 - 1
A = ID - I1 - I2 - I3 + 3 - C1 / 2 - C2 / 2 - C3 / 2 + CD / 2 - 1
A = ID - I1 - I2 - I3 + 1 + 1 + 1 - C1 / 2 - C2 / 2 - C3 / 2 + CD / 2 - 1
A = ID + CD / 2 - 1 - I1 - C1 / 2 + 1 - I2 - C2 / 2 + 1 - I3 - C3 / 2 + 1
A = ID + CD / 2 - 1 - (I1 + C1 / 2 - 1) - (I2 + C2 / 2 - 1) - (I3 + C3 / 2 - 1)
A = AD - A1 - A2 - A3
Am demonstrat astfel că formula este valabilă și pentru triunghiuri oarecare.
Soluția problemei noastre va fi dată de numărul I + C, adică A + C / 2 + 1. Am arătat deja cum se calculeză C. Aria poate fi determinată fie folosind formula cu determinantul, fie formula lui Heron.
Formula utilizată este, de fapt, teorema lui Pick și a fost descoperită în 1899. Se poate arăta că ea este valabilă pentru orice poligon, nu neapărat convex.
