Univerzita Karlova v Praze. Matematicko-fyzikální fakulta. předmětu matematika. Mgr. Marie Dostálová. Pickova věta

Univerzita Karlova v Praze Matematicko-fyzik´aln´ı fakulta

´ ERE ˇ ˇ A ´ PRACE ´ ZAV CN Kurz Vyuˇ cov´ an´ı vˇ seobecnˇ e vzdˇ el´ avac´ıho pˇ redmˇ etu matematika

Mgr. Marie Dost´alov´a Pickova vˇ eta Konzultant z´ avˇ ereˇ cn´ e pr´ ace: RNDr. Anton´ın Slav´ık, Ph.D.

Praha 2013

ˇ Kurz je akreditov´an u MSMT na z´akladˇe § 25 a § 27 z´akona ˇc. 563/2004 Sb., o pedagogick´ ych pracovn´ıc´ıch a o zmˇenˇe nˇekter´ ych z´akon˚ u, a v souladu se z´akonem ˇc. 500/2004 Sb. Pod ˇc. j. 27 655/2012-25-591.

Chtˇela bych touto cestou podˇekovat sv´emu pˇr´ıteli za trpˇelivou technickou pomoc pˇri psan´ı t´eto pr´ace a za vytvoˇren´ı vˇetˇsiny obr´azk˚ u. Tak´e bych chtˇela podˇekovat RNDr. Anton´ınu Slav´ıkovi, Ph.D. za velice podnˇetn´e pˇripom´ınky. Velk´e d´ıky tak´e patˇr´ı m´ ym rodiˇc˚ um a sestˇre za proˇcten´ı koneˇcn´eho textu.

Prohlaˇsuji, ˇze jsem tuto z´avˇereˇcnou pr´aci vypracovala samostatnˇe a v´ yhradnˇe s pouˇzit´ım citovan´ ych pramen˚ u, literatury a dalˇs´ıch odborn´ ych zdroj˚ u. Beru na vˇedom´ı, ˇze se na moji pr´aci vztahuj´ı pr´ava a povinnosti vypl´ yvaj´ıc´ı ze z´akona ˇc. 121/2000 Sb., autorsk´eho z´akona v platn´em znˇen´ı.

V . . . . . . . . . . . . . . . . . . . . . . dne . . . . . . . . . . . . .

podpis

Obsah ´ Uvod

3

1 Kapitola pˇ r´ıklad˚ u 1.1 Zaˇc´ın´ame . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Pick˚ uv vzorec a ˇreˇsen´ı pˇr´ıklad˚ u . . . . . . . . . . . . . . . . . . .

5 5 8

2 D˚ ukazy a souvislosti 2.1 Prvn´ı d˚ ukaz Pickova vzorce . . . . . . . . . 2.2 D˚ ukaz Pickova vzorce pˇres u ´hly viditelnosti . 2.3 Tˇret´ı d˚ ukaz Pickova vzorce . . . . . . . . . . 2.4 Euler˚ uv vzorec . . . . . . . . . . . . . . . . 2.5 Dalˇs´ı v´ ysledky o mˇr´ıˇzov´ ych bodech . . . . .

. . . . .

15 15 19 21 22 26

3 Zobecnˇ en´ı a rozˇ s´ıˇ ren´ı 3.1 Zobecnˇen´ı pro rozmanitˇejˇs´ı tvary . . . . . . . . . . . . . . . . . . 3.2 Rozˇs´ıˇren´ı do prostoru . . . . . . . . . . . . . . . . . . . . . . . . .

31 31 33

Medailonek o Georgu Pickovi

35

Z´ avˇ er

37

Literatura

39

1

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

2

´ Uvod Dost´av´a se v´am do rukou pr´ace, kter´a si klade za c´ıl sezn´amit ˇcten´aˇre s Pickovou formul´ı neboli Pickov´ ym vzorcem pro v´ ypoˇcet obsahu. Tento vzorec nen´ı nijak sloˇzit´ y a mnoh´e moˇzn´a okouzl´ı svoj´ı eleganc´ı, jin´e moˇzn´a zaujme svoj´ı jednoduchost´ı. Profesor G. Pick publikoval vzorec pro v´ ypoˇcet obsahu jednoduch´eho mnoho´ uheln´ıku, kter´ y m´a vrcholy v mˇr´ıˇzov´ ych bodech, na konci 19. stolet´ı. Tomuto v´ ysledku se vˇsak dostalo vˇetˇs´ı pozornosti aˇz v druh´e polovinˇe dvac´at´eho stolet´ı. Od t´e body se objevuj´ı nejr˚ uznˇejˇs´ı zp˚ usoby jak Pick˚ uv vzorec dok´azat a nach´azej´ı se i zaj´ımav´e spojitosti Pickova vzorce s dalˇs´ımi oblastmi matematiky. V pr´aci uk´aˇzeme nˇekolik zp˚ usob˚ u jak Pick˚ uv vzorec dok´azat, naznaˇc´ıme souvisej´ıc´ı t´emata, uk´aˇzeme zobecnˇen´ı Pickova vzorce pro sloˇzitˇejˇs´ı tvary a v neposledn´ı ˇradˇe se dotkneme ot´azky, jestli je moˇzn´e nˇejak jednoduˇse rozˇs´ıˇrit Pick˚ uv vzorec pro v´ ypoˇcet obsahu prostorov´ ych tˇeles. Pr´ace tak´e obsahuje r˚ uznorod´e pˇr´ıklady, kter´e se daj´ı ˇreˇsit pomoc´ı Pickova vzorce. Se ˇzivotn´ım pˇr´ıbˇehem profesora Picka se ve struˇcnosti ˇcten´aˇr m˚ uˇze sezn´amit v medailonku na konci pr´ace.

3

4

Kapitola 1 Kapitola pˇ r´ıklad˚ u V cel´e pr´aci budeme mluvit o mˇr´ıˇzov´ ych bodech, proto nen´ı na ˇskodu jiˇz zde ˇr´ıci, co se za t´ımto pojmem skr´ yv´a. Mˇ r´ıˇ zov´ e body jsou takov´e body, kter´e maj´ı v kart´ezsk´e soustavˇe souˇradnic celoˇc´ıseln´e souˇradnice. Jedn´a se tedy o body z mnoˇziny Z × Z. Napˇr´ıklad [3,4] nebo [0, − 19].

1.1

Zaˇ c´ın´ ame

V prvn´ı podkapitole jsou pˇripraven´e pˇr´ıklady, jejichˇz ˇreˇsen´ı m˚ uˇzete naj´ıt v druh´e podkapitole. Zkuste se nad nimi zamyslet, propoˇc´ıtat je a aˇz pot´e se pod´ıvat, jak´e maj´ı ˇreˇsen´ı. Pˇ r´ıklad 1. Urˇcete obsahy troj´ uheln´ık˚ u vepsan´ ych do jednotkov´e ˇctvercov´e s´ıtˇe na obr´azku 1.1. Maj´ı nˇekter´e troj´ uheln´ıky shodn´ y obsah?

1

2

3

5

4

6

7

8

Obr´azek 1.1: Obr´azek k pˇr´ıkladu 1

Pˇ r´ıklad 2. Jak´e obsahy maj´ı obrazce vepsan´e do jednotkov´e ˇctvercov´e s´ıtˇe, kter´e jsou na obr´azku 1.2? Vˇsechny vrcholy obrazc˚ u jsou v mˇr´ıˇzov´ ych bodech.

Obr´azek 1.2: Obr´azek k pˇr´ıkladu 2

5

Pˇ r´ıklad 3. Jak´ y obsah maj´ı ryby vepsan´e do jednotkov´e ˇctvercov´e s´ıtˇe na obr´azc´ıch? Vˇsechny vrcholy jsou v mˇr´ıˇzov´ ych bodech.

Obr´azek 1.3: Obr´azek k pˇr´ıkladu 3

Obr´azek 1.4: Obr´azek k pˇr´ıkladu 3

Pˇ r´ıklad 4. Je moˇzn´e zakreslit rovnostrann´ y troj´ uheln´ık do ˇctvercov´e s´ıtˇe tak, aby jeho vrcholy leˇzely v mˇr´ıˇzov´ ych bodech? Pˇ r´ıklad 5. (pˇrevzato ze zdroje [4]) Uvaˇzujme troj´ uheln´ıky se z´akladnou d´elky 1 a v´ yˇskou d´elky 2, kter´e maj´ı vrcholy v mˇr´ıˇzov´ ych bodech. Kolika mˇr´ıˇzov´ ymi body proch´azej´ı hrany takov´ ych troj´ uheln´ık˚ u? Je to nˇejak´e pravidlo nebo je to n´ahoda? Pˇ r´ıklad 6. (pˇrevzato ze zdroje [4]) Uvaˇzujme troj´ uheln´ıky se z´akladnou d´elky 1 a v´ yˇskou d´elky 3, kter´e maj´ı vrcholy v mˇr´ıˇzov´ ych bodech. Kolik mˇr´ıˇzov´ ych bod˚ u a kde (na hran´ach, uvnitˇr troj´ uheln´ıku) takov´eto troj´ uheln´ıky nutnˇe obsahuj´ı? Pˇ r´ıklad 7. Kter´ y z n´asleduj´ıc´ıch obrazc˚ u m´a nejvˇetˇs´ı obsah?

Obr´azek 1.5: Obr´azek k pˇr´ıkladu 7

Pˇ r´ıklad 8. (pˇrevzato z [12]) Obd´eln´ık na obr´azku 1.6 byl rozdˇelen na 40×25 jednotkov´ ych ˇctvereˇck˚ u s vrcholy v mˇr´ıˇzov´ ych bodech. Nˇekter´e ze ˇctvereˇck˚ u byly odstranˇeny a z˚ ustal obrazec s uzavˇrenou hranic´ı, kter´a proch´az´ı vˇsemi 40×25 mˇr´ıˇzov´ ymi body. Jak´ y je obsah vybarven´eho obrazce? 6

Obr´azek 1.6: Obr´azek k pˇr´ıkladu 8 [a2 , b2 ]

[a1 , b1 ]

Obr´azek 1.7: Ilustrace k pˇr´ıkladu 9

Pˇ r´ıklad 9. Kolik je mˇr´ıˇzov´ ych bod˚ u na u ´seˇcce spojuj´ıc´ı mˇr´ıˇzov´e body [a1 ,b1 ] a [a2 ,b2 ]? Pˇ r´ıklad 10. (pˇrevzato ze zdroje [4]) Pˇr´ımka spojuj´ıc´ı body A [n,0] a B [0,n] m´a rovnici x−y = n. Na t´eto pˇr´ımce tedy leˇz´ı vˇsechny body tvaru [n−i, i], i ∈ Z. Mezi body A a B je n−1 tˇechto bod˚ u, oznaˇcme je X1 , . . . ,Xn−1 . Spoj´ıme-li vˇsechny tyto body s poˇca´tkem O [0,0], rozdˇel´ıme troj´ uheln´ık ABO na mal´e troj´ uheln´ıky, jak je naznaˇceno na obr´azku 1.8. Bude n´as zaj´ımat poˇcet mˇr´ıˇzov´ ych bod˚ u uvnitˇr jednotliv´ ych mal´ ych troj´ uheln´ık˚ u. Zˇrejmˇe dva mal´e troj´ uheln´ıky OAX1 a OXn−1 B pˇri os´ach x a y nebudou obsahovat uvnitˇr ˇza´dn´ y mˇr´ıˇzov´ y bod. Ale co ostatn´ı troj´ uheln´ıky OXi Xi+1 , i = 1, . . . ,n − 2? Dokaˇzte, ˇze pokud je n prvoˇc´ıslo, pak kaˇzd´ y ze zb´ yvaj´ıc´ıch mal´ ych troj´ uheln´ık˚ u obsahuje stejn´ y poˇcet mˇr´ıˇzov´ ych bod˚ u. Jak´ y je poˇcet mˇr´ıˇzov´ ych bod˚ u uvnitˇr kaˇzd´eho mal´eho troj´ uheln´ıku OXi Xi+1 , i = 1, . . . ,n − 2? Pˇ r´ıklad 11. (pˇrevzato z knihy [11]) Nakreslete do jednotkov´e ˇctvercov´e s´ıtˇe dva ˇctverce o stranˇe d´elky 5, jejichˇz vrcholy leˇz´ı v mˇr´ıˇzov´ ych bodech, jeden tak, aby obsahoval 36 mˇr´ıˇzov´ ych bod˚ u, a druh´ y tak, aby obsahoval 28 mˇr´ıˇzov´ ych bod˚ u. Nav´ıc dokaˇzte, ˇze ˇctverec o stranˇe d´elky 5, jehoˇz vrcholy leˇz´ı v mˇr´ıˇzov´ ych bodech, pokr´ yv´a maxim´alnˇe 36 mˇr´ıˇzov´ ych bod˚ u a minim´alnˇe 28 mˇr´ıˇzov´ ych bod˚ u. ˇ Pˇ r´ıklad 12. (pˇrevzato ze zdroje [4]) Ctverec o obsahu n2 , n ∈ N poloˇz´ıme n´ahodnˇe na ˇctvercovou jednotkovou mˇr´ıˇz. Ukaˇzte, ˇze ˇctverec nem˚ uˇze zakr´ yvat 2 v´ıc neˇz (n + 1) mˇr´ıˇzov´ ych bod˚ u. 7

B[0,n]

Xn−1 Xn−2

X1

A[n,0]

O

Obr´azek 1.8: Ilustrace k pˇr´ıkladu 10

Pˇ r´ıklad 13. (pˇrevzato z knihy [11]) Kolika zp˚ usoby lze rozmˇenit dolar na ˇctvrt’a´ky, deseticenty a pˇeticenty, pokud je dolar 100 cent˚ u a ˇctvrt’a´k 25 cent˚ u? Pˇ r´ıklad 14. (pˇrevzato z knihy [11]) Kolika zp˚ usoby lze rozmˇenit D dolar˚ u na ˇctvrt’a´ky, deseticenty a pˇeticenty, pokud je dolar 100 cent˚ u a ˇctvrt’a´k 25 cent˚ u? Pˇ r´ıklad 15. (pˇrevzato z knihy [11]) P´alkaˇrsk´ y pr˚ umˇer basebalov´ ych hr´aˇc˚ u je podle wikipedie relativn´ı statistick´ y ukazatel u ´toˇc´ıc´ıch basebalov´ ych hr´aˇc˚ u. Je definov´an pomˇerem poˇctu vˇsech dobr´ ych odpal˚ u (hits) k poˇctu pokus˚ u na p´alce (at bat) bˇehem dan´e doby (obvykle mˇes´ıc, sez´ona, kari´era). Vyjadˇruje schopnost p´alkaˇre dobˇre odp´alit m´ıˇc a dostat se na mety. Neuv´ad´ı se v procentech ani v jin´e jednotce, zaˇzit´ y je tvar .XXX“ (teˇcka a tˇri ˇc´ıslice). Napˇr´ıklad hr´aˇc se ” tˇremi dobr´ ymi odpaly bˇehem 11 nadhoz˚ u m´a p´alkaˇrsk´ y pr˚ umˇer .273, protoˇze 3 = 0,2727272.... ≈ .273. Stejn´ y p´ a lkaˇ r sk´ y pr˚ u mˇ e r m´ a i hr´ aˇc se 41 dobr´ ymi 11 odpaly z 150 nadhoz˚ u nebo se 131 z 480 a stejnˇe tak se 273 z tis´ıce. Ot´azka je kolika zp˚ usoby m˚ uˇze hr´aˇc dos´ahnout p´alkaˇrsk´eho pr˚ umˇeru .273 z nejv´ yˇse 2000 nadhoz˚ u?

