Kontakt: gornicki59@gmail.com
Geometria to nie tylko trójkąty, koła czy parabole. Oto jej inne oblicze. Na początku XX wieku Giuseppe Vitali, badając funkcje rzeczywiste, wykazał następujące twierdzenie.
Twierdzenie 1 (G. Vitali). Niech \(E\) będzie przedziałem ograniczonym o długości \(\vert E\vert.\) Wtedy każdy skończony zbiór przedziałów \(E_1,\) \(E_2,\ldots ,E_m\) pokrywających przedział \(E\) zawiera nienachodzące na siebie przedziały \(E_{m_1},\) \(E_{m_2}, \ldots ,E_{m_i}\) o łącznej długości \[\vert E_{m_1}\vert +\ldots +\vert E_{m_i}\vert \geqslant \frac{1}{3}\cdot\vert E\vert.\] Dowód. Spośród przedziałów \(E_1,\ldots ,E_m\) wybieramy przedział najdłuższy i oznaczamy go jako \(E_{m_1}.\) Następnie usuwamy ze zbioru przedział \(E_{m_1}\) i wszystkie przedziały pokrycia, które na niego nachodzą. Usunięte przedziały mogą pokryć przedział nie dłuższy niż \(3\cdot\vert E_{m_1}\vert.\) Z pozostałych przedziałów pokrycia wybieramy przedział najdłuższy i oznaczamy go jako \(E_{m_2}.\) Usuwamy przedział \(E_{m_2}\) i wszystkie przedziały, które na niego nachodzą. Usunięte przedziały mogą pokryć przedział nie dłuższy niż \(3\cdot\vert E_{m_2}\vert.\) Proces ten prowadzimy do wyczerpania wszystkich możliwości. Tak wybrane przedziały \(E_{m_1},\ldots ,E_{m_i}\) nie nachodzą na siebie i \[3\cdot\vert E_{m_1}\vert +\ldots +3\cdot\vert E_{m_i}\vert \geqslant \vert E\vert.\] Istotnie, gdyby \(3\cdot\vert E_{m_1}\vert +\ldots +3\cdot\vert E_{m_i}\vert < \vert E\vert,\) to w zbiorze \(E\) istniałyby punkty pokryte przez pewien przedział, który nie został rozpatrzony. Sprzeczność, bo postępowanie było prowadzone do wyczerpania wszystkich możliwości. Dowód jest zakończony. \(\square\)
Zbiór \(E\subset \mathbb{R},\) różny od punktu, nazywamy przedziałem, gdy każda liczba leżąca między liczbami należącymi do \(E\) też należy do \(E.\)
Przedziały \(E_j,\) \(j=1,2,\ldots ,m\) pokrywają przedział \(E,\) gdy \(E\subset\bigcup\limits_{j=1}^mE_j.\)
Przedziały \(E_i,\) \(E_j\) nie nachodzą na siebie, gdy nie mają wspólnych punktów wewnętrznych (choć mogą mieć wspólne punkty brzegowe).
Prawdziwy jest odpowiednik twierdzenia 1 dla płaszczyzny.
Twierdzenie 2. Niech \(S\) będzie figurą ograniczoną o polu \(\vert S\vert.\) Z każdego skończonego zbioru kwadratów \(K_1,\) \(K_2,\ldots ,K_n,\) o równoległych bokach, pokrywających figurę \(S\) można wybrać nienachodzące na siebie kwadraty \(K_{n_1}, K_{n_2},\ldots ,K_{n_r}\) o łącznym polu \[\vert K_{n_1}\vert + \ldots +\vert K_{n_r}\vert \geqslant \frac{1}{9}\cdot \vert S\vert.\] Dowód. Spośród kwadratów \(K_1, K_2,\ldots ,K_n\) wybieramy kwadrat o największym polu (równoważnie: najdłuższym boku) i oznaczamy go jako \(K_{n_1}.\) Usuwamy ten kwadrat i wszystkie kwadraty pokrycia, które nachodzą na kwadrat \(K_{n_1}.\) Usunięte kwadraty mogą pokryć kwadrat o polu nie większym niż \(9\cdot\vert K_{n_1}\vert.\) Z pozostałymi kwadratami pokrycia powtarzamy tę procedurę do wyczerpania wszystkich możliwości. Tak wybrane kwadraty \(K_{n_1}, K_{n_2},\ldots ,K_{n_r}\) nie nachodzą na siebie, ponadto \[9\cdot\vert K_{n_1}\vert +\ldots +9\cdot\vert K_{n_r}\vert \geqslant \vert S\vert,\] a stąd wynika teza. \(\Box\)
Tibor Radó (1895–1965) w liście z 20 września 1927 roku do Wacława Sierpińskiego (ówczesnego redaktora czasopisma Fundamenta Mathematicae) zauważył, że współczynnik \(\frac{1}{3}\) w twierdzeniu 1 można zastąpić współczynnikiem \(\frac{1}{2}\) (łatwo pokazać, że jest to wartość optymalna, zostawiamy to więc Czytelnikowi jako ćwiczenie).
Twierdzenie 3 (T. Radó, 1928). Niech \(E\) będzie przedziałem ograniczonym o długości \(\vert E\vert.\) Wtedy każdy skończony zbiór przedziałów \(E_1,\) \(E_2,\ldots ,E_m\) pokrywających przedział \(E\) zawiera nienachodzące na siebie przedziały \(E_{m_1},\) \(E_{m_2}, \ldots ,E_{m_k}\) o łącznej długości \[\vert E_{m_1}\vert +\ldots +\vert E_{m_k}\vert \geqslant \frac{1}{2}\cdot\vert E\vert.\] Dowód. Przedziały pokrywające \(E\) ustawiamy w pewnej dowolnej, ale ustalonej kolejności. Przeglądamy je po kolei i odrzucamy każdy przedział zawarty w sumie nieodrzuconych na tym etapie przedziałów. W ten sposób dostajemy nowe pokrycie. W każdym z nieodrzuconych przedziałów \(E_i\) wybieramy punkt wewnętrzny \(x_i\) tak, by był on punktem zewnętrznym dla wszystkich pozostałych przedziałów z nowego pokrycia. Punkty te są różne między sobą i możemy przyjąć, że zostały tak ponumerowane, aby \({x_1<x_2<\ldots <x_n}.\) Dla \(i \geq 1\) i przedziałów \(E_i,\) \(E_{i+h},\) gdzie \(h\geqslant 2,\) mamy \(x_i<x_{i+1}<x_{i+h}.\) Ponieważ punkt \(x_{i+1}\) jest punktem zewnętrznym dla przedziałów \(E_i\) i \(E_{i+h},\) więc przedziały te nie nachodzą na siebie. Oznacza to, że przedziały \(E_i\) o indeksach parzystych tworzą zbiór przedziałów nienachodzących na siebie o łącznej długości \(L'.\) Podobnie przedziały o indeksach nieparzystych tworzą zbiór przedziałów nienachodzących na siebie o łącznej długości \(L”.\) Ponieważ \({E\subset E_1\cup\ldots \cup E_n},\) więc \(L'+L”\geqslant \vert E\vert.\) Oznacza to, że przynajmniej jedna z liczb \(L', L”\) jest nie mniejsza niż \(\frac{1}{2} \cdot \vert E \vert.\) \(\square\)
Jednocześnie T. Radó wyraził przypuszczenie, że w twierdzeniu 2 współczynnik \(\frac{1}{9}\) można zastąpić współczynnikiem \(\frac{1}{4},\) ale nie potrafił tego wykazać. (Jak poprzednio, jest jasne, że nie ma nadziei na wartość większą od \(\frac{1}{4}\)). List T. Radó opublikowany w Fundamenta Mathematicae [tom 11 (1928), 228–229] zapoczątkował problem nawiązujący do twierdzenia 2.
Problem (T. Radó, 1928). Jaka jest największa liczba \(\frac{1}{9}\leqslant c\leqslant \frac{1}{4}\) taka, że z każdego skończonego zbioru kwadratów \(K_1,\) \(K_2,\ldots ,K_n\) o równoległych bokach pokrywających figurę ograniczoną \(S\) można wybrać nienachodzące na siebie kwadraty \(K_{n_1}, K_{n_2},\ldots ,K_{n_j}\) o łącznym polu \[\vert K_{n_1}\vert + \ldots +\vert K_{n_j}\vert \geqslant c\cdot \vert S\vert\,?\] Odpowiedź na to pytanie nie jest znana, choć znamy już lepsze oszacowanie współczynnika \(c\): \(0{,}1179\approx \frac{1}{8,4797}<c\leqslant \frac{1}{4}-\frac{1}{384}\approx 0{,}2473\) (zob. [\(*\)]). Problem T. Radó doczekał się wielu wariantów (np. gdy pokrycia utworzone są z kół) oraz \(n\)-wymiarowych odpowiedników. Również w tych przypadkach rozwiązania nie są znane.
S. Bereg, A. Dumitrescu, M. Jiang, On covering problems of Radó, Algorithmica 57(3) 2010, 538–561.
Pokażemy teraz, że przypuszczenie Tibora Radó jest słuszne w przypadku, gdy figurę \(S\) pokrywa skończona liczba przystających kwadratów (o równoległych bokach). Niezwykle pomysłowe uzasadnienie, wykorzystujące znane twierdzenie H. Blichfeldta, podał w 1940 roku A. S. Sokolin.
Na papierze w kratkę kratka stanowi sieć. Jej oczka to kwadraty jednostkowe, a punkty przecięć kratki to węzły.
Twierdzenie 4 (H. Blichfeldt, 1914). Niech \(S\subset \mathbb{R}^2\) będzie figurą ograniczoną o polu \(\vert S\vert > n-1.\) Wtedy figurę \(S\) można przesunąć równolegle tak, aby zawierała \(n\) węzłów sieci.
Dowód (G. Birkhoff). Zamiast przesuwać figurę \(S,\) przesuniemy oczka sieci. Kratka dzieli figurę \(S\) na części \(S_1,S_2,\ldots ,S_n\) leżące w kwadratach jednostkowych \(K_1,K_2,\ldots ,K_n.\) Przesuwamy równolegle kwadraty \(K_i\) \((i>1)\) wraz z częściami \(S_i\) na kwadrat \(K_1.\) Wtedy we wnętrzu kwadratu \(K_1\) istnieje punkt należący jednocześnie do co najmniej \(n\) części \(S_i\) figury \(S.\) Gdyby tak nie było, to \({\vert S\vert\leqslant n-1 <\vert S\vert}.\) Przebijamy w tym punkcie wszystkie kwadraty \(K_i\) \((i=1,2,\ldots ,n),\) a następnie każdy kwadrat przesuwamy równolegle do położenia pierwotnego. Ślady przebić (jest ich co najmniej \(n\)) to węzły nowej sieci kwadratowej (jednostkowej) równoległej do sieci wyjściowej, które należą do figury \(S.\) \(\square\)
Twierdzenie 5 (A.S. Sokolin, 1940). Niech \(S\) będzie figurą ograniczoną o polu \(\vert S\vert.\) Z każdego skończonego zbioru przystających kwadratów \(K_1,\) \(K_2,\ldots ,K_m,\) o równoległych bokach, pokrywających figurę \(S\) można wybrać nienachodzące na siebie kwadraty \(K_{m_1}, K_{m_2},\ldots ,K_{m_n}\) o łącznym polu \[\vert K_{m_1}\vert + \ldots +\vert K_{m_n}\vert \geqslant \frac{1}{4}\cdot \vert S\vert.\] Dowód. Załóżmy, bez zmniejszania ogólności rozumowania, że pole każdego kwadratu z pokrycia jest równe \((\frac{1}{2})^2.\) Niech \(n\) będzie największą liczbą naturalną spełniającą nierówność \(\vert S\vert >n-1.\) Zgodnie z twierdzeniem 4 (Blichfeldta) figurę \(S\) możemy przesunąć równolegle tak, by zawierała \(n\geqslant \vert S\vert\) węzłów sieci jednostkowej. Wówczas dla każdego węzła pozostawiamy jeden kwadrat pokrywający ten węzeł. Tak wybrane kwadraty nie nachodzą na siebie, a ich łączna powierzchnia wynosi \((\frac{1}{2})^2\cdot n\geqslant \frac{1}{4}\cdot \vert S\vert.\) \(\Box\)
Pozostaje nam podać ostateczne rozwiązanie problemu Tibora Radó, ale to wymaga jeszcze trochę pracy\(\ldots\)
