O problemie sadu bez prześwitów

W 1918 roku George Pólya opublikował artykuł Zahlentheoretisches und wahrscheinlichkeits-theoretisches über die Sichtweite im Walde, w którym rozważał następujący problem (w literaturze anglojęzycznej nosi on nazwę Orchard Visibility Problem).

Problem (Orchard Visibility Problem). Sad ma kształt koła o promieniu $+ |s∈ N$ i środku w początku układu współrzędnych. W każdym punkcie kratowym tego sadu, oprócz punktu $|(0,0),$ posadzono drzewo. Zakładamy, że każde drzewo ma pień, którego przekrój jest kołem o promieniu $|r.$ Jakie jest najmniejsze $r,$ dla którego każdy promień wychodzący z punktu $(0, 0)$ napotyka na swojej drodze jakieś drzewo? Innymi słowy, dla jakich $r,$ stojąc w punkcie $(0, 0),$ nie zobaczymy w tym sadzie żadnych prześwitów?

Zadanie Pólya znalazło się we wspaniałym zbiorze zadań George Pólya i Gábora Szegő Problems and Theorems in Analysis (vol. 2, chap. 5, Problem 239, Springer-Verlag, New York, 1976). Istnieje przekład rosyjski tej książki, niestety nie ma przekładu polskiego.

Eksperymenty

W sformułowaniu zadania z cytowanej książki Pólya i Szegő znajduje się oszacowanie dla poszukiwanego najmniejszego $r,$ my jednak rozpoczniemy od eksperymentalnej analizy zagadnienia. Eksperymenty przeprowadzono za pomocą programu GeoGebra, korzystając z dwóch suwaków (dla $|s$ oraz dla $|r$ ). Zamieszczone poniżej zrzuty ekranów dotyczą przypadków, gdy $|s = 4$ oraz $|s = 6.$

W obu przypadkach minimalny promień $r,$ dla którego jakaś półprosta wychodząca z punktu $(0, 0)$ napotka drzewo, jest w przybliżeniu równy $1 |s .$ Kolejne spostrzeżenie wynika z symetrii. Otóż drzewa w kole położone są symetrycznie względem obu osi układu, więc wystarczy rozpatrzyć I ćwiartkę koła (sadu) i ograniczyć się do drzew o środkach w punktach $|(x,y),$ przy czym $x ⩾ y.$

Minimalny promień drzew dla sadu bez prześwitów - łatwiejsza część

Udowodnimy, że jeśli $-1--- r < s2+1 ,$ to sad ma prześwit. Spójrzmy na fragment sadu przedstawiony na marginesie (rozumowanie jest ogólne, ilustrujemy je dla $s = 6$ ). Odległość punktów $|E = (1,0)$ i $F = (s− 1,1)$ od półprostej $OA,$ gdzie $A = (s,1),$ wynosi $| --1--, s2+1$ stąd drzewa w punkcie $|E$ oraz w punkcie $F$ o promieniu $1 |r < --s2+1$ nie dotykają półprostej $|OA.$ Zatem jeśli sad nie ma prześwitów, to $r⩾ --1--. s2+1$ Uzasadnienie, że promień $--1-- | s2+1$ faktycznie jest najmniejszym możliwym, jest już bardziej złożone.

Minimalny promień drzew - trudniejsza część

Zauważmy najpierw, że kluczowe dla rozpatrywanego problemu są drzewa posadzone w punktach $|(a,b),$ gdzie $a$ oraz $|b$ są względnie pierwsze. Tak rzeczywiście jest, gdyż jeśli $|NWD(a, b) = d > 1,$ to drzewo w punkcie $( a, b) d d$ zasłania drzewo w punkcie $(a, b).$ Przypomnijmy, że prześwity sadu obserwujemy z punktu $|(0,0).$ Rozpatrzmy więc wszystkie punkty w sadzie o współrzędnych względnie pierwszych. Dla $|s = 5$ w pierwszej ćwiartce takich punktów jest łącznie trzynaście. Wszystkie te punkty można znaleźć, stosując algorytm Sterna-Brocota, który polega na prostej operacji sumowania punktów. Opiszemy go właśnie dla $s = 5.$

Rozpoczynamy od pary punktów $(0,1)$ i $(1,0)$ (etap I), a następnie na każdym kolejnym etapie pomiędzy dwa sąsiednie punkty z poprzedniego etapu wstawiamy punkt, którego współrzędne to sumy odpowiednich współrzędnych punktów sąsiednich. Popatrzmy na punkty otrzymane w kolejnych etapach tej procedury:

Zauważmy, że cztery punkty z etapu V nie należą do rozpatrywanego sadu - zaznaczono je kolorem na rysunku poniżej . 13 kluczowych dla naszego problemu punktów ma kolor czarny, pozostałe punkty są nieistotne. Otrzymane za pomocą algorytmu Sterna-Brocota na każdym etapie punkty mają ważne, łatwe do udowodnienia własności:

