Twierdzenie Picka

Q: Jak liczyć punkty na brzegu wzdłuż ukośnej krawędzi?

Liczba punktów kratowych na odcinku od (x_1, y_1) do (x_2, y_2) (bez jednego końca) wynosi mathrmNWD(|x_2 - x_1|, |y_2 - y_1|). Dla odcinka z (0,0) do (4,6) to mathrmNWD(4,6) = 2.

Pole wielokąta, którego wszystkie wierzchołki leżą w punktach kratowych, wynosi

$P = W + \frac{B}{2} - 1,$

gdzie $W$ to liczba punktów kratowych wewnątrz wielokąta, a $B$ - liczba punktów kratowych na jego brzegu.

Co mówi twierdzenie

Punkty kratowe to punkty o obu współrzędnych całkowitych - węzły zwykłej kratki w zeszycie. Twierdzenie Picka mówi coś zaskakującego: żeby policzyć pole takiego wielokąta, nie trzeba niczego mierzyć ani dzielić figury na trójkąty. Wystarczy policzyć kropki.

Nie ma znaczenia, jak dziwaczny jest kształt: wielokąt może być wklęsły, mieć sto wierzchołków i wyglądać jak kontur wyspy. Dopóki wszystkie wierzchołki siedzą w węzłach kratki, wzór działa.

Wielokąt kratowy: 9 punktów wewnątrz (kropki pełne) i 12 na brzegu (kropki z obwódką), więc pole wynosi 9 + 6 − 1 = 14.

Przykład - policzmy pole z rysunku

Krok 1. Liczymy punkty wewnętrzne. Na rysunku są to kropki pełne: trzy kolumny po trzy punkty, czyli

$W = 9.$

Krok 2. Liczymy punkty na brzegu. To kropki z obwódką: pięć na dolnej krawędzi, trzy nowe na prawej, po jednym w wierzchołkach górnych i dwa na lewej krawędzi:

$B = 12.$

Krok 3. Podstawiamy do wzoru.

$P = 9 + \frac{12}{2} - 1 = 9 + 6 - 1 = 14.$

Krok 4. Sprawdzamy niezależnie. Wielokąt ma wierzchołki $(0,0)$ , $(4,0)$ , $(4,3)$ , $(2,4)$ , $(0,3)$ . Wzór szniurowy (Gaussa) daje

$P = \tfrac{1}{2}\left| 0 + 12 + 10 + 6 + 0 \right| = \tfrac{1}{2} \cdot 28 = 14.$

Ten sam wynik - a przy liczeniu kropek nie trzeba było znać ani jednej współrzędnej.

Dowód

Pokaż dowódUkryj dowód

Dowód składa się z czterech kroków: sprawdzamy wzór na najprostszych figurach, pokazujemy, że dobrze się skleja, i rozkładamy dowolny wielokąt na te proste kawałki.

Krok 1. Wzór jest addytywny. Niech wielokąt będzie sklejony z dwóch wielokątów kratowych $M_1$ i $M_2$ wzdłuż wspólnej łamanej zawierającej $k$ punktów kratowych (licząc oba końce). Oznaczmy $f(M) = W + \tfrac{B}{2} - 1$ . Punkty wspólnej krawędzi, poza dwoma końcami, były brzegowe w obu kawałkach, a w sklejeniu stają się wewnętrzne. Liczymy:

$f(M_1) + f(M_2) = \left(W_1 + W_2 + (k-2)\right) + \frac{B_1 + B_2 - 2(k-2) - 2}{2} - 1 = f(M).$

Zatem jeśli wzór działa dla obu kawałków, działa też dla sklejenia (i odwrotnie). Pole też jest addytywne, więc wystarczy sprawdzić wzór na kawałkach elementarnych.

Krok 2. Prostokąt o bokach równoległych do osi. Prostokąt o wymiarach $m \times n$ ma $W = (m-1)(n-1)$ punktów wewnątrz i $B = 2(m+n)$ na brzegu:

$W + \frac{B}{2} - 1 = (m-1)(n-1) + (m+n) - 1 = mn = P.$

Krok 3. Trójkąt prostokątny o przyprostokątnych równoległych do osi. Dwa takie przystające trójkąty sklejają się wzdłuż przekątnej w prostokąt z kroku 2. Oba mają tę samą liczbę punktów wewnętrznych i brzegowych, a wzór jest addytywny (krok 1), więc skoro działa dla prostokąta, musi działać i dla połówki.

Krok 4. Dowolny trójkąt, a potem dowolny wielokąt. Każdy trójkąt kratowy da się uzupełnić trójkątami prostokątnymi (z kroku 3) do prostokąta z kroku 2 - a z addytywności wzór przenosi się na niego. Wreszcie każdy wielokąt kratowy można striangulować, czyli podzielić przekątnymi na trójkąty o wierzchołkach kratowych. Stosując addytywność tyle razy, ile jest trójkątów, otrzymujemy wzór dla całego wielokąta. $\blacksquare$

Kiedy wzór przestaje działać