1.2

Pick˚ uv vzorec a ˇ reˇ sen´ı pˇ r´ıklad˚ u

Pˇr´ıklady, kter´e byly v minul´e kapitole, lze ˇreˇsit nˇekolika zp˚ usoby. Nˇekter´e pˇr´ıklady byly jednoduch´e n´avodn´e a nen´ı na nˇe potˇreba pouˇz´ıvat nijak sloˇzit´e techniky. Nˇekter´e jsou ale trochu komplikovanˇejˇs´ı a pokud zn´ame a pouˇzijeme Pick˚ uv vzorec, mnohdy si ˇreˇsen´ı a argumentaci znaˇcnˇe usnadn´ıme. Georg Pick, kter´ y byl profesorem na univerzitˇe v Praze, tento vzorec publikoval v roce 1899 ve sv´e pr´aci [14]. Jeˇstˇe neˇz vyslov´ıme vˇetu, o kter´e je cel´a tato pr´ace, osvˇetl´ıme pojem, kter´ y se v n´ı vyskytuje. Jednoduch´ y mnoho´ uheln´ık je mnoho´ uheln´ık, jehoˇz hranice je uzavˇren´a lomen´a ˇc´ara, kter´e sama sebe neprot´ın´a. To znamen´a, ˇze uvnitˇr jednoduch´eho mnoho´ uheln´ıku nejsou ˇza´dn´e d´ıry. Vˇ eta 1. (Pick˚ uv vzorec) Obsah jednoduch´eho mnoho´ uheln´ıku, kter´y m´a vrcholy v mˇr´ıˇzov´ych bodech, je roven B S = I + − 1, 2 8

kde I je poˇcet mˇr´ıˇzov´ych bod˚ u uvnitˇr mnoho´ uheln´ıku a B je poˇcet mˇr´ıˇzov´ych bod˚ u na hranici mnoho´ uheln´ıku. Je pˇrekvapiv´e, ˇze obsah lze urˇcit jen seˇcten´ım bod˚ u. Najednou m˚ uˇzeme poˇc´ıtat obsah nejr˚ uznˇejˇs´ıch sloˇzit´ ych u ´tvar˚ u tak jednoduˇse. Je to v˚ ubec moˇzn´e, ˇze obsah nez´avis´ı na tvaru mnoho´ uheln´ıku? Z Pickova vzorce tak´e plyne, ˇze obsah mnoho´ uheln´ıku, jehoˇz vrcholy jsou v mˇr´ıˇzov´ ych bodech, je bud’ celoˇc´ıseln´ y nebo cel´e ˇc´ıslo plus jedna polovina. Pozor ale na to, ˇze Pick˚ uv vzorec plat´ı jen pro jednoduch´e mnoho´ uheln´ıky. Na poveden´e ilustraci z knihy [11] jsou pˇr´ıklady mnoho´ uheln´ık˚ u, pro nˇeˇz Pick˚ uv vzorec neplat´ı. Nevˇeˇste ale hlavu, existuje rozˇs´ıˇren´ı i pro takov´eto mnoho´ uheln´ıky s vrcholy v mˇr´ıˇzov´ ych bodech, budeme o nˇem mluvit v kapitole 3.1.

Obr´azek 1.9: Pˇr´ıklad mnohostˇen˚ u, kter´e nejsou jednoduch´e

D˚ ukaz Pickova vzorce uk´aˇzeme pozdˇeji, a ne jen jeden. Nejdˇr´ıve vˇsak vyˇreˇs´ıme pˇr´ıklady, kter´e byly v minul´e kapitole. ˇ sen´ı: V´ ysledky a Reˇ Pˇr´ıklad 1: Troj´ uheln´ıky maj´ı n´asleduj´ıc´ı obsahy: 3 4 5 6 7 8 Troj´ uheln´ık 1 2 Obsah 10 8 10,5 7 6,5 7,5 7 7 Troj´ uheln´ıky ˇc´ıslo 4, 7 a 8 maj´ı stejn´ y obsah. Pˇr´ıklad 2: Chobotnice m´a obsah 40,5, ulita m´a obsah 33,5 a med´ uza m´a obsah 18,5. Pˇr´ıklad 3: Ryba na obr´azku 1.3 m´a obsah 49,5 a ryba na obr´azku 1.4 m´a obsah 140,5. Pˇr´ıklad 4: Pokud by takov´ y rovnostrann´ y troj´ ık existoval, jeho obsah by √uheln´ 3 2 byl podle vzorce pro obsah troj´ uheln´ıku roven 4 a , kde a je d´elka jeho strany. Jelikoˇz a je vzd´alenost mezi dvˇema mˇr´ıˇzov´ ymi body je a2 vˇzdy cel´e ˇc´ıslo. A to proto, ˇze bud’ je a d´elka u ´seˇcky rovnobˇeˇzn´e s osou x nebo osou y, nebo je a d´elka pˇrepony nˇejak´eho pravo´ uhl´eho troj´ uheln´ıku s odvˇesnami rovnobˇeˇzn´ ymi s osami x a y. Z Pythagorovy vˇety dost´av´ame, ˇze a2 je cel´e ˇc´ıslo. Z Pickova vzorce vˇsak v´ıme, ˇze obsah jednoduch´eho mnoho´ uheln´ıku s vrcholy v mˇr´ıˇzov´ ych bodech, je 1 nˇejak´ y celoˇc´ıseln´ y n´asobek 2 . Takov´ y obsah ale pro rovnostrann´ y troj´ uheln´ık nen´ı √ 3 2 moˇzn´ y, protoˇze nelze napsat ve tvaru 4 a . Pˇr´ıklad 5: Kaˇzd´ y takov´ y troj´ uheln´ık m´a pr´avˇe jednu hranu, kter´a proch´az´ı jedn´ım mˇr´ıˇzov´ ym bodem. Viz obr´azek 1.10. D˚ ukaz tohoto faktu lehce d´av´a Pick˚ uv vzorec. Pˇr´ıklad 6: Kaˇzd´ y takov´ y troj´ uheln´ık m´a podle zad´an´ı tˇri vrcholy v mˇr´ıˇzov´ ych bodech a pak bud’ jeden mˇr´ıˇzov´ y bod uvnitˇr nebo dva mˇr´ıˇzov´e body na hranˇe. Viz obr´azek 1.11. I tento fakt lehce plyne z Pickova vzorce. 9

Obr´azek 1.10: Pˇr´ıklad troj´ uheln´ık˚ u s v´ yˇskou 2

Obr´azek 1.11: Pˇr´ıklad troj´ uheln´ık˚ u s v´ yˇskou 3

Pˇr´ıklad 7: Obsah vˇsech obrazc˚ u je stejn´ y, vˇsechny maj´ı stejn´ y poˇcet mˇr´ıˇzov´ ych bod˚ u na hranici a ˇza´dn´ y mˇr´ıˇzov´ y bod uvnitˇr. Pˇr´ıklad 8: Podle zad´an´ı se jedn´a o jednoduch´ y mnoho´ uheln´ık, m˚ uˇzeme tedy aplikovat Pick˚ uv vzorec. Hranice proch´az´ı u ´plnˇe vˇsemi 40×25 mˇr´ıˇzov´ ymi body, tj. B = 1000 a ˇza´dn´ y mˇr´ıˇzov´ y bod nen´ı uvnitˇr, tedy I = 0. Celkov´ y obsah je tedy 499. Pˇr´ıklad 9: Na u ´seˇcce spojuj´ıc´ı body [a1 ,b1 ] a [a2 ,b2 ] je N SD(|a2 − a1 |,|b2 − b1 |) + 1 mˇr´ıˇzov´ ych bod˚ u, kde N SD(k,l) znaˇc´ı nejvˇetˇs´ı spoleˇcn´ y dˇelitel ˇc´ısel k a l. ´ cka m´a smˇerov´ Useˇ y vektor (a2 − a1 ,b2 − b1 ). Body, kter´e leˇz´ı na t´eto u ´seˇcce, maj´ı souˇradnice [a1 ,b1 ] + λ(a2 − a1 ,b2 − b1 ), kde λ nab´ yv´a hodnot od 0 do 1, nula pro bod [a1 ,b1 ] a jedna pro [a2 ,b2 ]. Mˇr´ıˇzov´e body jsou pak takov´e, pro kter´e jsou λ(a2 − a1 ) a λ(b2 − b1 ) cel´a ˇc´ısla. Pokud jsou ˇc´ısla |a2 − a1 | a |b2 − b1 | soudˇeln´a existuje nˇekolik λ, aby ˇc´ısla λ(a2 − a1 ) a λ(b2 − b1 ) byla cel´a. Pokud oznaˇc´ıme d = N SD(|a2 − a1 |,|b2 − b1 |), budou se takov´a vhodn´a λ postupnˇe rovnat 0 = d0 , 1 , . . . , d−1 , dd = 1. Je jich tedy d + 1. d d Pˇr´ıklad 10: Pokud je n prvoˇc´ıslo, pak jsou ˇc´ısla i a n − i vz´ajemnˇe nesoudˇeln´a pro libovoln´e i. Pokud by totiˇz n − i a i byly dˇeliteln´e ˇc´ıslem d, dˇelilo by toto ˇc´ıslo i (n − i) + i = n. To znamen´a, ˇze pro i 6= 0 na pˇr´ımce ix + (n − i)y = 0, nen´ı mezi poˇca´tkem a bodem [n − i, i] ˇza´dn´ y dalˇs´ı mˇr´ıˇzov´ y bod. Jin´e mˇr´ıˇzov´e body tedy leˇz´ı pouze na hran´ach AO a BO. Nyn´ı si povˇsimnˇeme toho, ˇze vˇsechny mal´e troj´ uheln´ıky OXi Xn−i , i = 1, . . ., n − 2, maj´ı stejnou v´ yˇsku i d´elku z´akladny, kter´a leˇz´ı na u ´seˇcce AB. Proto maj´ı stejn´ y obsah. Kaˇzd´ y z troj´ uheln´ık˚ u m´a pouze tˇri mˇr´ıˇzov´e body na sv´e hranici, coˇz jsou pr´avˇe jeho vrcholy, proto dost´av´ame z Pickova vzorce, ˇze vˇsechny maj´ı uvnitˇr stejn´ y poˇcet mˇr´ıˇzov´ ych bod˚ u. Ted’ uˇz nen´ı tˇeˇzk´e urˇcit poˇcet mˇr´ıˇzov´ ych bod˚ u uvnitˇr kaˇzd´eho mal´eho troju ´heln´ıku, kter´ y je n+1 . 2 Pˇr´ıklad 11: Pick˚ uv vzorec n´am d´av´a rovnost 25 + 1 = I + B2 . Pokud chceme maxim´aln´ı poˇcet mˇr´ıˇzov´ ych bod˚ u ve ˇctverci, snaˇz´ıme se naj´ıt polohu ˇctverce, ve kter´e je 10

ˇ sen´ı pˇr´ıkladu 11 Obr´azek 1.12: Reˇ

maxim´aln´ı poˇcet mˇr´ıˇzov´ ych bod˚ u na hranici. To nastane v pˇr´ıpadˇe, ˇze hrany ˇctverce leˇz´ı rovnobˇeˇznˇe s osami x a y a je 4 × 5 = 20 = B, pak je I = 16. Minim´aln´ı poˇcet bod˚ u na hranici je B = 4, tedy jen vrcholy ˇctverce. Pak je I = 24. Pˇr´ıklad 12: V pˇr´ıpadˇe, ˇze ˇctverec leˇz´ı tak, ˇze jeho vrcholy jsou v mˇr´ıˇzov´ ych bodech a jeho hrany jsou rovnobˇeˇzn´e s osami x a y, zakr´ yv´a pˇresnˇe (n + 1)2 mˇr´ıˇzov´ ych bod˚ u. Protoˇze obvod ˇctverce je 4n, nemohou hrany ˇctverce v jeho obecn´e poloze obsahovat v´ıce neˇz 4n mˇr´ıˇzov´ ych bod˚ u. Pick˚ uv vzorec n2 = I + B/2 − 1 d´av´a do souvislosti obsah ˇctverce s vrcholy v mˇr´ıˇzov´ ych bodech a poˇcet mˇr´ıˇzov´ ych bod˚ u na jeho hran´ach a uvnitˇr nˇej. Celkov´ y poˇcet mˇr´ıˇzov´ ych bod˚ u, kter´e m˚ uˇze ˇctverec pˇrekr´ yt, je I + B, coˇz, jak vypl´ yv´a z n´asleduj´ıc´ı nerovnice, je maxim´alnˇe (n + 1)2 , I +B =I +

B B 4n B − 1 + + 1 = n2 + + 1 ≤ n2 + + 1 = (n + 1)2 . 2 2 2 2

Pˇr´ıklad 13: Kolika zp˚ usoby lze rozmˇenit dolar na ˇctvrt’a´ky, deseticenty a pˇeticenty? Tato u ´loha zd´anlivˇe nesouvis´ı s obsahem nˇejak´eho mnoho´ uheln´ıku natoˇz s Pickov´ ym vzorcem, ale zd´an´ı m˚ uˇze klamat. Uk´aˇzeme tˇri zp˚ usoby ˇreˇsen´ı t´eto u ´lohy, jak jsou pops´any v knize [11], a zjist´ıme, ˇze i zde se Pick˚ uv vzorec hod´ı. Prvn´ı ˇreˇsen´ı. Pro prvn´ı ˇreˇsen´ı zvol´ıme nejpˇr´ımˇejˇs´ı postup a to vypsat si systematicky vˇsechny moˇzn´e kombinace ˇctvrt’a´k˚ u, deseticent˚ u a pˇeticent˚ u, tak aby jejich souˇcet byl jeden dolar, tedy sto cent˚ u. Hled´ame trojice (c,d,p) tak, aby splˇ novaly rovnici 25c + 10d + 5p = 100. d = 10 d=9 d=8 d=7 d=6 d=5 d=4 d=3 d=2 d=1 d=0

(0,10,0) (0,9,2) (0,8,4) (0,7,6) (0,6,8) (0,5,10) (0,4,12) (0,3,14) (0,2,16) (0,1,18) (0,0,20) c=0

(1,7,1) (1,6,3) (1,5,5) (1,4,7) (1,3,9) (1,2,11) (1,1,13) (1,0,15) c=1

(2,5,0) (2,4,2) (2,3,4) (2,2,6) (3,2,1) (2,1,8) (3,1,3) (2,0,10) (3,0,5) (4,0,0) c=2 c=3 c=4

T´ımto systematick´ ym v´ yˇctem vˇsech moˇznost´ı dost´av´ame, ˇze existuje 29 moˇznost´ı, jak rozmˇenit dolar. 11

