\documentclass{article}

\usepackage{amssymb,amsmath,amsthm}
\usepackage[polish]{babel}
\usepackage{polski}
\usepackage[latin2]{inputenc}

\begin{document}

{\bf{Czarownica w nieskończonym lesie}}

Dawno dawno temu, kiedy Ziemia była jeszcze płaszczyzną, rosnął
nieskończony las: w każdym punkcie kratowym Ziemi (czyli punkcie
o obu współrzędnych całkowitych) rosło drzewo.

Czarownica Mirosława chciała zbudować sobie dom na drzewie. Czarownica ma jednak bardzo dużo wymagań co do nowego domu:
\begin{itemize}
\item ma być wielokątem wypukłym, by nie dało się w nim zgubić;
\item ma być zbudowany na jednym drzewie, żadne inne drzewo nie może być w środku budynku, bo to głupio wygląda;
\item dodatkowo, by się dom się nie przewrócił, powinien on być środkowosymetryczny
względem pnia drzewa, na którym się opiera;
\item jego powierzchnia powinna być jak największa, w końcu Czarownice lubią żyć wygodnie.
\end{itemize}

Czy Czarownicy uda się zbudować dom marzeń? Sformułujmy zadanie w języku matematyki: szukamy
jak największego wielokąta wypukłego środkowosymetrycznego względem punktu $(0, 0)$, niezawierającego
innego punktu kratowego.

Weźmy taki wielokąt $F$. Niech $G = \frac{1}{2} F$, czyli $F$ zmniejszony dwukrotnie przez jednokładność względem punktu
$(0, 0)$.
Niech $x_0, y_0 \in {\mathbb Z}$ i $G' = G + (x_0, y_0)$, czyli $G$ przesunięty o wektor $(x_0, y_0)$; innymi słowy przesuwamy
wielokąt $G$ tak, by jego środek był w punkcie $(x_0, y_0)$.
Załóżmy, że $(x, y) \in G \cap G'$. Wówczas $A = (2x, 2y) \in F$ i $B = (2(x-x_0), 2(y-y_0)) \in F$.
Wielokąt $F$ był środkowosymetryczny, czyli $A' = (-2x, -2y) \in F$. Z warunku wypukłości $F$ wynika, że
środek odcinka $A'B$ należy do $F$. Środek ten ma współrzędne:

$$\Big(\frac{2(x-x_0)-2x}{2}, \frac{2(y-y_0)-2y}{2}\Big) = (-x_0, -y_0)$$

Jest to punkt kratowy! Czyli, skoro $F$ było poprawnym domkiem Czarownicy, to $x_0=y_0=0$. Udowodniliśmy, że
równoległe, przesunięte o wektor całkowity, kopie wielokąta $G$ są rozłączne.
Intuicja już nam podpowiada, że wobec tego domek Czarownicy nie może być za duży. Spróbujmy to pokazać.

Domek jest ograniczony --- bo jest wielokątem; 
załóżmy że zawiera się w kwadracie $[-m, m] \times [-m, m]$. Weźmy bardzo bardzo duże $M$,
dużo większe od $m$. Dla każdego punktu kratowego $(x_0, y_0)$ spełniającego $-M \leq x_0, y_0 \leq M$, tworzymy
kopię wielokąta $G$ o środku w tym punkcie kratowym. Kopie te są rozłączne --- to udowodniliśmy ---
i zawierają się w kwadracie $[-M-m, M+m]^2$,
o polu $4(M+m)^2$. Kopii stworzyliśmy $(2M+1)^2 > 4M^2$. Kopie mają takie same pole; czyli kopia nie może mieć większego
pola niż $$\frac{4(M+m)^2}{4M^2} = \Big(1+\frac{m}{M}\Big)^2,$$
co, dla dużego $M$ jest dowolnie bliskie jedności. Czyli $G$
nie może mieć większego pola niż $1$. $G$ było pomniejszonym dwukrotnie wielokątem $F$, więc $F$ ma maksymalnie pole $4$.
Biedna Czarownica.

Zostawiając Czarownicę Mirosławę z jej problemem, spróbujmy uogólnić nasz wynik. Po pierwsze zauważmy, że nigdzie nie
korzystaliśmy z tego że $F$ jest wielokątem, była dla nas istotna wypukłość, środkowosymetryczność i ograniczoność.
Po drugie, spróbujmy przeprowadzić nasz dowód w $n$ wymiarach. Niewiele się zmieni: będziemy mieli $(2M+1)^n$ kopii
zbioru $G$ w kostce o objętości $2^n(M+m)^n$; więc wciąż objętość $G$ nie może przekraczać jedności, czyli objętość domku
Czarownicy --- zbioru $F$ --- wynosi maksymalnie $2^n$.

\end{document}
