XXXIII OM - III - Zadanie 4

Zawody matematyczne:

XXXIII OM, 1981-1982

Etap:

III

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

$ 1\leq \frac{N_j}{S_j} \leq 4 $

( $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

$ a) 1 \leq \frac{N}{d^2} \leq 4,\ b) \frac{N}{d^2} > 4,\ c) \frac{N}{d^2} < 1. $

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

$ \frac{N_i}{S_i} \leq \frac{N}{\frac{d^2}{4}} < 4. $

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ść

$ 1 \leq \frac{N_i}{S_i} \leq 4. $