Probleme cu puncte laticiale

(Categoria Matematică, Autor Cosmin Negruşeri)

• Conţinut
• Introducere
• Problema 1
• Bibliografie

Introducere

Articolul de faţă se va concentra pe probleme în care vor apărea puncte de coordonate întregi care sunt numite puncte laticeale. Sursele [1] şi [2] menţionate în bibliografie conţin câte un capitol despre puncte laticeale care deşi sunt mai matematice decât acest articol pot fi interesante pentru un elev, în pregătirea pentru olimpiadă. Să vedem acum câteva probleme ce au apărut pe la concursurile de programare.

Problema 1

Să se determine numărul de puncte de coordonate întregi prin care trece segmentul determinat de punctele (0, 0) şi (M, N). De exemplu, pentru M = 9 şi N = 12 pe segment vor fi 4 puncte de coronate întregi.

Rezolvare

Putem considera doar cazurile în care 0 <= N <= M, daca N = 0 atunci evident avem M + 1 puncte pe segment. Astfel trebuie să rezolvăm doar cazul în care 1 <= N <= M.
Evident că orice punct (x, y) pentru a fi pe segmentul nostru trebuie să satisfacă ecuaţia y = M/N x.Această ecuaţie are ca soluţie un număr natural doar dacă Mx se divide cu N, de aici dacă D = cmmdc(N, M) atunci x se divide cu N/D, deci x de forma kN/D => y = kM/D. Pentru ca punctul (x, y) să aparţină segmentului, trebuie ca 0 <= x <= N şi 0 <= y <= M astfel 0 <= k <= D. Deci numărul de puncte de pe un segment de la (0, 0) la (N, M) este egal cu cel mai mare divizor comun al numerelor M şi N la care adăugăm 1. Putem determina acest număr în complexitate în O(log (N + M)).

Problema 2

Se dă un triunghi cu vârfurile de coordonate întregi. Se cere să se determine numărul de puncte de coordonate întregi ce se află în interiorul triunghiului sau pe laturile lui. De exemplu un triunghi cu vârfurile de coordonate (1, 5), (5, 1) şi (6, 6) are 16 puncte în interior.

Bibliografie

• Buşneag, Maftei, Teme pentru cercurile şi concursurile de matematică ale elevilor, Scrisul Românesc, Craiova, 1983
• Iaglom, Iaglom, Probleme neelementare tratate elementar, ed tehnică, Bucureşti, 1962
• WolframMathWorld
• FAQs
• Geometry Algorithms