Druh´e ˇreˇsen´ı bude vyˇzadovat trochu pˇredstavivosti. Pokud vybereme poˇcet ˇctvrt’a´k˚ u a deseticent˚ u v rozmˇenˇen´ı, bude t´ımto v´ ybˇerem uˇz urˇceno, kolik pˇeticent˚ u mus´ıme dodat, aby souˇcet minc´ı byl jeden dolar. Staˇc´ı n´am tedy hledat jen vˇsechny moˇzn´e kombinace poˇctu ˇctvrt’a´k˚ u c a poˇctu deseticent˚ u d, aby platilo 25c + 10d ≤ 100. Pˇredstavme si, ˇze m´ame pˇred sebou na stole ˇctyˇri ˇctvrt’a´ky a deset deseticent˚ u. Dohromady maj´ı tyto mince hodnotu dva dolary a s jejich pomoc´ı m˚ uˇzeme reprezentovat vˇsechny moˇzn´e kombinace na rozmˇenˇen´ı dolaru. M´ame pˇet moˇznost´ı, kolik vz´ıt ˇctvrt’a´k˚ u (c = 0,1,2,3, 4), a jeden´act moˇznost´ı pro deseticenty (d = 0,1, . . . , 10). Dohromady 5 · 11 = 55 moˇzn´ ych kombinac´ı minc´ı. Pˇresnˇe dolar dostaneme ve tˇrech moˇznostech, a to (c,d) = (4,0), (2,5) a (0,10). Zb´ yv´a 52 moˇznost´ı, ˇ astka, kterou vybereme, je 25c+10d cent˚ kter´e mus´ıme doplnit pˇeticenty. C´ u, a na stole z˚ ustane 4−c ˇctvrt’a´k˚ u a 10−d deseticent˚ u, jejichˇz hodnota je 200−(25c+10d) cent˚ u. Z toho vid´ıme, ˇze 52 kombinac´ı se skl´ad´a z 26 komplement´arn´ıch p´ar˚ u, jejichˇz hodnota je dohromady 200 cent˚ u. Tedy 26 kombinac´ı d´av´a ˇca´stku menˇs´ı neˇz dolar a 26 kombinac´ı vˇetˇs´ı neˇz dolar. Dohromady dost´av´ame, ˇze je 26 + 3 = 29 moˇznost´ı, jak rozmˇenit dolar s pouˇzit´ım ˇctvrt’a´k˚ u, deseticent˚ u a pˇeticent˚ u. Ve tˇret´ım zp˚ usobu ˇreˇsen´ı budeme poˇc´ıtat body uvnitˇr troj´ uheln´ıku. V u ´loze o rozmˇenˇen´ı dolaru vlastnˇe hled´ame poˇcet celoˇc´ıseln´ ych kombinac´ı ˇc´ısel (c,d) tak, aby 25c + 10d ≤ 100. Poˇcet pˇeticent˚ u opˇet neuvaˇzujeme, protoˇze je jednoznaˇcnˇe urˇcen ˇc´ısly c a d. V kart´ezsk´e soustavˇe souˇradnic budeme poˇc´ıtat, kolik je mˇr´ıˇzov´ ych bod˚ u v troj´ uheln´ıku vyznaˇcen´em na obr´azku. Kaˇzd´ y mˇr´ıˇzov´ y bod d [0,10] 25c+10d=100

c [0,0]

[4,0]

v troj´ uheln´ıku odpov´ıd´a nˇejak´e moˇznosti rozmˇenˇen´ı dolaru. Napˇr´ıklad bod [1,4] odpov´ıd´a jednomu ˇctvrt’a´ku, ˇctyˇrem deseticent˚ um a sedmi pˇeticent˚ um. Pokud spoˇcteme body vyznaˇcen´e na obr´azku dostaneme 29, coˇz, jak uˇz v´ıme, je poˇcet moˇzn´ ych rozmˇenˇen´ı dolaru na ˇctvrt’a´ky, deseticenty a pˇeticenty. Pro tento mal´ y troj´ uheln´ık nebylo tˇeˇzk´e mˇr´ıˇzov´e body spoˇc´ıtat rovnou. Mohli bychom ale k tomuto u ´ˇcelu lehce pouˇz´ıt Pick˚ uv vzorec, jak to udˇel´ame v dalˇs´ım pˇr´ıkladu, kdy n´as zaj´ım´a, kolika zp˚ usoby lze rozmˇenit v´ıce dolar˚ u. Tˇret´ı pˇr´ıstup kombinoval myˇslenky prvn´ıho a druh´eho ˇreˇsen´ı. Staˇc´ı si uvˇedomit, ˇze kaˇzd´ y z mˇr´ıˇzov´ ych bod˚ u v troj´ uheln´ıku odpov´ıd´a jedn´e kombinaci v tabulce v prvn´ım ˇreˇsen´ı. Obd´eln´ıkov´e pole s 5 · 11 = 55 mˇr´ıˇzov´ ymi body odpov´ıd´a vˇsem moˇzn´ ym kombinac´ım, kter´e lze sloˇzit ze ˇctyˇr ˇctvrt’a´k˚ u a deseti deseticent˚ u, kter´e jsme uvaˇzovali v druh´em ˇreˇsen´ı. Body pod diagon´alou odpov´ıdaj´ı kombinac´ım minc´ı s celkovou hodnotou menˇs´ı neˇz je dolar, tˇri body na diagon´ale tˇrem kombinac´ım, kdy jsme dostali pˇresnˇe dolar, a body nad diagon´alou odpov´ıdaj´ı kombinac´ım minc´ı, kter´e maj´ı celkovou hodnotu vˇetˇs´ı neˇz dolar. 12

Pˇr´ıklad 14: Pokud se pt´ame, kolika zp˚ usoby lze rozmˇenit D dolar˚ u na ˇctvrt’a´ky, deseticenty a pˇeticenty, pt´ame se vlastnˇe kolik je celoˇc´ıseln´ ych, nez´aporn´ ych ˇreˇsen´ı rovnice 25c + 10d + 5p = 100D, kde c je poˇcet ˇctvrt’a´k˚ u, d poˇcet deseticent˚ u a p pˇeticent˚ u. Celou rovnice m˚ uˇzeme vydˇelit 5 a dostaneme 5c + 2d + p = 20D. Pokud urˇc´ıme c a d, bude jiˇz p urˇceno, proto n´am staˇc´ı hledat kombinace c a d tak, ˇze splˇ nuj´ı 5c + 2d ≤ 20D, c ≥ 0, d ≥ 0. Tyto tˇri nerovnosti urˇcuj´ı troj´ uheln´ık s vrcholy [0,0], [4D,0] a [0,10D]. Kaˇzd´ y mˇr´ıˇzov´ y bod tohoto troj´ uheln´ıku pak odpov´ıd´a jedn´e z moˇzn´ ych kombinac´ı ’ ˇctvrt a´k˚ u, deseticent˚ u a pˇeticent˚ u v rozmˇenˇen´ı D dolar˚ u. Vyuˇzijeme Pick˚ uv vzorec pro urˇcen´ı poˇctu mˇr´ıˇzov´ ych bod˚ u v troj´ uheln´ıku. Obsah troj´ uheln´ıku pak je S = 21 ·40D2 . Na obvodu je 4D +10D +N SD(4D,10D) mˇr´ıˇzov´ ych bod˚ u, kde jsme pouˇzili v´ ysledek Pˇr´ıkladu 9 pro urˇcen´ı poˇctu mˇr´ıˇzov´ ych bod˚ u na spojnici bod˚ u [4D,0] a [0,10D]. Nejvˇetˇs´ı spoleˇcn´ y dˇelitel 4D a 10D je 2D, proto je poˇcet bod˚ u 1 2 na obvodu troj´ uheln´ıku B = 16D. Pick˚ uv vzorec d´av´a 20D = I + 2 · 16D − 1, tedy uvnitˇr m´ame I = 20D2 − 8D + 1 mˇr´ıˇzov´ ych bod˚ u. Celkov´ y poˇcet mˇr´ıˇzov´ ych 2 bod˚ u v troj´ uheln´ıku je pak I + B = 20D + 8D + 1, coˇz je poˇcet vˇsech moˇznost´ı, jak rozmˇenit D dolar˚ u na ˇctvrt’a´ky, deseticenty a pˇeticenty. Pˇr´ıklad 15: Pod´ıv´ame-li se na basebalovou u ´lohu z matematick´eho hlediska, n je hled´ame poˇcet dvojic (x,y), jejichˇz pomˇer xy je mezi 0,2725 a 0,2735 a z´aroveˇ 0 < x ≤ 2000. Pokud poˇzijeme poˇc´ıtaˇc nebo jinou v´ ypoˇcetn´ı techniku m˚ uˇzeme z´ıskat seznam vˇsech takov´ ych dvojic. S Pickov´ ym vzorcem dostaneme v´ ysledek i bez otrock´eho vypisov´an´ı vˇsech moˇznost´ı. P´alkaˇrsk´ y pr˚ umˇer bude .273, pokud x a y, 0 < x ≤ 2000, splˇ nuj´ı 0,2725 =

y 547 545 ≤ < = 0,2735. 2000 x 2000

Vˇsechny dvojice (x,y), kter´e hled´ame, jsou mˇr´ıˇzov´e body n´aleˇzej´ıc´ı troj´ uheln´ıku s vrcholy [2000,545], [2000,547] a [0,0]. y poˇcet odpal˚ u

[2000,547]

[x, y]

[2000,545]

x poˇcet nadhoz˚ u

Obr´azek 1.13: Palkaˇrsk´ y pr˚ umˇer .273

Obr´azek ilustruje tento troj´ uheln´ık, i kdyˇz osy x a y nemaj´ı stejn´e mˇeˇr´ıtko. Troj´ uheln´ık m´a obsah 2000, protoˇze svisl´a strana m´a d´elku 2 a pˇr´ısluˇsn´a v´ yˇska je 2000. Na hranici jistˇe leˇz´ı tˇri vrcholy troj´ uheln´ıku a jeden mˇr´ıˇzov´ y bod na svisl´e 13

hranˇe. Na hranˇe [2000,545], [0,0] leˇz´ı ˇctyˇri, protoˇze ˇc´ısla 2000 a 545 jsou soudˇeln´a a jejich nejvˇetˇs´ı spoleˇcn´ y dˇelitel je 5, viz Pˇr´ıklad 9, zato ˇc´ısla 2000 a 547 soudˇeln´a nejsou, a tak na posledn´ı hranˇe ˇza´dn´ y mˇr´ıˇzov´ y bod neleˇz´ı. Podle Pickova vzorce je 8 2000 = I + − 1 = I + 3, 2 takˇze uvnitˇr troj´ uheln´ıku je I = 1997 bod˚ u. Dva vrcholy troj´ uheln´ıku mus´ıme z celkov´eho poˇctu moˇznost´ı odeˇc´ıst, jsou to [0,0] a [2000,547], kter´e jsou na obr´azku naznaˇceny pr´azdn´ ym koleˇckem a neodpov´ıdaj´ı zad´an´ı. Poˇcet moˇznost´ı, jak z´ıskat poˇzadovan´ y p´alkaˇrsk´ y pr˚ umˇer z maxim´alnˇe 2000 nadhoz˚ u, je tedy I + B − 2 = 2003.

14

Kapitola 2 D˚ ukazy a souvislosti Sedmdes´at let z˚ ustal Pick˚ uv elegantn´ı vzorec skoro nepovˇsimnut. Pozornost opˇet z´ıskal d´ıky H. Steinhausovˇe knize Mathemtical Snapshots, kter´a vyˇsla v roce 1969. Od t´e doby matematici naˇsli mnoho d˚ ukaz˚ u Pickova vzorce s vyuˇzit´ım nejr˚ uznˇejˇs´ıch metod. Nˇekter´e zaj´ımav´e souvislosti a d˚ ukazy uk´aˇzeme. Neˇz se pust´ıme do prvn´ıho d˚ ukazu Pickova vzorece, pˇripomeneme jeho znˇen´ı. Obsah jednoduch´eho mnoho´ uheln´ıku, kter´ y m´a vrcholy v mˇr´ıˇzov´ ych bodech je roven B S = I + − 1, 2 kde I je poˇcet mˇr´ıˇzov´ ych bod˚ u uvnitˇr mnoho´ uheln´ıku a B je poˇcet mˇr´ıˇzov´ ych bod˚ u na hranici mnoho´ uheln´ıku.

2.1

Prvn´ı d˚ ukaz Pickova vzorce

V minul´e kapitole jsme se jiˇz sezn´amili s Pickov´ ym vzorcem a s jeho aplikacemi. Z˚ ustal n´am ale dluh. Vzorec jsme sice vyslovili, pouˇz´ıvali, ale nedok´azali jsme, ˇze opravdu plat´ı. V t´eto kapitole proto uk´aˇzeme, ˇze plat´ı. V d˚ ukazu budeme postupovat podle knihy [11]. D˚ ukaz. Zaˇcneme od nejjednoduˇs´ıch tvar˚ u. Plat´ı opravdu Pick˚ uv vzorec napˇr´ıklad pro obd´eln´ık se stranami d´elky a, b ∈ N, kter´ y m´a hrany rovnobˇeˇzn´e s osami x a y? Na obvodu m´a takov´ y obd´eln´ık 2a + 2b = B mˇr´ıˇzov´ ych bod˚ u, viz obr´azek 2.1. Uvnitˇr je (a − 1)(b − 1) = I mˇr´ıˇzov´ ych bod˚ u. Pick˚ uv vzorec opravdu plat´ı, protoˇze B 1 I + − 1 = (a − 1)(b − 1) + (2a + 2b) − 1 = ab, 2 2 coˇz odpov´ıd´a obsahu obd´eln´ıku. Pick˚ uv vzorec tedy plat´ı pro obecn´ y obd´eln´ık. Plat´ı tak´e pro pravo´ uhl´ y troju ´heln´ık, kter´ y vznikl rozdˇelen´ım obd´eln´ıku u ´hlopˇr´ıˇckou na p˚ ul, tedy pro obecn´ y pravo´ uhl´ y troj´ uheln´ık s odvˇesnami d´elek a a b, kter´e jsou rovnobˇeˇzn´e s osami x a y? K ovˇeˇren´ı Pickova vzorce v tomto pˇr´ıpadˇe mus´ıme uk´azat, ˇze plat´ı I+

B ab −1= . 2 2 15

b

a

Obr´azek 2.1: Obd´eln´ık s vrcholy v mˇr´ıˇzov´ ych bodech a hranami d´elky a, b

Oznaˇcme B ∗ poˇcet mˇr´ıˇzov´ ych bod˚ u na pˇreponˇe vˇcetnˇe krajn´ıch bod˚ u. Pak je poˇcet mˇr´ıˇzov´ ych bod˚ u na hranici troj´ uheln´ıku B = a + b + B ∗ − 1.