Wielokąt z dziurą. Jeśli figura ma otwór (np. ramka), wzór trzeba poprawić. Dla figury z $h$ dziurami:

$P = W + \frac{B}{2} - 1 + h,$

przy czym punkty na brzegach dziur liczymy do $B$ . To wersja „z charakterystyką Eulera” - liczba $-1$ w oryginalnym wzorze to właśnie charakterystyka Eulera dysku.

Wierzchołki poza kratą. Trójkąt o wierzchołkach $(0,0)$ , $(1,0)$ , $(0{,}5;\ 0{,}5)$ ma pole $0{,}25$ , ale $W = 0$ i $B = 2$ , co dałoby $0 + 1 - 1 = 0$ . Wzór wymaga, by wszystkie wierzchołki leżały w punktach kratowych.

Trzy wymiary. Analogiczny wzór dla wielościanów nie istnieje. Pokazał to John Reeve w 1957 roku: czworościan o wierzchołkach $(0,0,0)$ , $(1,0,0)$ , $(0,1,0)$ , $(1,1,n)$ dla każdego $n$ ma tylko $4$ punkty kratowe (same wierzchołki), a jego objętość wynosi $\tfrac{n}{6}$ - rośnie bez ograniczeń przy niezmienionej liczbie punktów. Żaden wzór typu Picka nie ma prawa działać.

Po co to komu

Zadania olimpijskie - twierdzenie Picka zamienia geometrię w rachunek na liczbach całkowitych; szczególnie pomaga, gdy trzeba wykazać, że jakiegoś wielokąta nie da się narysować na kratce (np. trójkąta równobocznego - jego pole $\tfrac{a^2\sqrt{3}}{4}$ jest niewymierne, a wzór Picka zawsze daje wielokrotność $\tfrac{1}{2}$ ).
Geometria obliczeniowa i GIS - szybkie szacowanie pola obszaru zapisanego jako siatka pikseli lub komórek mapy.
Grafika komputerowa - zliczanie pikseli pokrywanych przez wielokąt (rasteryzacja).

Wniosek z ostatniego przykładu warto zapamiętać: pole wielokąta kratowego jest zawsze wielokrotnością $\tfrac{1}{2}$ , bo $W$ i $B$ są liczbami całkowitymi. Stąd natychmiast wiadomo, że trójkąta równobocznego nie da się umieścić wierzchołkami na kratce.

Kto i kiedy

Twierdzenie ogłosił w 1899 roku Georg Alexander Pick, austriacki matematyk pracujący w Pradze. Przez kilkadziesiąt lat wynik pozostawał ciekawostką; rozsławił go dopiero Hugo Steinhaus, umieszczając go w 1969 roku w Kalejdoskopie matematycznym.

Pick zapisał się w historii nauki jeszcze inaczej: to on wprowadził Alberta Einsteina, wówczas profesora w Pradze, w rachunek tensorowy Ricciego i Levi-Civity - narzędzie, bez którego nie powstałaby ogólna teoria względności (o matematycznych zmaganiach Einsteina: „moje trudności z matematyką są jeszcze większe”). Zginął w 1942 roku w obozie w Theresienstadt.

Najczęstsze pytania

Czy wielokąt musi być wypukły? Nie. Wzór działa dla dowolnego wielokąta prostego (bez samoprzecięć), także mocno wklęsłego.

Jak liczyć punkty na brzegu wzdłuż ukośnej krawędzi? Liczba punktów kratowych na odcinku od $(x_1, y_1)$ do $(x_2, y_2)$ (bez jednego końca) wynosi $\mathrm{NWD}(|x_2 - x_1|, |y_2 - y_1|)$ . Dla odcinka z $(0,0)$ do $(4,6)$ to $\mathrm{NWD}(4,6) = 2$ .

Czy twierdzenie działa dla figur z dziurami? Tak, po poprawce: do wzoru dodajemy liczbę dziur. Bez tej poprawki wynik będzie zaniżony.

Czy istnieje odpowiednik w trzech wymiarach? Nie. Czworościany Reeve’a pokazują, że objętości nie da się odczytać z liczby punktów kratowych.

Do czego to się przydaje na maturze? Bezpośrednio - do niczego, bo twierdzenia nie ma w podstawie programowej. Pośrednio bardzo: uczy patrzeć na figurę jak na zbiór punktów i bywa najszybszą drogą do wyniku w zadaniu z kratką.

Podsumowanie

$P = W + \tfrac{B}{2} - 1$ - pole wielokąta kratowego liczone z samych kropek.
Dowód opiera się na addytywności wzoru przy sklejaniu figur oraz sprawdzeniu go dla prostokąta i trójkąta prostokątnego.
Warunek konieczny: wszystkie wierzchołki w punktach kratowych; dla figur z dziurami wzór wymaga poprawki $+h$ .
Pole wielokąta kratowego jest zawsze wielokrotnością $\tfrac{1}{2}$ - stąd np. niemożność narysowania trójkąta równobocznego na kratce.
W trzech wymiarach analogiczne twierdzenie nie istnieje (czworościany Reeve’a).