P R E S E K
List za mlade matematike, fizike, astronome in računalnikarje
ISSN 0351-6652 Letnik 18 (1990/1991) Številka 3 Strani 140-145
Boris Lavric:
VECKOTNIKI NA KVADRATNI MREŽI
Ključne besede: matematika, geometrija.
Elektronska verzija: http://www.presek.si/18/1036-Lavric.pdf
© 1990 Društvo matematikov, fizikov in astronomov Slovenije © 2010 DMFA - založništvo
VEČKOTNIKI NA KVADRATNI MREŽI
Na mreži iz kvadratkov ploščine 1 teži večkotnik, ki ima oglišča v križiščih te mreže. Koliko meri njegova ploščina? Nekaj spretnosti zadostuje, da jo določimo brez večjih težav; formula, ki jo nameravamo obravnavati v tem prispevku, pa nam delo zelo olajša. Ploščina je namreč enaka
p = r/2+k~l
kjer je r Čtevilo križišč mreže, ki leže na robu lika, k pa število križišč v notranjosti večkotnika.
Zapisano enakost je odkril leta 1899 matematik Pick in se zato imenuje Pickova formula. Lani je to formulo angleški dijak Skevington z majčkeno pomočjo svojega učitelja matematike posploši! na večkotnike z večkotniškimi luknjami. Ugotovil je, da ploščina večkotnika z I luknjami meri p — r/2+ +k + l- 1.
Najprej bomo postopoma dokazali Pickovo formulo, do posplošitve pa bo potem potreben le še korak.
1. Enostavni paralelogrami In trikotniki
Položimo na obravnavano kvadratno mrežo ravnino IR2 = HxIR, tako da bodo točke s celoštevilskimi koordinatami pokrile točno vsa križišča mreže Seveda tedaj križišča tvorijo množico Z — TLx~Ei.
Namenimo zdaj nekaj besed paralelogramom z oglišči v 1?. Naj bo P takšen paralelogram. Ta določa novo mrežo, sestavljeno iz skladnih parafelo-gramov, ki jih dobimo z vzporednimi premiki paralelograma P (glej sliko).
Označimo z M(P) množico vseh križišč te mreže in povabimo bralca, da dokaže naslednji trditvi
TI Množica M(P) je vsebovana v
T2 Tri različne točke iz TL1 so oglišča treh različnih paralelogramov
rs 24 k = 39
M(Pi) =
Pl. Pi in P3. Vsi trije določajo
= M(P2)= M(P3).
m^eže z /strm/ križišči, torej:
Naj ima paralelogram P eno oglišče v točki 0 — (0,0), dve drugi pa v točkah A in B. Z uporabo rezultata druge trditve vidimo, da se celoštevllski večkratniki vektorja OA končajo v tistih točkah množice M(P), ki ležijo na nosilki daljice OA, Podobno velja za celoštevilske večkratnike vektorja OB. Od tod hitro sledi, da konci vektorjev oblike
mOA + nOB. m, n G Z	{*)
tvorijo množico M(P).
Enostavni paralelogram! in trikotniki Slika 1.	Slika 2.
Naslednja definicija nam bo skrajšala nadaljnje pisanje. Paralelogram (oziroma trikotnik) z oglišči v Z2 je enosfafer), Če razen ogliSC ne vsebuje nobene točke iz H?.
Bralec se bo bfez težav prepričal o naslednjih lastnostih enostavnih pa-ralelogramov in trikotnikov.
T3 če je trikotnik z oglišči A, B, C £ enostaven, so vsi para lelog ram i z oglišči v točkah A, B in C enostavni.
T4 Paralelogram P z oglišči v
J? je enostaven natanko takrat, kadar
množica M(P) sovpada z
Ploščino p trikotnika z oglišči A =: (ai.aj), B = (faj, fcjJ.C = (ci, cj) lahko izračunamo po znani formuli
2p =| ai(fc2 ~ c2) + t>i(c2 - a2) + ci(a2 - b2) |	(F)
Ce
oglišča leže v množici
je na desni strani formule celo število, torej ploščina takšnega trikotnika meri vsaj 1/2. Kateri trikotniki imajo ploščino enako 1/2? Odgovor da naslednji izrek.
IZREK 1. Trikotnik z oglišči v H?
ima ploščino enako 1/2 natanko
takrat, kadar je enostaven.
Dokaz. Denimo, da trikotnik z oglišči A, B, C € H? ni enostaven. Potem vsebuje vsaj eno točko D £ S2, ki ni njegovo oglišče. Če D leži v notranjosti trikotnika ABC, ta razpade na trikotnike ABD.BCD in CAD, zato meri njegova ploščina vsaj 3/2, Če pa D leži na stranici trikotnika ABC, je ta sestavljen iz dveh manjših, zato njegova ploščina meri vsaj 1, Torejje trikotnik ABC s ploščino 1/2 nujno enostaven.
Naj bo zdaj trikotnik z oglišči A, B .C E enostaven in P paralelogram z oglišči A, B, C in D. Po trditvi T3 je tudi paralelogram P enostaven, torej T 4 pove, da velja M (P) = ti2.
Brez škode za splošnost dokaza smemo privzeti, da oglišče C leži v izhodišču O — (0,0). Ker konci vektorjev oblike (*) tvorijo 1K7, obstajata tak! celi števili m in n, da velja
mOA + nOB = OS. kjer je 5 = (1, 0) Za A — (ai, a2) in 8 = (£>i, ¿2) je zato
maj + nb\ — 1 ma2 + nt>2 — O
Od tod brez težav dobimo enakost)
m(aib2 - ajbi) = b2 n(aib2 - 92 ¿1) = ~a2
ki povesta, da celo število
d — a\b2 —
deli ¿>2 'n a2- namesto točke S vzamemo točko T = (0, 1), na enak način kot prej vidimo, da c/ deli tudi aj in bi- Potem pa je d = a\b2 — fci deljiv z d7 in zato enak -I, 0 aft 1, Ploščina trikotnika ABC je različna od nič in po formuli (F) meri
p = (i/ž) | 3162-32^1 |=| d | /2 torej je enaka 1/2. S tem je dokaz sklenjen.
2. Pickova formula in njena posplošitev
Dokaz Pickove formule bomo naslonili na prvo poglavje in na članek Triangulacije večkotnikov iz te številke Preseka.
Naj bo r točk iz S2 na robu večkotnika z oglišči v E , k pa v njegovi notranjosti. Napravimo triangulacijo z oglišči v teh r + k točkah. Vsak trikotnik iz triangulacije ima le oglišča v %2, zato je enostaven in ima po izreku 1 ploščino enako 1/2. Izrek 2 iz prej omenjenega Članka pove, da je v triangulaciji r + 2k — 2 trikotnikov, torej meri ploščina večkotnika p = = r/2 + k - 1.
Pickova formula je tu, njeno posplošitev pa strnimo v naslednji izrek.
IZREK 2. Večkotnik z oglišči v 1? naj ima I večkotniSkih lukenj, ki se ne dotikajo ena druge aH roba večkotnika in imajo oglišča v E2. Če je r točk množice 1? na robu preluknja nega večkotnika, k pa v njegovi notranjosti, meri njegova ploščina
p = r/2+ k + /- 1
Dokaz. Označimo večkotniSke luknje z Vi, V2.....Vf, nepreluknjani več-
kotnik pa z Vq. Naj r; točk iz ¡E2 leži na robu večkotnika V;(/ = 1,2, ..,/). k; točk iz Z2 pa v njegovi notranjosti. PreŠtejmo točke iz 'S?- narobu preluk-njanega večkotnika:
r = ro + n + ,.. + r/ nato pa še vse točke iz 7L1, ki ležijo v notranjosti neprduknjanega večkotnika
*o = h+ (m + +... + (n + k1)
Po Pickovi formuli je ploščina V/ enaka p; = r,j2 I kj - 1, zato ploščina preluknjanega večkotnika meri
P = PO ~ (Pl + ... + Pi) = = ro/2 +k0-l- (a/2 + ... + r,/2 + fcj + ... + k,) + I =
= (rb + Jl + .., + r,)f 2+ k + I — 1 = r/2 + /t + / — 1
Izrek je dokazan, bralca pa čaka še nekaj nalog
1. Dokaži, da enakostraniČni trikotnik ne more imeti vseh treh ogiiSč v
2.	Naj ima daljtca le krajišči A in B v J,2, Potem obstaja tak C E 7?. da je trikotnik ABC enostaven.
3.	Poišči vsaj en preluknjani kotnik i ogtišči v X2 in s ploščino p — 3*
4.	Doka£if da meri ploščina preluknjanega večkotnika z / večkotniškimi luknjami in z ogliŠči v s2 vsaj (5/ -f l)/2 \n da se ta ocena ne da izboljšati»
Boris Lavrič
Opomba: O Pickovi formuli je pisal tudi L Pucelj v Preseku P-V/L
VEČKOTNIKI NA KVADRATNI MREŽI - Rešitve s str. 140
1.	Kvadrat dolfine vsake daljice s krajišči v E2 je po Pitagorovem izreku celo ftevilo. Denimo, da ima enakostranični trikotnik s stranico dolžine a vsa ogliiča v Potem je njegova ploščina p — 3/4 iracionalno število, ker velja a2 G 2! Toda po formuli (F) je dvakratnik ploSČine p celo Število. Oboje hkrati ni mogoče, torej trditev velja.
2.	Vzporedno premaknimo daljico AB, tako da A preide v A' — (0,0). B pa v B' — (m,n). Seveda sta m in n celi Števili. Razen krajiSč na daljici A'B' ni točk iz Z2, zato sta Števili m in n tuji. Res, v nasprotnem primeru bi namreč na A'B' ležala tudi točka (m/d, n/d), kjer je d največja skupna mera števil m in rt.
Ker sta števili m in n tuji, obstajata taki celi števili p in q, da velja pm + qn = 1. Postavimo C — (—q, p).
Po formuli (F) ploSčina trikotnika A'B'C' meri
p = (l/2)jpm+gn |=l/2
torej je trikotnik A' B'C' po izreku 1 enostaven, Premaknimo zdaj A' B'C' nazaj, tako da A1 B'C' preide v ABC, in iskana točka C je tu.
3.
4, Vsaka luknja ima vsaj tri ogligča, zato ima preluknjani večko-tnik na robu vsaj 3/ + 3 točke iz Po izrek« 2 tedaj za njegovo ploščino velja
p = rji + k + I — 1> > (3/ + 3)/2 + 1 — 1 = = (5/ l)/2
Na sliki desno je načrtan trikotnik z / luknjami in s ploščino
p = (5/ + l)/2
torej se ocene res ne da izboljšati.
Boris L a vrič