Protoˇze B ∗ mˇr´ıˇzov´ ych bod˚ u na u ´hlopˇr´ıˇcce leˇz´ı na hranici obou pravo´ uhl´ ych troju ´heln´ık˚ u, na kter´e u ´hlopˇr´ıˇcka rozdˇeluje obd´eln´ık, dost´av´ame tedy 2I + 2B = (a + 1)(b + 1) + B ∗ ,
1 I + B = (a + 1)(b + 1) + B ∗ . 2 Z toho plyne
1 B B 1 ab I + − 1 = I + B − − 1 = (a + 1)(b + 1) + B ∗ − (a + b + B ∗ − 1) − 1 = . 2 2 2 2 2 Pick˚ uv vzorec tedy opravdu plat´ı pro pravo´ uhl´ y troj´ uheln´ık. Zat´ım jsme uk´azali, ˇze vzorec plat´ı pro obd´eln´ık a pravo´ uhl´ y troj´ uheln´ık, d´ale pˇrejdeme uˇz k obecn´ ym jednoduch´ ym mnoho´ uheln´ık˚ um s vrcholy v mˇr´ıˇzov´ ych bodech. Pozor, jednoduch´ y mnoho´ uheln´ık v tomto smyslu nenaznaˇcuje, ˇze mnoho´ uheln´ık nem´a komplikovan´ y tvar, ale ˇze jeho hranice je uzavˇren´a lomen´a ˇc´ara, kter´a sama sebe nikde neprot´ın´a. Pˇredpokl´adejme, ˇze jednoduch´ y mnoho´ uheln´ık M je rozdˇelen do dvou menˇs´ıch 0 00 mnoho´ uheln´ık˚ u M a M jako je naznaˇceno na obr´azku 2.2.

M 00 M0

Obr´azek 2.2: Mnoho´ uheln´ık M rozdˇeleny na dva mnoho´ uheln´ıky Obsahy tˇechto mnoho´ uheln´ık˚ u jistˇe splˇ nuj´ı SM = SM 0 + SM 00 , kde SM je obsah mnoho´ uheln´ıku M a podobnˇe SM 0 ,SM 00 pro M 0 a M 00 . Nyn´ı pˇredpokl´adejme, ˇze podle Pickova vzorce je B0 SM 0 = I 0 + − 1, 2 B 00 SM 00 = I 00 + − 1. 2 16

Uk´aˇzeme, ˇze obsah velk´eho mnoho´ uheln´ıku M tak´e splˇ nuje Pick˚ uv vzorec. Poˇcet mˇr´ıˇzov´ ych bod˚ u, kter´e leˇz´ı na spoleˇcn´e ˇca´sti hranice menˇs´ıch mnoho´ uheln´ık˚ u M0 a M 00 , oznaˇcme B ∗ . Poˇcet mˇr´ıˇzov´ ych bod˚ u v mnoho´ uheln´ıku M je pak d´an I = I 0 + I 00 + B ∗ − 2, B = B 0 + B 00 − 2B ∗ + 2.

(2.1)

Takˇze B 00 B0 − 1) + (I 00 + − 1) = 2 2 1 B = (I 0 + I 00 + B ∗ − 2) + (B 0 + B 00 − 2B ∗ + 2) − 1 = I + − 1. 2 2

