XXXIII OM - III - Zadanie 4

Na płaszczyźnie dany jest skończony zbiór punktów. Dowieść, że zbiór ten można pokryć otwartymi kwadratami rozłącznymi $ Q_1, Q_2, \ldots, Q_n $, tak, że

\[<br />
1\leq \frac{N_j}{S_j} \leq 4<br />
\]

($ j = 1, 2,\ldots, n $) gdzie $ N_j $ jest liczbą punktów zbioru leżących w kwadracie $ Q_j $, zaś $ S_j $ jest polem kwadratu $ Q_j $.

Rozwiązanie

Obieramy na płaszczyźnie taki układ współrzędnych, aby zbiór punktów, których liczbę oznaczymy literą $ N $, leżał wewnątrz pierwszej ćwiartki i dodatkowo jeszcze żadna ze współrzędnych jego punktów nie dała się przedstawić w postaci $ \frac{k}{2n} $, gdzie $ k $, $ n $ są liczbami naturalnymi. Niech $ d $ będzie taką liczbą naturalną, że kwadrat $ Q $ o wierzchołkach $ (0,0) $, $ (d, 0) $, $ (d, d) $, $ (0, d) $ zawiera w swym wnętrzu wszystkie dane punkty. Niech $ N $ będzie liczbą danych punktów. Rozważmy następujące przypadki

\[<br />
a) 1 \leq \frac{N}{d^2} \leq 4,\<br />
b) \frac{N}{d^2} > 4,\<br />
c) \frac{N}{d^2} < 1.<br />
\]

W przypadku a) kwadrat $ Q $ spełnia wymagane warunki. W przypadku b) przyjmujemy $ d_1 = \frac{\sqrt{N}}{2} $ $ (d_1> d) $ i kwadrat $ Q_1 $ o wierzchołkach $ (0, 0) $,
$ (d_1, 0) $, $ (d_1, d_1) $, $ (0, d_1) $ spełnia warunki zadania.

W przypadku c) dzielimy kwadrat $ Q $ na cztery przystające kwadraty. Ze sposobu wyboru układu współrzędnych wynika, że każdy z danych punktów należy do wnętrza jednego z tych kwadratów. Dla każdego z tych kwadratów jest $ S_i = \frac{d^2}{4} $ oraz $ N_i \leq N $, więc

\[<br />
\frac{N_i}{S_i} \leq \frac{N}{\frac{d^2}{4}} < 4.<br />
\]

Te kwadraty, dla których $ 0 < \frac{N_i}{S_i} < 1 $ dzielimy ponownie na cztery przystające kwadraty, przy czym żaden z danych punktów nie leży na brzegu nowego kwadratu. Postępowanie to kontynuujemy. Po $ m $-tym podziale jest albo $ N_i = 0 $ albo $ \frac{N_i}{S_i} \geq \frac{1}{S_i} $. Jeżeli $ \frac{N_i}{S_i} \geq \frac{1}{S_i} $, to $ \frac{N_i}{S_i} \geq \frac{2^{2m}}{d^2} $, gdyż $ S_i = \left( \frac{d}{2^m} \right)^2 $.

Zatem po nie więcej niż $ [\log_2d] + 1 $ podziałach dla każdego kwadratu będzie spełniona nierówność

\[<br />
1 \leq \frac{N_i}{S_i} \leq 4.<br />
\]

Komentarze

Dodaj nową odpowiedź