$|♠$: jeśli punkty $|(a,b)$ oraz $(c,d)$ są sąsiednie, to $bc −ad = 1$ ;
$♣$: punkty $(a,b)$ w odniesieniu do ilorazu $a/b$ są uporządkowane rosnąco, co oznacza także, że kąt, jaki tworzy półprosta łącząca $(0,0)$ i $|(a,b)$ z dodatnią półosią $OX,$ maleje.

Rozpatrzmy parę sąsiednich punktów na jakimś etapie procedury Sterna-Brocota, które leżą w kole o promieniu $s$ (nazwijmy te punkty $X,Y$ ), oraz takich, że punkt $|X + Y$ leży poza tym kołem. Na rysunku takimi punktami są na przykład $E = (2,1),I = (3,1),$ punkt $|E + I = (5,2) = Q$ leży na zewnątrz koła. Czwórka punktów $(O,X,Y ,X +Y )$ tworzy równoległobok bez punktów kratowych wewnątrz. Kluczowe dla dalszych rozumowań jest poniższe twierdzenie.

Twierdzenie. Niech $|(O,X,Y ,X + Y )$ będzie czwórką punktów opisaną powyżej, przy czym $| X + Y ,$ czyli odległość punktu $X +Y$ od punktu $|O,$ jest najmniejszą możliwą. Wówczas sad z drzewami o promieniu $|r$ nie ma prześwitów wtedy i tylko wtedy, gdy $--1- r⩾ SX+Y .$

Dowód. Spójrzmy na rysunek na marginesie. Jeżeli pomiędzy drzewami znajdującymi się w punktach $X$ i $Y$ jest prześwit, to pomiędzy nimi będzie widoczne drzewo w punkcie $|X + Y .$ Ponieważ $|X + Y$ znajduje się poza sadem, oznacza to, że nie możemy dopuścić do tego prześwitu. Zauważmy najpierw, że odległość punktów $X,Y$ od prostej łączącej $|O$ z $X +Y$ wynosi $|SX1+Y-.$ Wynika to z tego, że pole równoległoboku $|O,X,Y ,X + Y$ jest równe 1 (własność $♠).$ Ponadto z własności $|♣$ wynika, że w wycinku $SOT$ rozpatrywanego koła nie ma punktów kratowych. Zatem jeśli $r < SX1+Y-,$ to półprosta łącząca $|O$ z $X +Y$ nie napotyka w sadzie żadnego drzewa.

Załóżmy teraz, że $1 r ⩾ SX+Y-.$ Pokażemy, że w sadzie w pasie między zaznaczonymi kolorem prostymi nie ma żadnych punktów kratowych o współrzędnych względnie pierwszych. Niech $X = (a,b)$ oraz $|X + Y = (c,d).$ Obie proste w kolorze są równoległe do prostej łączącej $|O$ z $X +Y ,$ zatem równania kolorowych prostych są postaci:

d- bc−-ad- d- ad-−bc- ygó rna = c ⋅x + c , ydolna = c ⋅x + c .

Stąd jeśli punkt kratowy $|(x,y)$ leży w rozpatrywanym zbiorze, to otrzymujemy:

d⋅x+ ad-−-bc < y < d-⋅x+ bc-−-ad , ad −bc < cy− dx < bc−ad. c c c c

Zatem $cy − dx = 0,$ czyli punkt $(x, y)$ o współrzędnych względnie pierwszych leży na prostej łączącej $|O$ z $X +Y ,$ ale jedynym takim punktem z "listy" Brocota-Sterna jest punkt $X + Y.$

Z nierówności $r ⩾ SX1+Y-$ wynika, że prosta łącząca $O$ z $X + Y$ nie może ominąć drzewa w punkcie $X$ ani $Y .$ Jeśli weźmiemy inną czwórkę punktów $O, P,Q,P + Q,$ przy czym punkty $|P,Q$ leżą w sadzie i każdy z nich ma współrzędne względnie pierwsze oraz punkt $P + Q$ leży na zewnątrz sadu, to $| P + Q ⩾ X + Y$ oraz $SP1+QS ⩽ SX+1Y-.$ Jeśli weźmiemy promień drzewa równy $|-1--, SX+Y$ to prosta łącząca $O$ z $P + Q$ nie ominie punktu $|P$ ani $Q.$

Możemy teraz postawić kropkę nad i - znaleźć minimalny promień drzew dla sadu bez prześwitów. Z twierdzenia wynika, że dla dowolnej liczby całkowitej $| s$ ten minimalny promień oblicza się ze wzoru

√ --2---2 √--2---2 rmin= 1/ min{ a + b a,b ∈Z, a + b > s}.

Oczywiście $|s2 + 12 = s2 +1 > s2,$ więc $rmin = -s12+1 .$