SM = SM 0 + SM 00 = (I 0 +

Pˇredchoz´ı v´ ypoˇcet ukazuje, ˇze pokud pro mnoho´ uheln´ıky M 0 a M 00 plat´ı Pick˚ uv B vzorec, plat´ı i pro mnoho´ uheln´ık M . To znamen´a, ˇze Pick˚ uv vzorec I + 2 − 1 je aditivn´ı stejnˇe jako obsah, tj. z˚ ust´av´a v platnosti i pro celek vznikl´ y seˇcten´ım ˇca´st´ı, pro kter´e vzorec platil. Obsahy nemus´ıme pouze sˇc´ıtat, m˚ uˇzeme je t´eˇz odeˇc´ıtat a tak pˇredchoz´ı tvrzen´ı m˚ uˇzeme vyslovit i takto: pokud pro mnoho´ uheln´ıky M 0 00 a M plat´ı Pick˚ uv vzorec, plat´ı i pro mnoho´ uheln´ık M . Princip aditivity tedy m˚ uˇzeme d´ale pouˇz´ıvat a kaˇzd´ y mnoho´ uheln´ık rozdˇelit na vhodn´e ˇc´asti, jejichˇz obsah jiˇz dok´aˇzeme spoˇc´ıtat. Pˇripomeˇ nme jeˇstˇe, ˇze v popsan´e aditivitˇe je d˚ uleˇzit´e, ˇze v´ ysledn´ y mnoho´ uheln´ık je opˇet jednoduch´ y. Pokud by sloˇzen´ y mnoho´ uheln´ık nebyl jednoduch´ y, neplatily by totiˇz vztahy (2.1). D´ale budeme analyzovat z´akladn´ı stavebn´ı kameny, na kter´e lze mnoho´ uheln´ık, jehoˇz vrcholy jsou v mˇr´ıˇzov´ ych bodech, rozdˇelit. Jsou jimi element´ arn´ı troju ´ heln´ıky, jejichˇz vrcholy jsou mˇr´ıˇzov´e body, ale kter´e jiˇz ˇz´adn´e dalˇs´ı mˇr´ıˇzov´e body neobsahuj´ı ani uvnitˇr ani na hranici. Kaˇzd´ y mnoho´ uheln´ık budeme cht´ıt rozdˇelit na element´arn´ı troj´ uheln´ıky. Toto rozdˇelen´ı budeme naz´ yvat element´ arn´ı triangulace. Element´arn´ı triangulace nen´ı jednoznaˇcn´a, dokonce vˇetˇsinou existuje nˇekolik moˇznost´ı, jak ji udˇelat. N´am bude staˇcit, ˇze existuje a ˇze m´a vˇzdy stejn´ y poˇcet element´arn´ıch troj´ uheln´ık˚ u. Pojd’me do pr´ace, mus´ıme dok´azat, ˇze element´arn´ı troj´ uheln´ıky splˇ nuj´ı dvˇe d˚ uleˇzit´e vlastnosti. Zformulujeme je do dvou tvrzen´ı. Tvrzen´ı 2. Kaˇzd´y mnoho´ uheln´ık, kter´y m´a vrcholy v mˇr´ıˇzov´ych bodech, m´a element´arn´ı triangulaci.

Obr´azek 2.3: Pˇr´ıklad moˇzn´e triangulace mnoho´ uheln´ıku M

D˚ ukaz. Zaprv´e kaˇzd´ y mnoho´ uheln´ık s vrcholy v mˇr´ıˇzov´ ych bodech m˚ uˇze b´ yt pomoc´ı u ´hlopˇr´ıˇcek rozdˇelen na troj´ uheln´ıky s vrcholy v mˇr´ıˇzov´ ych bodech. Zadruh´e 17

kaˇzd´ y neelement´arn´ı troj´ uheln´ık s vrcholy v mˇr´ıˇzov´ ych bodech m˚ uˇze b´ yt rozdˇelen na dva nebo tˇri menˇs´ı troj´ uheln´ıky s vrcholy v mˇr´ıˇzov´ ych bodech, • pokud obsahuje vnitˇrn´ı mˇr´ıˇzov´ y bod, propojen´ım tohoto bodu s vrcholy troj´ uheln´ıku, • pokud obsahuje mˇr´ıˇzov´ y bod na hranˇe, spojen´ım tohoto bodu s protˇejˇs´ım vrcholem:

Obr´azek 2.4: Dvˇe moˇznosti jak rozdˇelit troj´ uheln´ık, kter´ y nen´ı element´arn´ı

Pokud budeme tato dˇelen´ı opakovat, dokud bude existovat nˇejak´ y mˇr´ıˇzov´ y bod, kter´ y leˇz´ı uvnitˇr nebo na hranˇe nˇejak´eho troj´ uheln´ıku a nen´ı jeho vrcholem, dostaneme rozdˇelen´ı, kter´e bude element´arn´ı triangulac´ı.

k

Tvrzen´ı 3. Obsah kaˇzd´eho element´arn´ıho troj´ uheln´ıku je 12 . D˚ ukaz. Kaˇzd´ y troj´ uheln´ık s vrcholy v mˇr´ıˇzov´ ych bodech m˚ uˇze b´ yt veps´an do obd´eln´ıku s hranami, kter´e jsou rovnobˇeˇzn´e s osami x a y. Hrany tohoto obd´eln´ıku jsou u ´seˇcky, kter´e jsou pops´any maximem a minimem x-ov´e a y-ov´e souˇradnice vrchol˚ u troj´ uheln´ıku. Z hlediska veps´an´ı do obd´eln´ıku existuj´ı dva druhy troj´ uheln´ık˚ u s vrcholy v mˇr´ıˇzov´ ych bodech. Bud’ je strana troj´ uheln´ıku u ´hlopˇr´ıˇcka v obd´eln´ıku nebo nen´ı, jak ilustruje obr´azek 2.5.

Obr´azek 2.5: Troj´ uheln´ıky vepsan´e do obd´eln´ık˚ u

Element´arn´ı troj´ uheln´ıky mohou odpov´ıdat pouze konfiguraci vlevo na obr´azku 2.5, protoˇze troj´ uheln´ık vpravo mus´ı obsahovat vnitˇrn´ı mˇr´ıˇzov´ y bod, jak je naznaˇceno. Nejdelˇs´ı strana element´arn´ıho troj´ uheln´ıku je u ´hlopˇr´ıˇcka obd´eln´ıku a jedin´e mˇr´ıˇzov´e body na u ´hlopˇr´ıˇcce jsou jej´ı krajn´ı body. Veps´an´ım element´arn´ıho troj´ uheln´ıku OU Z do obd´eln´ıku vznikne ˇctyˇru ´heln´ık OW U Z viz obr´azek 2.6. Pro ˇctyˇru ´heln´ık plat´ı Pick˚ uv vzorec, protoˇze m˚ uˇze b´ yt rozdˇelen na obd´eln´ık a dva pravo´ uhl´e troj´ uheln´ıky, jak ukazuje dan´ y obr´azek. Pick˚ uv vzorec tak´e plat´ı pro pravo´ uhl´ y troj´ uheln´ık OW U . Odeˇcten´ım obsah˚ u 18

U

U

Z

O

Z

W

O

W

Obr´azek 2.6: Doplnˇen´ı element´arn´ıho troj´ uheln´ıku do ˇctyˇru ´heln´ıku

dost´av´ame, ˇze mus´ı platit i pro element´arn´ı troj´ uheln´ık OU Z. Element´arn´ı troju ´heln´ık m´a I = B = 3, a tak z Pickova vzorce, kter´ y je jiˇz dok´az´an pro obd´eln´ıky a pravo´ uhl´e troj´ uheln´ıky, dost´av´ame, ˇze obsah element´arn´ıho troj´ uheln´ıku je 12 .

k

T´ımto je dokonˇcen d˚ ukaz Pickova vzorce. Uk´azali jsme, ˇze Pick˚ uv vzorec je platn´ y pro element´arn´ı troj´ uheln´ıky. D´ıky aditivitˇe bude vzorec platn´ y i pro jednoduch´e mnoho´ uheln´ıky, kter´e sloˇz´ıme z element´arn´ıch troj´ uheln´ık˚ u. Na druhou stranu pokud m´ame jednoduch´ y mnoho´ uheln´ık, m˚ uˇzeme jej rozdˇelit na element´arn´ı troj´ uheln´ıky, pro neˇz Pick˚ uv vzorec plat´ı, a opˇet d´ıky aditivitˇe Pickova vzorce dostaneme obsah cel´eho jednoduch´eho mnoho´ uheln´ıku.

k

2.2

D˚ ukaz Pickova vzorce pˇ res u ´ hly viditelnosti

Pick˚ uv vzorec je dok´az´an, ale jak jiˇz bylo ˇreˇceno dˇr´ıve, d˚ ukaz˚ u tohoto kr´asn´eho vztahu je mnohem v´ıce. Nˇekomu se moˇzn´a bude v´ıce l´ıbit n´asleduj´ıc´ı pˇr´ımoˇcar´ y d˚ ukaz. Publikoval jej Dale E. Varberg [17] a je zaloˇzen´ y na myˇslence o u ´hlech viditelnosti. D˚ ukaz. Nejdˇr´ıve pˇriˇrad’me kaˇzd´emu mˇr´ıˇzov´emu bodu Pk uvnitˇr mnoho´ uheln´ıku θk ´hel viditelnosti“ v bodˇe Pk , kter´ ym se d´ıv´ame M v´ahu wk = 2π , kde θk je u ” dovnitˇr mnoho´ uheln´ıku.

M0 M 00

Obr´azek 2.7: Mnoho´ uheln´ık rozdˇelen´ y na dva mnoho´ uheln´ıky s naznaˇcen´ ymi u ´hly viditelnosti

Vnitˇrn´ı mˇr´ıˇzov´e body mnoho´ uheln´ıku maj´ı wk = 1, mˇr´ıˇzov´e body, kter´e leˇz´ı na hran´ach mnoho´ uheln´ıku a nejsou jeho vrcholy, maj´ı wk = 12 . Ve vrcholu, kter´ y m´a napˇr´ıklad wk = 14 , hrany sv´ıraj´ı prav´ yu ´hel, nebo ve vrcholu, kter´ y m´a wk = 61 , hrany sv´ıraj´ı u ´hel π3 atd. O v´aze wk m˚ uˇzeme uvaˇzovat jako o pˇr´ıspˇevku, kter´ y vrchol Pk pˇrid´av´a do spoleˇcn´eho obsahu mnoho´ uheln´ıku. 19

Budeme definovat veliˇcinu W =

X

wk .

Pk ∈M

Uk´aˇzeme, ˇze W je obsah mnoho´ uheln´ıku. Nejdˇr´ıve se zaob´ırejme ot´azkou, jestli je W aditivn´ı podobnˇe jako obsah. To znamen´a, ˇze pokud m´ame mnoho´ uheln´ık M , kter´ y vznikne spojen´ım dvou mnoho´ uheln´ık˚ u M 0 a M 00 , je W (M ) = W (M 0 ) + W (M 00 ). Popsan´a vlastnost je d˚ usledek toho, ˇze u ´hly viditelnosti v M 0 a M 00 v mˇr´ıˇzov´ ych bodech na jejich spoleˇcn´e hranˇe d´avaj´ı u ´hly viditelnosti v˚ uˇci mnoho´ uheln´ıku M , tedy opravdu W je aditivn´ı. 1 4

1 2

1 4

w

1 2

1

1 2

1 2

1 2

1

1 2

1 2

1 2

1 2

1

1 2

1

1 2

1 4

1 2

1 4

1 2

1 4

1−w 4

Obr´azek 2.8: Obd´eln´ık s naznaˇcen´ ymi u ´hly viditelnosti, pˇrevzat´ y z [7] V dalˇs´ım kroku mus´ıme uk´azat, ˇze W odpov´ıd´a obsahu mnoho´ uheln´ıku. Nejdˇr´ıve uvaˇzme obd´eln´ık, kter´ y m´a hrany rovnobˇeˇzn´e s osou x a y a jehoˇz vrcholy leˇz´ı v mˇr´ıˇzov´ ych bodech. Pro tento pˇr´ıpad je zˇrejm´e, ˇze W je obsah obd´eln´ıku, jak je ilustrov´ano na obr´azku 2.8 vlevo. Pokud uv´aˇz´ıme pravo´ uhl´ y troj´ uheln´ık, kter´ y m´a odvˇesny rovnobˇeˇzn´e s osami x a y, veliˇcina W opˇet d´av´a stejn´ y v´ ysledek jako obsah, protoˇze staˇc´ı d´ıky jiˇz dok´azan´e aditivitˇe vz´ıt W pro cel´ y obd´eln´ık a vydˇelit je dvˇema, viz obr´azek 2.8. D´ale libovoln´ y troj´ uheln´ık lze doplnit na obd´eln´ık s vyuˇzit´ım pravo´ uhl´ ych troj´ uheln´ık˚ u a obd´eln´ık˚ u, jak je naznaˇceno na obd´eln´ıc´ıch vpravo na obr´azku 2.8. Veliˇcina W je aditivn´ı, a tak W obecn´eho troj´ uheln´ıku dostaneme vhodn´ ym odeˇcten´ım veliˇciny W pro obd´eln´ıky a pravo´ uhl´e troj´ uheln´ıky. Stejnˇe tak bychom z´ıskali i obsah takov´eho troj´ uheln´ıku, a tak W pro obecn´ y troj´ uheln´ık je roven obsahu tohoto troj´ uheln´ıku. Poznamenejme, ˇze v d˚ ukazu zat´ım nebyl nikde pouˇzit pˇredpoklad o jednoduchosti mnoho´ uheln´ıku. Princip, na kter´em je d˚ ukaz zaloˇzen, vyuˇzijeme jeˇstˇe v Kapitole 3.1, kde budeme mluvit o zobecnˇen´em Pickovˇe vzorci pro mnoho´ uheln´ıky, kter´e nejsou jednoduch´e. Koneˇcnˇe se dost´av´ame k samotn´emu d˚ ukazu Pickova vzorce. Pro jednoduch´ y mnoho´ uheln´ık, jehoˇz vrcholy jsou mˇr´ıˇzov´e body, plat´ı podle Vˇety 1 S=I+

B − 1, 2

kde I je poˇcet mˇr´ıˇzov´ ych bod˚ u uvnitˇr mnoho´ uheln´ıku a B je poˇcet mˇr´ıˇzov´ ych bod˚ u na hranici mnoho´ uheln´ıku. Jednoduch´ y n-´ uheln´ık m´a n vnitˇrn´ıch u ´hl˚ u, coˇz jsou pr´avˇe vˇsechny u ´hly viditelnosti pˇri vrcholech a jejich souˇcet je (n − 2)π. Napˇr´ıklad troj´ uheln´ık m´a souˇcet 20

vnitˇrn´ıch u ´hl˚ u π, ˇctyˇru ´heln´ık 2π atd. Poˇcet mˇr´ıˇzov´ ych bod˚ u, kter´e jsou na hranici n-´ uheln´ıku, ale nejsou jeho vrcholy je B − n, pak je souˇcet u ´hl˚ u viditelnosti ’ k nim n´aleˇzej´ıc´ım (B − n)π. Ted jiˇz dost´av´ame, ˇze souˇcet vˇsech u ´hl˚ u viditelnosti, n´aleˇzej´ıc´ıch vˇsem B mˇr´ıˇzov´ ym bod˚ um na hranici mnoho´ uheln´ıku (jak vrchol˚ um, tak bod˚ um, kter´e nejsou vrcholy mnoho´ uheln´ıku), je (B − n)π + (n − 2)π = (B − 2)π. Takˇze pokud I je mnoˇzina vnitˇrn´ıch mˇr´ıˇzov´ ych bod˚ u mnoho´ uheln´ıku M a B je mnoˇzina mˇr´ıˇzov´ ych bod˚ u na jeho hranici, je obsah mnoho´ uheln´ıku S = W (M ) =

X Pk ∈I

2.3

wk +

X

wk = I +

Pk ∈B

B (B − 2)π = I + − 1. 2π 2

k

Tˇ ret´ı d˚ ukaz Pickova vzorce

Neˇz se pust´ıme do dalˇs´ıho d˚ ukazu Pickova vzorce, kter´ y opˇet vych´az´ı z knihy [11], ujasnˇeme si, co rozum´ıme pod pojmem triangulace nˇejak´eho mnoho´ uheln´ıku jiˇz ne nutnˇe s vrcholy v mˇr´ıˇzov´ ych bodech. Triangulace je rozdˇelen´ı tohoto mnoho´ uheln´ıku na troj´ uheln´ıky tak, ˇze ˇz´adn´ y z vrchol˚ u nˇejak´eho z troj´ uheln´ık˚ u neleˇz´ı na hranˇe jin´eho troj´ uheln´ıku, jak je naznaˇceno na obr´azku 2.9.

Obr´azek 2.9: Moˇzn´a triangulace mnoho´ uheln´ıku Jak jiˇz v´ıme d´ıky Tvrzen´ı 2 a 3, jednoduch´ y mnoho´ uheln´ık s vrcholy v mˇr´ıˇzov´ ych bodech m´a element´arn´ı triangulaci a obsah kaˇzd´eho element´arn´ıho troju ´heln´ıku je 12 . K d˚ ukazu Pickova vzorce by tedy vlastnˇe staˇcilo zjistit, kolik element´arn´ıch troj´ uheln´ık˚ u je v kaˇzd´e takov´e element´arn´ı triangulaci. Pokud by tento poˇcet byl 2I + B − 2, kde, jak jsme jiˇz zvykl´ı, I je poˇcet vnitˇrn´ıch a B poˇcet hraniˇcn´ıch mˇr´ıˇzov´ ych bod˚ u, byli bychom hotovi. Je to pravda, ale tento fakt mus´ıme dok´azat a udˇel´ame to pro mnoho´ uheln´ık, jehoˇz vrcholy nemusej´ı b´ yt mˇr´ıˇzov´e body. Tvrzen´ı 4. Triangulace jednoduch´eho mnoho´ uheln´ıku s B vrcholy na hranici a I vrcholy uvnitˇr je sloˇzen´a z T troj´ uheln´ık˚ u, kde pro T plat´ı T = 2I + B − 2. D˚ ukaz. K ovˇeˇren´ı tohoto tvrzen´ı uvaˇzme souˇcet vˇsech vnitˇrn´ıch u ´hl˚ u vˇsech troju ´heln´ık˚ u v triangulaci mnoho´ uheln´ıku, kter´ y oznaˇc´ıme Υ. Tento souˇcet budeme 21

poˇc´ıtat dvˇema zp˚ usoby a porovn´ame oba v´ ysledky. Zaprv´e kaˇzd´ y troj´ uheln´ık v triangulaci m´a souˇcet vnitˇrn´ıch u ´hl˚ u roven π. Takˇze Υ = T π.

2π π

Obr´azek 2.10: Triangulace s naznaˇcen´ ymi souˇcty u ´hl˚ u

Zadruh´e souˇcet u ´hl˚ u okolo kaˇzd´eho z I vnitˇrn´ıch bod˚ u je 2π a v B vrcholech na hranici je souˇcet π(B − 2) podle vzorce pro souˇcet vnitˇrn´ıch u ´hl˚ u mnoho´ uheln´ıku. Tedy dost´av´ame
Υ = 2I + (B − 2) π.

Pokud porovn´ame oba vztahy pro Υ dostaneme poˇzadovanou rovnost.

2.4

k

Euler˚ uv vzorec

K dalˇs´ımu d˚ ukazu Pickova vzorce vyuˇzijeme Euler˚ uv vzorec, kter´ y n´as zavede na v´ ylet do teorie graf˚ u. Ale pozor, nejedn´a se o grafy funkc´ı, ale o jist´a sch´emata, kter´a vhodn´ ym zp˚ usobem popisuj´ı nejr˚ uznˇejˇs´ı situace. Grafem G ch´apeme mnoˇzinu vrchol˚ u V spolu s mnoˇzinou hran H, coˇz jsou spojnice mezi nˇekter´ ymi dvojicemi vrchol˚ u. Vrcholy grafu mohou napˇr´ıklad zn´azorˇ novat obce v nˇejak´em okrese a hrany silnice mezi nimi. Jindy mohou vrcholy reprezentovat u ´ˇcastn´ıky nˇejak´eho plesu a spojnice mohou reprezentovat dvojice u ´ˇcastn´ık˚ u, kteˇr´ı se navz´ajem znaj´ı.

Obr´azek 2.11: Pˇr´ıklad grafu Pokud bychom se ponoˇrili do teorie graf˚ u hloubˇeji, setkali bychom se s nejr˚ uznˇejˇs´ımi typy graf˚ u. Pr´avˇe zaveden´ y pojem grafu by potom dostal dalˇs´ı upˇresˇ nuj´ıc´ı pˇr´ızviska: obyˇcejn´ y neorientovan´ y graf. Z plej´ady nejr˚ uznˇejˇs´ıch graf˚ u n´as bude zaj´ımat rovinn´ y graf, ˇc´ımˇz rozum´ıme graf, kter´ y lze nakreslit v rovinˇe bez toho, aby se hrany kˇr´ıˇzily. Kaˇzd´ y takov´ y graf 22

rozdˇeluje rovinu na koneˇcn´ y poˇcet oblast´ı, kter´e budeme naz´ yvat stˇ eny. Pozor, mezi stˇeny poˇc´ıt´ame i oblast vnˇe grafu. Ekvivalentnˇe lze definovat rovinn´ y graf jako takov´ y graf, kter´ y lze nakreslit na dvoudimenzion´aln´ı sf´eru bez toho, aby se jeho hrany kˇr´ıˇzily. Tato ekvivalence vych´az´ı napˇr´ıklad z toho, ˇze na sf´eˇre lze zvolit libovoln´ y bod, kter´ y nen´ı vrcholem grafu, ani nen´ı na jeho hranˇe, a z tohoto bodu m˚ uˇzeme stereografickou projekc´ı zobrazit zbytek sf´ery do roviny. Stereografick´a projekce je naznaˇcen´a na obr´azku 2.12.

Obr´azek 2.12: Stereografick´a projekce grafu na sf´eˇre

Jeˇstˇe neˇz se dostaneme k Eulerovˇe vzorci, sezn´am´ıme se s nˇekolika pojmy teorie graf˚ u. Posloupnost vrchol˚ u {P1 ,P2 , . . . ,Pn } postupnˇe propojen´ ych hranami z P1 do P2 , z P2 do P3 ... z Pn−1 do Pn se naz´ yv´a cesta.

Obr´azek 2.13: Pˇr´ıklad cesty

Souvisl´ y graf je pak takov´ y graf, v nˇemˇz existuje cesta mezi kaˇzd´ ymi dvˇema vrcholy.

Obr´azek 2.14: Pˇr´ıklad souvisl´eho a nesouvisl´eho grafu

Kruˇ znice je uzavˇren´a cesta z vrcholu, pˇres jin´e vrcholy zpˇet do p˚ uvodn´ıho vrcholu, tj. jedn´a se o cestu, v n´ıˇz je P1 = Pn . Strom je takov´ y graf, kter´ y je souvisl´ y a neobsahuje kruˇznici. Kostrou grafu rozum´ıme nejmenˇs´ı souvisl´ y podgraf G souvisl´eho grafu, to znamen´a, ˇze obsahuje vˇsechny vrcholy grafu a nˇekter´e z p˚ uvodn´ıch hran tak, aby poˇcet hran byl minim´aln´ı, ale graf G z˚ ustal souvisl´ y. Takto zaveden´a kostra grafu je stromem, tj. neobsahuje ˇza´dnou uzavˇrenou kruˇznici, protoˇze z kruˇznice lze odstranit jednu hranu a z´ıskat st´ale souvisl´ y graf s menˇs´ım poˇctem hran. Nen´ı tˇeˇzk´e si rozmyslet, ˇze libovoln´ y strom m´a poˇcet vrchol˚ u o jedna vˇetˇs´ı neˇz je poˇcet jeho hran. Zkuste si to rozkreslit. D˚ ukaz by postupoval indukc´ı od nejjednoduˇs´ıho stromu, coˇz je jeden vrchol k vˇetˇs´ım strom˚ um. Staˇc´ı si uvˇedomit, ˇze s kaˇzd´ ym pˇrid´an´ım hrany pˇribude i jeden vrchol. 23

Obr´azek 2.15: Pˇr´ıklad kruˇznic v teorii graf˚ u

Vˇ eta 5. (Euler˚ uv vzorec) Pro souvisl´y rovinn´y graf G s V vrcholy, H hranami a S stˇenami plat´ı V − H + S = 2. D˚ ukaz˚ u Eulerova vzorce je bezpoˇcet, uvedeme d˚ ukaz z knihy [1], kter´ y lze dohledat jiˇz v knize od von Stauda z roku 1847. D˚ ukaz. Bud’ T ⊂ H podmnoˇzina hran grafu G, kter´e jsou hranami kostry grafu G. D´ale budeme potˇrebovat du´aln´ı graf G∗ k grafu G. Ten vznikne n´asleduj´ıc´ım postupem: Do grafu G pˇrid´ame jeden nov´ y vrchol do kaˇzd´e stˇeny, nezapomeneme ani na vnˇejˇs´ı stˇenu. Tyto vrcholy propoj´ıme hranou tehdy, pokud odpov´ıdaj´ıc´ı si stˇeny maj´ı spoleˇcnou hranu. Pokud stˇeny soused´ı nˇekolika hranami, pˇres kaˇzdou hranu nakresl´ıme jednu novou hranu. T´ım jsme z´ıskali du´aln´ı graf G∗ .

Obr´azek 2.16: Kostra v du´aln´ım grafu

Uvaˇzme T ∗ ⊂ H∗ mnoˇzinu hran v du´aln´ım grafu, kter´a odpov´ıd´a hran´am grafu G, kter´e nejsou hranami libovoln´e pevnˇe zvolen´e kostry, tj. nejsou v T . Hrany v T ∗ propojuj´ı vˇsechny stˇeny, protoˇze p˚ uvodn´ı kostra grafu T neobsahuje kruˇznice. Tak´e T ∗ neobsahuje kruˇznice, protoˇze jinak by oddˇelila nˇejak´ y vrchol grafu G uvnitˇr kruˇznice od hran vnˇe kruˇznice. To nelze, protoˇze T spojuje vˇsechny vrcholy grafu G a s T ∗ nem´a ˇza´dn´ y pr˚ useˇc´ık. Takˇze T ∗ je kostrou v G∗ . Pro kaˇzd´ y strom plat´ı, jak jsme si rozmysleli v´ yˇse, ˇze poˇcet jeho vrchol˚ u je o jedna vˇetˇs´ı neˇz poˇcet jeho hran. Pro strom T dostaneme, ˇze poˇcet vrchol˚ u je ∗ V = HT + 1 zat´ımco pro T dostaneme poˇcet stˇen S = HT ∗ + 1, kde HT znaˇc´ı poˇcet hran v T a HT ∗ poˇcet hran v mnoˇzinˇe T ∗ . Seˇcten´ım obou rovnost´ı dostaneme V + S = (HT + 1) + (HT ∗ + 1) = H + 2. Pˇritom jsme vyuˇzili vztah H = HT + HT ∗ , protoˇze kaˇzd´a hrana grafu G je bud’ souˇc´ast´ı kostry grafu G nebo j´ı odpov´ıd´a hrana du´aln´ı kostry T ∗ .

k

Euler dok´azal rovnost V − H + S = 2 jiˇz v roce 1752, nˇekdy se vˇsak tvrd´ı, ˇze tento vztah znal jiˇz Descartes v roce 1640. P˚ uvodn´ı tvrzen´ı vˇsak popisovalo nam´ısto rovinn´ ych graf˚ u konvexn´ı mnohostˇeny, pro kter´e plat´ı stejn´ y vztah. Konvexn´ı mnohostˇ eny, totiˇz takov´e, ˇze spojnice libovoln´ ych dvou jejich bod˚ u leˇz´ı cel´a uvnitˇr mnohostˇenu, tj. ˇze povrch nen´ı nikde prohnut´ y dovnitˇr“, lze pˇrev´est ” 24

Obr´azek 2.17: Graf krychle a osmistˇenu

na rovinn´e grafy, kter´e maj´ı stejn´ y poˇcet vrchol˚ u, hran a stˇen. Na obr´azku jsou naznaˇceny rovinn´e grafy pro krychli a osmistˇen. Pro zaj´ımavost uved’me, ˇze v topologii, kter´a zkoum´a vlastnosti tˇeles a prostor˚ u bez ohledu na vzd´alenosti, u ´hly ˇci kˇrivosti, se zav´ad´ı Eulerova charakteristika tˇelesa χ = 2 − 2g, kde g je tzv. rod, kter´ y ud´av´a poˇcet dˇer“ v tˇelese. ” Napˇr´ıklad koule nebo krychle m´a rod 0, torus m´a rod 1 stejnˇe jako hrneˇcek s jedn´ım uchem a hrnec se dvˇema uchy m´a rod 2. Pro nejr˚ uznˇejˇs´ı hranoly se Eulerova charakteristika χ poˇc´ıt´a pr´avˇe pomoc´ı n´am jiˇz zn´am´eho vzorce χ = V − H + S. Napˇr´ıklad rod krychle nebo jin´ ych konvexn´ıch tˇeles je nula, tedy opravdu V − H + S = 2 = χ. N´asleduj´ıc´ı vˇetu o hran´ach a z n´ı vych´azej´ıc´ı d˚ ukaz Pickova vzorce publikoval W. W. Funkenbusch [6] v roce 1974. Vˇ eta 6. (o hran´ ach) Poˇcet hran grafu, kter´y je triangulac´ı jednoduch´eho mnoho´ uheln´ıku, splˇ nuje H = 3I + 2B − 3, kde H je poˇcet hran, B je poˇcet vrchol˚ u na hranici grafu a I je poˇcet vrchol˚ u uvnitˇr grafu. D˚ ukaz. Mˇejme graf, kter´ y je triangulac´ı jednoduch´eho mnoho´ uheln´ıku. Abychom tvrzen´ı dok´azali staˇc´ı uk´azat, ˇze vzorec plat´ı pro nejjednoduˇsˇs´ı jednoduch´ y mnohou ´heln´ık a ˇze plat´ı pro mnoho´ uheln´ıky, kter´e vzniknou, pˇrid´ame-li do grafu jeho triangulace nov´ y vrchol a t´ım tento graf zvˇetˇs´ıme. Nejjednoduˇsˇs´ı mnoho´ uheln´ık je troj´ uheln´ık, tj. B = 3, I = 0 a vzorec je splnˇen, protoˇze poˇcet hran je H = 3.

Obr´azek 2.18: Pˇr´ıklad pˇrid´an´ı bod˚ u

Pˇredpokl´adejme, ˇze vzorec plat´ı pro nˇejak´ y graf, kter´ y je triangulac´ı jednoduch´eho mnoho´ uheln´ıku, existuj´ı dvˇe moˇznosti, jak pˇridat do grafu nov´ y vrchol. Pokud pˇrid´ame do grafu vnitˇrn´ı bod jako na obr´azku 2.18 vlevo, zvedne se poˇcet hran H v grafu o 3 a dokazovan´ y vzorce bude st´ale platit. 25

Pokud pˇrid´ame do grafu hraniˇcn´ı vrchol jako na obr´azku 2.18 vpravo, pˇrid´ame nˇejak´ y poˇcet nov´ ych hran, kter´ y oznaˇcme X. Poˇcet nov´ ych hran je minim´alnˇe 2 a to kv˚ uli tomu, aby se st´ale jednalo o triangulaci nˇejak´eho jednoduch´eho mnohou ´heln´ıku. Dvˇe nov´e hrany jdou do vrchol˚ u, kter´e z˚ ustaly hraniˇcn´ımi a zbyl´e jdou do vrchol˚ u, kter´e byly p˚ uvodnˇe hraniˇcn´ı, ale ted’ jsou vnitˇrn´ı, takˇze je tˇechto novˇe vnitˇrn´ıch vrchol˚ u X − 2. Poˇcet vrchol˚ u uvnitˇr se tedy zv´ yˇsil o X − 2, vrchol˚ um na hranici pˇribyl jeden nov´ y a ubylo X − 2 vrchol˚ u. Dosad’me do dokazovan´eho vzorce:
H + X = 3(I + X − 2) + 2 B + 1 − (X − 2) − 3, H + X = 3I + 2B − 3 + 3X − 2X − 6 + 6. Vid´ıme, ˇze jej m˚ uˇzeme upravit na vztah pro p˚ uvodn´ı graf bez pˇridan´eho vrcholu H = 3I + 2B − 3, proto vzorec plat´ı i pro vˇetˇs´ı graf. T´ımto je spr´avnost vzorce ovˇeˇrena.

k

Nyn´ı jiˇz m´ame vˇse d˚ uleˇzit´e a m˚ uˇzeme uk´azat d˚ ukaz Pickova vzorce s vyuˇzit´ım Eulerova vzorce. D˚ ukaz. Mˇejme mnoho´ uheln´ık s vrcholy v mˇr´ıˇzov´ ych bodech a jeho element´arn´ı triangulaci. Pouˇzijeme-li Euler˚ uv vzorec V − H + S = 2 pro tento rovinn´ y graf, dostaneme V = I + B, S = 2 − V + H, H = 3I + 2B − 3. Poˇcet element´arn´ıch troj´ uheln´ık˚ u je S − 1 a jejich obsah, jak jiˇz bylo dok´az´ano 1 uheln´ıku je pak dˇr´ıve viz Tvrzen´ı 3, je 2 . Obsah mnoho´ 1 1 B (S − 1) = (2 − (I + B) + (3I + 2B − 3) − 1) = I + − 1. 2 2 2

k 2.5

Dalˇ s´ı v´ ysledky o mˇ r´ıˇ zov´ ych bodech

Pick˚ uv vzorec nen´ı jedin´ ym v´ ysledkem o mˇr´ıˇzov´ ych bodech. V dalˇs´ım uvedeme nˇekolik zaj´ımav´ ych vˇet a, aby nen´asledoval jen jejich v´ ypis, dok´aˇzeme pomoc´ı Minkowsk´eho vˇety jin´ ym zp˚ usobem Tvrzen´ı 3 z prvn´ıho d˚ ukazu Pickova vzorce. Zaˇcneme vˇetou, kterou Blichfeldt publikoval v roce 1914 v ˇcl´anku [3]. Bez zaj´ımavosti nen´ı ani to, ˇze tvrzen´ı vˇety m˚ uˇze b´ yt dokonce zobecnˇeno do libovoln´e dimenze. Vˇ eta 7. (Blichfeldt) Kaˇzd´y omezen´y rovinn´y obrazec M s obsahem ostˇre vˇetˇs´ım neˇz A muˇze b´yt posunut tak, aby poˇcet mˇr´ıˇzov´ych bod˚ u uvnitˇr M byl alespoˇ n A+1. 26

Vˇ eta 8. (Browkin) Pro libovoln´e pˇrirozen´e ˇc´ıslo n existuje v rovinˇe ˇctverec s pr´avˇe n mˇr´ıˇzov´ymi body uvnitˇr. Toto tvrzen´ı, kter´e lze nal´ezt v [18], bylo dokonce zobecnˇeno na libovoln´ y tvar, o coˇz se zaslouˇzili Schinzel a Kulikowski. Browkin pot´e tvrzen´ı pˇrevedl do tˇr´ı dimenz´ı a dok´azal jej pro krychli. N´asleduje tvrzen´ı, kter´e dok´azal Hermann Minkowski v roce 1889. Nejdˇr´ıve vˇsak osvˇetl´ıme n´asleduj´ıc´ı pojmy. Omezen´ a mnoˇ zina je takov´a mnoˇzina, kterou lze celou uzavˇr´ıt do koule o koneˇcn´em polomˇeru. Pokud ˇrekneme o mnoˇzinˇe, ˇze je symetrick´ a kolem poˇ c´ atku, m´ame na mysli, ˇze pokud je v mnoˇzinˇe bod se souˇradnicemi [x1 , . . . ,xn ], pak je v mnoˇzinˇe tak´e bod [−x1 , . . . , − xn ]. Vˇ eta 9. (Minkowski) V n-rozmˇern´em prostoru plat´ı, ˇze kaˇzd´a omezen´a konvexn´ı mnoˇzina C, kter´a je symetrick´a kolem poˇc´atku a m´a obsah vˇetˇs´ı neˇz 2n , obsahuje nejm´enˇe jeden mˇr´ıˇzov´y bod kromˇe poˇc´atku. Speci´alnˇe: omezen´a konvexn´ı mnoˇzina v rovinˇe, kter´a je symetrick´a kolem poˇc´atku a m´a obsah vˇetˇs´ı neˇz 4, mus´ı obsahovat nejm´enˇe jeden mˇr´ıˇzov´y bod, kromˇe poˇc´atku. Lze naj´ıt nejr˚ uznˇejˇs´ı pˇr´ım´e d˚ ukazy Minkowsk´eho vˇety, napˇr´ıklad v ˇcl´anku [15], nebo je tak´e moˇzn´e tvrzen´ı v cel´e obecnosti dok´azat pomoc´ı Blichfeldtovy vˇety. Pro n´as vˇsak bude staˇcit Minkowsk´eho vˇetu dok´azat pouze v rovinˇe. Jeˇstˇe neˇz se vˇsak pust´ıme do d˚ ukazu, kter´ y postupuje podle [2], vysvˇetl´ıme, co znamen´a operace a mod b“. V´ ysledkem je zbytek po dˇelen´ı ˇc´ısla a ˇc´ıslem b. ” Pokud nav´ıc chceme ˇr´ıci, ˇze i ˇc´ıslo c m´a stejn´ y zbytek po dˇelen´ı ˇc´ıslem b jako a, zap´ıˇseme to takto c ≡ a mod b. Tento z´apis ˇcteme: c je kongruentn´ı s a modulo b. Napˇr. plat´ı 7 ≡ 22 mod 5. ˇ ısla a a c vˇsak nemus´ı b´ C´ yt pouze cel´a a kladn´a, napˇr. −1,7 ≡ 3,3 mod 5. D˚ ukaz. V d˚ ukazu budeme pouˇz´ıvat mˇr´ıˇzov´e body a dvojn´asobn´e mˇr´ıˇzov´e body, tedy takov´e body, kter´e jsou ve tvaru [2x,2y], pro x,y ∈ Z. Cel´a rovina R2 lze vydl´aˇzdit“ ˇctverci, X + (λ,µ), kde X je dvojn´asobn´ y ” mˇr´ıˇzov´ y bod a parametry λ, µ prob´ıhaj´ı cel´ y interval (0,2). Tyto ˇctverce jsou disjunktn´ı, to znamen´a, ˇze ˇza´dn´e dva z nich nemaj´ı spoleˇcn´ y bod. Mnoˇzina C je omezen´a, proto je pˇrekryta jen koneˇcn´ ym poˇctem ˇctverc˚ u X1 + (λ,µ), . . ., Xn + (λ,µ),
oznaˇcme C1 , . . ., Cn pr˚ uniky mnoˇziny C se ˇctverci, tj. C1 = C ∩ X1 + (λ,µ) , atd. Pak jsou jistˇe C1 , . . ., Cn disjunktn´ı a souˇcet jejich obsah˚ u je roven obsahu mnoˇziny C. Oznaˇcme  ˇctverec [0,0] + (λ,µ), λ, µ ∈ (0,2). Zobrazen´ı f : [x,y] 7→ [x mod 2,y mod 2] zobrazuje celou rovinu do ˇctverce  tedy f : R2 → . Toto zobrazen´ı pˇresune vˇsechny kousky C1 , . . ., Cn do ˇctverce . Obsah mnoˇziny C je stejn´ y jako souˇcet obsah˚ u jednotliv´ ych kousk˚ u C1 , . . ., Cn a je podle pˇredpokladu vˇety vˇetˇs´ı neˇz 4, coˇz je obsah ˇctverce . Proto se mus´ı alespoˇ n dva kousky f (Cj ) a f (Ck ) pˇrekr´ yvat. V tomto pˇrekryvu vyberme bod f (P1 ) = f (P2 ), ˇze P1 ∈ Cj a P2 ∈ Ck . 27

To znamen´a, ˇze pro souˇradnice bod˚ u P1 = [x1 ,y1 ] a P2 = [x2 ,y2 ] mus´ı platit x1 ≡ x2 mod 2 a y1 ≡ y2 mod 2, coˇz lze jinak zapsat tak´e jako (x1 −x2 ) ≡ 0 mod 2 a (y1 − y2 ) ≡ 0 mod 2, tj. ˇc´ısla x1 − x2 a y1 − y2 jsou dˇeliteln´a dvˇema. Protoˇze body P1 a P2 jsou r˚ uzn´e, nejsou obˇe tyto ˇc´ısla z´aroveˇ n rovna nule. Protoˇze je mnoˇzina C symetrick´a podle poˇc´atku leˇz´ı v n´ı bod −P2 = [−x2 ,−y2 ] a protoˇze je konvexn´ı leˇz´ı uvnitˇr mnoˇziny C cel´a u ´seˇcka mezi body P1 a −P2 . Stˇred t´eto u ´seˇcky bod 21 (P1 − P2 ) = [ 12 (x1 − x2 ), 12 (y1 − y2 )] tedy jistˇe leˇz´ı v mnoˇzinˇe C. Jak uˇz v´ıme, ˇc´ısla x1 − x2 a y1 − y2 jsou dˇeliteln´a dvˇema a nejsou z´aroveˇ n obˇe y nuly, proto bod 12 (P1 − P2 ) m´a celoˇc´ıseln´e souˇradnice a jedn´a se o jeden hledan´ mˇr´ıˇzov´ y bod v mnoˇzinˇe C, kter´ y nen´ı poˇc´atkem.

k

Z Minkowsk´eho vˇety m´ame, ˇze v mnoˇzinˇe leˇz´ı kromˇe poˇca´tku jeden nenulov´ y mˇr´ıˇzov´ y bod, ze symetrie mnoˇziny vˇsak dost´av´ame, ˇze tam existuje jeˇstˇe bod s t´ımto symetrick´ y. Pokud zapoˇc´ıt´ame i poˇca´tek, tedy nulov´ y mˇr´ıˇzov´ y bod, kter´ y je v mnoˇzinˇe d´ıky jej´ı konvexitˇe, dostaneme tvrzen´ı: V omezen´e konvexn´ı mnoˇzinˇe v Rn symetrick´e kolem poˇc´atku, kter´a m´a obsah vˇetˇs´ı neˇz 2n , jsou alespoˇ n tˇri mˇr´ıˇzov´e body. S pomoc´ı Minkowsk´eho vˇety uk´aˇzeme jin´ ym zp˚ usobem jeden ze z´akladn´ıch stavebn´ıch prvk˚ u d˚ ukaz˚ u Pickova vzorce a to, ˇze obsah element´arn´ıho troj´ uheln´ıku je jedna polovina, viz Tvrzen´ı 3. V prvn´ı ˇca´sti d˚ ukazu budeme postupovat podle ˇcl´anku [15]. D˚ ukaz. Necht’ ∆ABC je element´arn´ı troj´ uheln´ık. Otoˇcme tento troj´ uheln´ık o 180◦ kolem stˇredu hrany a, kter´a je proti vrcholu A. Nov´ y troj´ uheln´ık oznaˇcme jako ∆A0 B 0 C 0 , vrchol B 0 odpov´ıd´a v otoˇcen´ı vrcholu C a C 0 = B. Tato rotace pˇresouv´a mˇr´ıˇzov´e body na mˇr´ıˇzov´e body. Protoˇze jedin´e mˇr´ıˇzov´e body, kter´e byly v ∆ABC, jsou jeho vrcholy, uvnitˇr rovnobˇeˇzn´ıku ABA0 C tak´e nebudou ˇza´dn´e mˇr´ıˇzov´e body.

A

C =B 0 A0 B =C 0

Obr´azek 2.19: N´aˇcrt rovnobˇeˇzn´ıku vznikl´eho z element´arn´ıho troj´ uheln´ıku D´ale proved’me rotaci kolem stˇred˚ u zb´ yvaj´ıc´ıch hran. Z´ısk´ame troj´ uheln´ık, jehoˇz stˇredn´ı pˇr´ıˇcky tvoˇr´ı p˚ uvodn´ı troj´ uheln´ık ∆ABC. Uvnitˇr tohoto troj´ uheln´ıku tak´e nen´ı ˇz´adn´ y vnitˇrn´ı mˇr´ıˇzov´ y bod. Otoˇcme cel´ y velk´ y troj´ uheln´ık kolem bodu B o 180◦ . P˚ uvodn´ı a otoˇcen´ y troj´ uheln´ık tvoˇr´ı rovnobˇeˇzn´ık, kter´ y je omezen´ y, konvexn´ı a symetrick´ y kolem bodu B, kter´ y je jedin´ y vnitˇrn´ı bod v rovnobˇeˇzn´ıku a kter´ y oznaˇcme jako poˇca´tek. Podle Minkowsk´eho vˇety nem˚ uˇze m´ıt rovnobˇeˇzn´ık obsah vˇetˇs´ı neˇz 4. Rovnobˇeˇzn´ık je tvoˇren osmi element´arn´ımi troj´ uheln´ıky shodn´ ymi s ∆ABC, a tak obsah element´arn´ıho troj´ uheln´ıku m˚ uˇze b´ yt nejv´ yˇse 21 . Pro v´ ypoˇcet doln´ıho odhadu obsahu troj´ uheln´ıku s vrcholy o celoˇc´ıseln´ ych souˇradnic´ıch A = [a1 ,a2 ],B = [b1 ,b2 ] a C = [c1 ,c2 ] pouˇzijeme vektorov´ y souˇcin. 28

Plat´ı totiˇz

1 1 S∆ = |~b||~c | sin α = |~b × ~c | 2 2

pro vektory ~b = (a1 − c1 ,a2 − c2 ,0) a ~c = (a1 − b1 ,a2 − b2 ,0) a u ´hel α mezi nimi pˇri vrcholu A. C → − b A

→ −c α

B

Obr´azek 2.20: vektorov´ y souˇcin

Dost´av´ame S∆ =


1 (a1 − c1 )(a2 − b2 ) − (a1 − b1 )(a2 − c2 ) , 2

coˇz je 12 kr´at nˇejak´e nenulov´e cel´e ˇc´ıslo, tedy obsah troj´ uheln´ıku bude nejm´enˇe 21 . v pˇredchoz´ı ˇca´sti d˚ ukazu jsme zjistili, ˇze obsah troj´ uheln´ıku m˚ uˇze b´ yt nejv´ yˇse 12 , a tak dost´av´ame, ˇze obsah element´arn´ıho troj´ uheln´ıku je 12 .

k

29

30

Kapitola 3 Zobecnˇ en´ı a rozˇ s´ıˇ ren´ı V t´eto kapitole budeme uvaˇzovat, jak rozˇs´ıˇrit Pick˚ uv vzorec pro sloˇzitˇejˇs´ı tvary a nebudeme se jiˇz omezovat pouze na jednoduch´e mnoho´ uheln´ıky. V druh´e ˇc´asti se dotkneme ot´azky rozˇs´ıˇren´ı Pickova vzorce do prostoru.

3.1

Zobecnˇ en´ı pro rozmanitˇ ejˇ s´ı tvary

Pro zobecnˇen´ı budeme vych´azet z ˇcl´anku [17]. Budeme uvaˇzovat obecn´ y mnoho´ uheln´ık M , kter´ y m´a vrcholy v mˇr´ıˇzov´ ych bodech, a m˚ uˇze obsahovat d´ıry nebo se jeho hrany mohou prot´ınat. Jedin´e, co poˇzadujeme, je, aby mnoho´ uheln´ık byl sjednocen´ım koneˇcn´eho poˇctu troj´ uheln´ık˚ u, kter´e maj´ı vrcholy v mˇr´ıˇzov´ ych bodech. Pick˚ uv vzorec je potˇreba pro takov´eto obecnˇejˇs´ı mnoho´ uheln´ıky drobnˇe upravit. H. Hadwiger a J. M. Wills v ˇcl´anku [8] uvedli a uk´azali tento zobecnˇen´ y Pick˚ uv vzorec. Vˇ eta 10. (Zobecnˇ en´ y Pick˚ uv vzorec) Bud’ M mnoho´ uheln´ık, jehoˇz vrcholy jsou mˇr´ıˇzov´e body. Pak H − χ, S=V − 2 kde V je poˇcet vˇsech mˇr´ıˇzov´ych bod˚ u uvnitˇr a na hran´ach mnoho´ uheln´ıku, H je poˇcet jeho hran (spojnic od mˇr´ıˇzov´eho bodu k mˇr´ıˇzov´emu bodu) a χ je Eulerova charakteristika.

V =8 H = 15 S=7 χ=0

Obr´azek 3.1: Moˇzn´a triangulace pro poˇc´ıt´an´ı Eulerovy charakteristiky

O Eulerovˇe charakteristice jsme se jiˇz zm´ınili pˇred Vˇetou 6, mluvili jsme ale o prostorov´ ych tˇelesech. Eulerova charakteristika pro mnoho´ uheln´ıky se poˇc´ıt´a podobnˇe. Najdeme nˇejakou triangulaci tohoto mnoho´ uheln´ıku a spoˇcteme 31

poˇcet vrchol˚ u V , poˇcet hran H a poˇcet troj´ uheln´ık˚ u, neboli vnitˇrn´ıch stˇen S, kter´e patˇr´ı do mnoho´ uheln´ıku, pak je Eulerova charakteristika rovna χ = V − H + S. Pro jednoduch´ y mnoho´ uheln´ık vych´az´ı Eulerova charakteristika 1, pro mnohou ´heln´ık, kter´ y m´a m oddˇelen´ ych dˇer, je Eulerova charakteristika rovna 1 − m. Pro jednoduch´e mnoho´ uheln´ıky zobecnˇen´ y Pick˚ uv vzorec plat´ı, protoˇze poˇcet bod˚ u na hranici mnoho´ uheln´ıku je roven poˇctu hran, ze kter´eho se hranice mnoho´ uheln´ıku skl´ad´a B = H a Eulerova charakteristika je 1. Neˇz budeme dokazovat zobecnˇen´ y Pick˚ uv vzorec v pln´e obecnosti, ovˇeˇrme jej v pˇr´ıpadˇe mnoho´ uheln´ıku s m oddˇelen´ ymi d´ırami, kter´e jsou samy o sobˇe jednoduch´e mnoho´ uheln´ıky. Napˇr´ıklad vlevo na obr´azku 3.2 je takov´ y mnoho´ uheln´ık s m = 3. Eulerova charakteristika je pro takov´ y mnoho´ uheln´ık s m d´ırami rovna χ = 1 − m.

V = 40 H = 36 χ = −2 S = 40 − 12 · 36 + 2

V = 20 H = 16 χ=1 S = 20 − 12 · 16 − 1

V = 26 H = 24 χ = −2 S = 26 − 21 · 24 + 2

Obr´azek 3.2: Nejednoduch´e mnoho´ uheln´ıky

K ovˇeˇren´ı zobecnˇen´eho Pickova vzorce (10) pouˇzijeme pro mnoho´ uheln´ık s m d´ırami princip z d˚ ukazu Pickova vzorce pˇres u ´hly viditelnosti, viz podkapitola 2.2. Oznaˇcme B0 , B1 , . . . ,Bm poˇcty mˇr´ıˇzov´ ych bod˚ u na vnˇejˇs´ı hranici a na hranic´ıch jednotliv´ ych m dˇer. Celkov´ y poˇcet mˇr´ıˇzov´ ych bod˚ u na hranici pak je B0 + B1 + . . . + Bm = B a poˇcet hran je roven poˇctu mˇr´ıˇzov´ ych bod˚ u na hranici mnoho´ uheln´ıku H = B. Pro celkov´ y poˇcet mˇr´ıˇzov´ ych bod˚ u pak zˇrejmˇe plat´ı V = I + B = I + H. D´ale si staˇc´ı uvˇedomit, ˇze souˇcet u ´hl˚ u viditelnosti dovnitˇr mnoho´ uheln´ıku na k-t´e d´ıˇre, je (Bk +2)π, zat´ımco na vnˇejˇs´ı hranici je to (B0 −2)π. Pak jiˇz m˚ uˇzeme vypoˇc´ıtat obsah mnoho´ uheln´ıku jako souˇcet poˇctu vnitˇrn´ıch mˇr´ıˇzov´ ych bod˚ u I a tˇech u ´hl˚ u viditelnosti θk dovnitˇr mnoho´ uheln´ıku vydˇelen´ ych 2π, kter´e odpov´ıdaj´ı mˇr´ıˇzov´ ym bod˚ um Pk leˇz´ıc´ım na hranici mnoho´ uheln´ıku, 32

tj. vˇsem mˇr´ıˇzov´ ym bod˚ um z mnoˇziny B. S=I+

1 X θk = 2π P ∈B k

(Bm + 2) (B0 − 2) (B1 + 2) + + ... + = 2 2 2 1 = I + (B0 + B1 + . . . + Bm ) + (m − 1) = 2 H B − χ. =I + −χ=V − 2 2 =I+

Postup s vyuˇzit´ım u ´hl˚ u viditelnosti jiˇz bohuˇzel nebude fungovat pro prostˇredn´ı a prav´ y mnoho´ uheln´ık na obr´azku 3.2, protoˇze na nich se hranice mnoho´ uheln´ıku prot´ın´a a jiˇz poˇcet vrchol˚ u na hranici neodpov´ıd´a poˇctu hraniˇcn´ıch u ´sek˚ u, tj. B 6= H. Zde jsme jiˇz nuceni ke klasick´emu pouˇzit´ı element´arn´ıch troj´ uheln´ık˚ u. D˚ ukaz. Pˇredpokl´adejme, ˇze obecn´ y mnoho´ uheln´ık, jehoˇz obsah n´as zaj´ım´a, je rozdˇelen na element´arn´ı troj´ uheln´ıky, tj. m´ame nˇejakou jeho element´arn´ı triangulaci s vrcholy v mˇr´ıˇzov´ ych bodech. Oznaˇcme V , Ht a St poˇcet vrchol˚ u, hran a troj´ uheln´ık˚ u v t´eto triangulaci. Kaˇzd´ y troj´ uheln´ık m´a 3 hrany a kaˇzd´a z hran n´aleˇz´ı dvˇema troj´ uheln´ık˚ um kromˇe hran, kter´e jsou na okraji mnoho´ uheln´ıku M . Takˇze dost´av´ame 3St = 2Ht − H, pokud tuto rovnost uprav´ıme, dostaneme St = −H + 2Ht − 2St = −H + 2V − 2(V − Ht + St ) = 2V − H − 2χ. y Kaˇzd´ y element´arn´ı troj´ uheln´ık m´a obsah 21 , z ˇcehoˇz jiˇz dost´av´ame poˇzadovan´ vztah pro obsah mnoho´ uheln´ıku S = 12 St = V − H2 − χ.

k

3.2

Rozˇ s´ıˇ ren´ı do prostoru

Minkowsk´eho vˇeta plat´ı i pro prostory vyˇsˇs´ı dimenze. Mohli bychom si proto myslet, ˇze i Pick˚ uv vzorec lze zobecnit pro v´ıcedimenzion´aln´ı prostory. Avˇsak tak jednoduch´e to nen´ı. Uˇz v trojrozmˇern´em prostoru lehce najdeme mnohostˇeny, jejichˇz vrcholy leˇz´ı v mˇr´ıˇzov´ ych bodech a kter´e maj´ı stejn´ y poˇcet mˇr´ıˇzov´ ych bod˚ u uvnitˇr a na hranici mnohostˇenu, ale jejichˇz obsah je r˚ uzn´ y. [0,0,1] [1,1,1]

[0,1,0] [1,0,0]

ˇ rstˇen vepsan´ Obr´azek 3.3: Ctyˇ y do krychle

33

Obr´azek z knihy [11] ukazuje jednotkovou krychli rozdˇelenou na pˇet jehlan˚ u. Vnitˇrn´ı jehlan s vrcholy [0,0,1], [1,0,0], [0,1,0] a [1,1,1] m´a vˇsechny strany rovnoˇ ri vnˇejˇs´ı jehlany pak maj´ı strann´e troj´ uheln´ıky a je pravideln´ ym ˇctyˇrstˇenem. Ctyˇ tˇri stˇeny pravo´ uhl´e troj´ uheln´ıky a jednu stˇenu rovnostrann´ y troj´ uheln´ık. Vˇsechny jehlany maj´ı ˇctyˇri mˇr´ıˇzov´e body na sv´e hranici a ˇz´adn´e vnitˇrn´ı mˇr´ıˇzov´e body. Pokud by existoval nˇejak´ y jednoduch´ y vzorec, kter´ y by podobnˇe jako Pick˚ uv, vyuˇz´ıval pouze poˇcet mˇr´ıˇzov´ ych bod˚ u k urˇcen´ı objemu mnohostˇenu v prostoru, mˇely by vˇsechny tyto jehlany stejn´ y objem. Ale pokud pouˇzijeme vzorec pro obsah jehlanu tj. obsah z´akladny kr´at jedna tˇretina v´ yˇsky, dostaneme, ˇze kaˇzd´ y ze 1 ˇctyˇr vnˇejˇs´ıch jehlan˚ u m´a objem 6 . Protoˇze cel´a jednotkov´a krychle m´a objem 1, mus´ı b´ yt obsah vnitˇrn´ıho pravideln´eho jehlanu 1 − 4 · 16 = 13 . Dalˇs´ı ilustrace tentokr´at z [15] tak´e ukazuje, proˇc neexistuje jednoduch´a analogie Pickova vzorce v prostoru. Uvaˇzujme jehlan, kter´ y m´a jako z´akladnu troju ´heln´ık s vrcholy [0,0,0], [1,0,0] a [1,1,0] a jehoˇz vrchol je v bodˇe [0,1,n], kde n ∈ N. Tento jehlan jistˇe pro libovoln´e n ∈ N neobsahuje ˇz´adn´e dalˇs´ı mˇr´ıˇzov´e body, objem vˇsak m´a podle vzorce pro objem jehlanu roven n6 . [0,1,n]

[0,0,0]

[1,0,0]

[1,1,0]

Obr´azek 3.4: Jehlan, kter´ y m´a jen 4 vrcholy, ale r˚ uzn´ y objem podle polohy hlavn´ıho vrcholu J. E. Reeve [16] zobecnil Pick˚ uv vzorec pro tˇr´ıdimenzion´aln´ı prostor s vyuˇzit´ım p˚ ulmˇr´ıˇzov´ ych bod˚ u“. Tˇemito p˚ ulmˇr´ıˇzov´ ymi body mysl´ıme takov´e body [a,b,c], ” ˇze [2a,2b,2c] ∈ Z3 . Reeve dok´azal urˇcit obsah mnohostˇenu, jehoˇz vrcholy jsou mˇr´ıˇzov´e body, pomoc´ı poˇctu mˇr´ıˇzov´ ych a p˚ ulmˇr´ıˇzov´ ych bod˚ u uvnitˇr a na hranici mnohostˇenu. D´ale se rozˇs´ıˇren´ım Pickova vzorce do prostoru nebudeme zab´ yvat. Tomu, koho by toto t´ema zaj´ımalo, doporuˇcuji ˇcl´anek [9].

34

Medailonek o Georgu Pickovi

Obr´azek 3.5: Georg Alexander Pick Georg Alexander Pick se narodil 10. srpna 1859 ve V´ıdni do ˇzidovsk´e rodiny, jeho rodiˇce byli Josefa Schleisinger a Adolf Josef Pick. Jeho otec jej vyuˇcoval doma aˇz do jeden´acti let, pak nastoupil na gymn´azium a n´aslednˇe v letech 1875 aˇz 1879 studoval na univerzitˇe ve V´ıdni matematiku a fyziku. V roce 1880 z´ıskal doktor´at pod veden´ım L. K¨onigsbergera, kter´ y je povaˇzov´an za ˇza´ka K. Weierstrasse. Po dokonˇcen´ı doktor´atu ve V´ıdni pˇrijal m´ısto pomocn´eho asistenta E. Macha na Karlo-Ferdinandovˇe univerzitˇe v Praze. V roce 1882 byl Georg Pick habilitov´an, v roce 1888 byl jmenov´an mimoˇra´dn´ ym profesorem a v roce 1892 ˇr´adn´ ym profesorem matematiky na Praˇzsk´e nˇemeck´e univerzitˇe. Dva semestry pravdˇepodobnˇe 1884-1885 str´avil na univerzitˇe v Lipsku, kde byl ovlivnˇen prac´ı F. Kleina. Ve ˇskoln´ım roce 1900-1901 byl dˇekanem filozofick´e fakulty. V roce 1927 byl jmenov´an emeritn´ım profesorem. (Zaslouˇzil´ y profesor, kter´ y v r´amci sv´e penze st´ale m˚ uˇze p˚ usobit na univerzitˇe.) Aktivn´ı p˚ usoben´ı na univerzitˇe ukonˇcil v roce 1929 a vr´atil se do V´ıdnˇe. Po obsazen´ı Rakouska se odstˇehoval v roce 1938 zp´atky do ˇ e akademie vˇed a umˇen´ı, ale po obsazen´ı Prahy. Zde byl Pick zvolen ˇclenem Cesk´ ˇ ri roky pot´e, co se vr´atil do Prahy, byl Prahy nacisty byl z akademie vylouˇcen. Ctyˇ dne 13. ˇcervence 1942 deportov´an pod ˇc´ıslem 824 transportem AAq do Terez´ına. Tam o dva t´ ydny pozdˇeji 26. ˇcervence 1942 zemˇrel ve vˇeku nedoˇzit´ ych 83 let. Georg Pick p˚ usobil 46 let v Praze jako vysokoˇskolsk´ y uˇcitel. V pedagogick´e ˇcinnosti se vˇenoval hlavnˇe anal´ yze a geometrii. Vedl 20 disertaˇcn´ıch prac´ı. Mezi jeho doktorsk´e studenty patˇr´ı napˇr´ıklad E. Str´ansk´ y nebo K. L¨owner, pozdˇejˇs´ı profesor nˇemeck´e univerzity v Praze a po nucen´e emigraci profesor na v´ yznamn´ ych americk´ ych univerzit´ach. V letech 1876 aˇz 1939 publikoval Georg Pick 67 prac´ı. Tyto pr´ace jsou napˇr´ıklad z integr´aln´ıho poˇctu, komplexn´ı anal´ yzy, diferenci´aln´ıch rovnic, geometrie 35

a diferenci´aln´ı geometrie. Jm´eno Pick nen´ı v matematice zapomenuto, kromˇe Pickova vzorce jeho jm´eno nese jeˇstˇe Schwarzovo-Pickovo lemma, kter´e rozˇsiˇruje Schwarzovo lemma z komplexn´ı anal´ yzy, nebo Pickova matice, kter´a souvis´ı s interpolac´ı analytick´ ych funkc´ı. Za zm´ınku tak´e stoj´ı pˇr´atelstv´ı mezi Georgem Pickem a Albertem Einsteinem. Pick byl hybnou silou pˇri schvalov´an´ı Einsteinovy ˇz´adosti o m´ısto profesora teoretick´e fyziky na univerzitˇe v Praze. Bˇehem jeho pobytu v letech 1911 aˇz 1912 byl Georg Pick Einsteinov´ ym velmi bl´ızk´ ym kolegou. Poutal je nejen profesion´aln´ı vztah, ale oba hr´ali na housle a ˇcasto hr´avali spolu. Napˇr´ıklad M. Brdiˇcka [5] o jejich vztahu p´ıˇse. Einstein˚ uv duchovn´ı ˇzivot se v t´e dobˇe skl´adal ” hlavnˇe z vˇedy a hudby. Spˇra´telil se s G. Pickem, kter´ y byl nejen v´ yborn´ ym geometrem ochotn´ ym pomoci pˇri nejasnostech absolutn´ıho diferenci´aln´ıho poˇctu a pˇri jeho aplikac´ıch na geometrizaci fyziky, resp. v poloˇzen´ı z´aklad˚ u obecn´e relativity, ale i nevˇsedn´ım komorn´ım hudebn´ıkem, jenˇz zprostˇredkoval Einsteinovi m´ısto ve smyˇccov´em kvartetu. Pˇr´atelsk´e kontakty mezi Pickem a o 20 let mladˇs´ım Einsteinem nebyly pˇreruˇseny ani po Einsteinovˇe odchodu z Prahy. Poˇ sledn´ı Pick˚ uv dopis Einsteinovi do Princetonu je z r. 1939, z doby po okupaci Cech a nedlouho pˇred Pickov´ ym transportem do koncentraˇcn´ıho t´abora v Terez´ınˇe, z nˇehoˇz se jiˇz nevr´atil.“ V dobˇe Einsteinova pobytu v Praze vedl tak´e Georg Pick pˇredn´aˇsku Infinitesimalgeometrie. Nen´ı tak´e ˇz´adn´ ych pochyb,“ jak uv´ad´ı ” [13], ˇze Pick a Einstein vedli odborn´e diskuze.“ Svˇedˇc´ı o tom napˇr. z´avˇereˇcn´a ” pozn´amka v rozˇs´ıˇren´em textu Einsteinovy pˇredn´aˇsky z 28. 2. 1914; viz dokument 30 v [10], strana 607: Na z´avˇer vyslovuji podˇekov´an´ı m´emu dˇr´ıvˇejˇs´ımu kolegovi ” G. Pickovi za jeho pozn´amky, kter´e v´ yklad vˇeci z´asadnˇe zjednoduˇsily.“ ˇ Casto se polemizuje, jakou roli sehr´al Georg Pick v Einsteinovˇe odvozen´ı speci´aln´ı teorie relativity. Cit´aty z nejr˚ uznˇejˇs´ıch zdroj˚ u k tomuto t´ematu lze naj´ıt v ˇcl´anku Georg Pick – praˇzsk´ y kolega Alberta Einsteina od I. Netuky [13].

36

Z´ avˇ er Tato pr´ace zdaleka nevyˇcerpala vˇsechna t´emata, kter´a souvis´ı s Pickov´ ym vzorcem. Na z´avˇer jeˇstˇe zm´ın´ıme nˇekolik souvislost´ı, kter´e v pr´aci nejsou v´ıce rozebr´any. V kapitole 3.2 jsme se jiˇz trochu dotkli t´ematu rozˇs´ıˇren´ı Pickova vzorce do prostoru. Nab´ız´ı se vˇsak ot´azka, zda existuje analogie Pickova vzorce v n-dimenzion´aln´ıch prostorech, pro n > 3, nebo zda lze vyslovit nˇejak´a dalˇs´ı zaj´ımav´a tvrzen´ı o mˇr´ıˇzov´ ych bodech v n-dimenzion´aln´ım prostoru jako jsou Vˇety 7 a 9. Pokraˇcovat by se dalo tak´e v Pˇr´ıkladu 13 o tom, jak rozmˇenit dolar. Co kdybychom nerozmˇen ˇovali dolar, ale tˇreba ˇceskou dvoustovku na pades´atikoruny, pˇetikoruny a dvoukoruny. Vyˇreˇsen´ı t´eto u ´lohy jistˇe nebude probl´em. Pouˇzijeme stejn´ y princip jako u rozmˇen ˇov´an´ı dolaru. Ale pojd’me d´al. Co kdybychom pˇridali jeˇstˇe dvacetikoruny. Najednou jiˇz nelze pouˇz´ıt u ´plnˇe stejn´ y postup, ale mus´ıme jej upravit, protoˇze jsme se dostali od probl´emu, kter´ y lze ˇreˇsit pˇreveden´ım na poˇc´ıt´an´ı mˇr´ıˇzov´ ych bod˚ u v rovinˇe, k probl´emu, kter´ y lze pˇrev´est na hled´an´ı poˇctu mˇr´ıˇzov´ ych bod˚ u v prostoru. Podobnou u ´lohou se zab´ yv´a i kniha [11], kdyˇz ˇreˇs´ı ’ ot´azku: Kolika zp˚ usoby lze rozmˇenit dolar na ˇctvrt a´ky, deseticenty, pˇeticenty a centy? V t´eto knize tak´e najdete obecn´ y vzorec pro poˇcet moˇznost´ı jak sloˇzit nˇejakou ˇca´stku ze tˇr´ı druh˚ u minc´ı. Pokud bychom se vr´atili do Pickova ˇcl´anku [14], kde profesor Georg Pick publikoval sv˚ uj vzorec, zjist´ıme, ˇze jej formuloval mnohem obecnˇeji. Neuvaˇzoval pouze pravo´ uhlou ˇctvercovou s´ıt’, ale dokonce i kosod´eln´ıkovou s´ıt’. V takov´em pˇr´ıpadˇe je objem mnoho´ uheln´ıku s vrcholy v mˇr´ıˇzov´ ych bodech odpov´ıdaj´ıc´ıch kosod´eln´ıkov´e s´ıti roven B S = Sk (I + − 1), 2 kde Sk znaˇc´ıme obsah nejmenˇs´ıho kosod´eln´ıku, ze kter´eho se skl´ad´a kosod´eln´ıkov´a s´ıt’, I je poˇcet mˇr´ıˇzov´ ych bod˚ u uvnitˇr mnoho´ uheln´ıku a B je poˇcet mˇr´ıˇzov´ ych bod˚ u na hranici mnoho´ uheln´ıku s t´ım rozd´ılem, ˇze mˇr´ıˇzov´e body uvaˇzujeme v kosod´eln´ıkov´e s´ıti. Odvozen´ı tohoto tvrzen´ı a mnohem v´ıce lze nal´ezt v ˇcl´anku [9].

Obr´azek 3.6: Kosod´eln´ıkov´a s´ıt’ se zakreslen´ ym mnoho´ uheln´ıkem

Dalˇs´ı smˇer, kter´ ym bychom se mohli ub´ırat, je souvislost Pickova vzorce s Fareyov´ ymi posloupnostmi a Stern-Brocotov´ ym stromem v teorii ˇc´ısel, viz [4]. 37

Pokud hled´ate dalˇs´ı pˇr´ıklady, kter´e souvisej´ı s Pickov´ ym vzorcem, moˇzn´ ym zdrojem je kniha [11].

38

Literatura [1] Aigner, M. Ziegler G. M. Proofs from THE BOOK (4th ed.). Berlin, New York: Springer-Verlag, 2009. ISBN 978-3-642-00855-9. [2] Bensimon, I. Minkowski’s Convex Body Theorem. Project for MA341, Boston University, 2009. http://math.bu.edu/people/kost/teaching/MA341/Minkow.pdf. [3] Blichfeldt, H. F. A New Principle in the Geometry of Numbers, with Some Applications. Trans. Amer. Math. Soc. 15, 1914, 227-235. [4] Bogomolny, A. Applications of Pick’s Theorem from Interactive Mathematics Miscellany and Puzzles. http://www.cut-the-knot.org/ctk/PickApps.shtml, Accessed 15 August 2013. ˇ a einsteinovsk´a pohlednice. Cs. ˇ ˇcas. fyz. ˇka, M. Einstein a Praha, Cesk´ [5] Brdic A 29, 1979, 269–275. [6] Funkenbusch, W. W. From Euler’s formula to Pick’s formula using an edge theorem. American Mathematical Monthly 81, 1974, 647–648. [7] Ostermann, A.,Wanner, G. Geometry by Its History. New York: Springer, 2012. ISBN 978-3-642-29162-3. [8] Hadwiger, H., Wills, J. M. Neuere Studien u ¨ber Gitterpolygone. J. Math, 280, 1975, 61-69. [9] Iseri, H. An Exploration of Pick’s Theorem in Space. Mathematics Magazine Vol. 81, No. 2, April, 2008, 106-115. [10] Klein, M. J., Kox, A. J., Schulmann, R. (Eds.) The collected papers of Albert Einstein Princeton: Princeton University Press, Vol. 5. 1993. [11] Michael, T. S. How to Guard an Art Gallery and Other Discrete Mathematical Adventures. Baltimore: JHU Press, 2009. ISBN 9780801897047. [12] Montgomery, H. A Timely Problem. Mathematics Magazine Vol. 85, No. 3, June 2012, 220. [13] Netuka, I. Georg Pick - praˇzsk´y matematick´y kolega Alberta Einsteina. Pokroky matematiky, fyziky a astronomie, Vol. 44, 1999, No. 3, 227-232. 39

[14] Pick, A. G. Geometrisches zur Zahlenlehre, Sitzungsberichte Lotos. Praha: Naturwissenschaftlich-Medizinschen Vereines f¨ ur B¨ohmen, NF 19, 1899, 311–319. [15] Ram Murty, M., Nithum Thain, Pick’s Theorem via Minkowski’s Theorem. The American Mathematical Monthly Vol. 114, No. 8, October, 2007, 732-736. [16] Reeve, J. E. On the volume of lattice polyhedra. Proceedings of the London Mathematical Society (3rd Ser.), 7, 1957, 378–395. [17] Varberg, D. E. Pick’s theorem revisited. American Mathematical Monthly 92, 1985, 584–587. [18] Weisstein, E. W. Browkin’s Theorem. From MathWorld–A Wolfram Web Resource. http://mathworld.wolfram.com/BrowkinsTheorem.html.

40