XXXVIII OM - III - Zadanie 1

W kwadracie o boku 1 znajduje się $ n $ punktów ($ n > 2 $). Dowieść, że można je ponumerować $ P_1, P_2, ..., P_n $ tak, by \sum_{i=1}^n |P_{i-1}P_i|^2 \leq 4 (przyjmujemy $ P_0=P_n $).

Rozwiązanie

Dowód oprzemy na następującym lemacie:
Lemat. W trójkącie prostokątnym $ ABC $, w którym $ |AB| = |BC| = a $, $ |\measuredangle ABC| = 90^\circ $, znajduje się $ k $ punktów ($ k \geq 1 $). Można je wówczas ponumerować $ P_1, \ldots , P_k $ tak, że

\[<br />
\sum_{i=1}^{k+1}|P_{i-1}P_i|^2 \leq 2 a^2<br />
\]

(przyjmujemy $ P_0 = A $, $ P_{k+1} = C $).

Dowód. Stosujemy indukcję. Gdy $ k = 1 $, mamy jeden punkt $ P $ i do udowodnienia nierówność $ |AP|^2+|PC|^2 \leq 2a^2 $, która wynika z tego, że $ 2a^2 = |AC|^2 $, a kąt $ APC $ jest nieostry.

Ustalmy liczbę naturalną $ m \geq 2 $ i załóżmy, że teza lematu zachodzi dla dowolnego trójkąta prostokątnego równoramiennego i dowolnego zawartego w nim zbioru Uczącego k punktów, gdzie $ k $ jest dowolną liczbą naturalną mniejszą niż $ m $.

Niech będzie dany trójkąt $ ABC $ ($ |AB| = |BC| = a $, $ |\measuredangle B| = 90^\circ $), a w nim zbiór $ Z $ złożony z $ m $ punktów. Niech $ A_0B_0C_0 $ będzie najmniejszym trójkątem o bokach równoległych do odpowiednich boków trójkąta $ ABC $, zawierającym zbiór $ Z $. (,,Konstrukcja'': każdą z trzech prostych zawierających boki trójkąta $ ABC $ przesuwamy równolegle aż do napotkania pierwszego z punktów zbioru $ Z $; przesunięte proste utworzą trójkąt $ A_0B_0C_0 $, o którym mowa.)

Oznaczmy przez $ E_O $ spodek wysokości opuszczonej z wierzchołka $ B_0 $ na przeciwprostokątną $ A_0C_0 $. Oczywiście

\[<br />
|B_0E_0| = \frac{1}{2} |A_0C_0| \leq \frac{1}{2} |AC| = \frac{1}{2} \sqrt{2a}.<br />
\]

Oznaczmy trójkąty (domknięte) $ A_0E_0B_0 $ i $ B_0E_0C_0 $ odpowiednio przez $ \Delta' $ i $ \Delta'' $, a ich część wspólną, czyli odcinek $ B_0E_0 $, przez $ I $. Każdy z trójkątów $ \Delta' $ i $ \Delta'' $ zawiera punkty zbioru $ Z $; inaczej trójkąt $ A_0B_0C_0 $ nie byłby minimalny. Dzielimy teraz zbiór $ Z $ na dwa niepuste podzbiory $ Z' $ i $ Z'' $ zawarte odpowiednio w $ \Delta' $ i $ \Delta'' $: punkty zbioru $ Z_n \cap \Delta' \setminus I $ zaliczamy do $ Z' $, punkty zbioru $ Z_n \cap \Delta' \setminus I $ zaliczamy do $ Z'' $, a punkty zbioru $ Z \cap l $ rozdzielamy między zbiory $ Z' $ i $ Z'' $ w dowolny sposób, z jedynym zastrzeżeniem, by powstałe zbiory $ Z' $ i $ Z" $ były niepuste; jest to możliwe, gdyż w myśl poprzedniej konkluzji $ Z \cap \Delta' \neq\emptyset $ , $ Z_n \cap \Delta'' \neq \emptyset $, a $ m \geq 2 $.

Niech $ k $ będzie liczbą elementów zbioru $ Z' $, a $ m-k $ liczbą elementów zbioru $ Z'' $ ($ 0 < k < m $). Na mocy przesłanki indukcyjnej zastosowanej do trójkątów $ \Delta' $ i $ \Delta' $ oraz zawartych w nich zbiorów $ Z' $ i $ Z" $ można ponumerować punkty tych zbiorów odpowiednio: $ P_1, \ldots, P_k $ oraz $ P_{k+1}, \ldots, P_m $ tak, by

\[<br />
(1) \qquad |A_0P_1l^2+|P_1P_2|^2+\ldots+|P_kB_0|^2 \leq 2|B_0E_0|^2 \leq a^2,<br />
\]
\[<br />
(2) \qquad |B_0P_{k+1}|^2+|P_{k+1}P_{k+2}^2+ \ldots +|P_mC_0| \leq 2|B_0E_0|^2 < a^2.<br />
\]

Zauważmy teraz, że

\[<br />
|P_kB_0|^2+|B_0P_{k+1}|^2 \geq |P_kP_{k+1}|^2<br />
\]

(bo $ |\measuredangle P_kB_0P_{k+1}| \leq 90^\circ $), a ponadto

\[<br />
|AP_1| \geq |A_0P_1|, \quad |P_mC| \geq |P_mC_0||<br />
\]

(rysunek 17). Wobec tego

\[<br />
\begin{split}<br />
&|AP_1|^2 \ldots +|P_kP_{k+1}|^2+ \ldots +|P_mC|^2 \leq\\<br />
&\qquad \leq \mathrm{(suma lewych stron nierówności (1) i (2))} \leq 2a^2.<br />
\end{split}<br />
\]

Znaczy to, że ponumerowanie $ P_1, \ldots, P_m $ punktów zbioru $ Z $ spełnia postawiony warunek. Indukcyjny dowód lematu jest tym samym zakończony.
om38_2r_img_17.jpg
Aby wydedukować z lematu tezę zadania, dzielimy dany kwadrat $ ABCD $ (o boku długości 1) na dwa trójkąty prostokątne przekątną $ AC $. Dany zbiór $ n $ punktów dzielimy na dwa podzbiory, zawarte odpowiednio w jednym i drugim trójkącie i liczące odpowiednio $ k $ i $ n-k $ punktów ($ 0 \leq k \leq n $); punkty leżące na przekątnej zaliczamy do któregokolwiek z tych zbiorów.

Rozpatrzymy dwa przypadki:

1. $ 0 < k < n $. Z lematu wynika możliwość ponumerowania punktów w każdym z tych zbiorów: $ P_1, \ldots, P_k $ oraz $ P_{k+1}, \ldots, P_k $ tak, żeby były spełnione warunki:

\[<br />
(3) \qquad |AP_1|^2+ \ldots +|P_kC|^2 \leq 2,<br />
\]
\[<br />
(4) \qquad |CP_{k+1}|^2+ \ldots +|P_nAl^2\leq 2.<br />
\]

Podobnie, jak w dowodzie lematu, skorzystamy z nierówności

\[<br />
|P_kC|^2+|CP_{k+1}|^2 \geq |P_kP_{k+1}|^2 \quad  |P_nA|^2 + |AP_1|^2 \geq |P_nP_1|^2,<br />
\]

wynikających z tego, że $ |\measuredangle P_kCP_{k+1}| \leq 90^\circ $, $ |\measuredangle P_nAP_1| \leq 90^\circ $ (rysunek 18). Dostajemy nierówność

\[<br />
\begin{split}<br />
&|P_1P_2|^2 \ldots +|P_kP_{k+1}|^2+ \ldots +|P_nP_1|^2 \leq\\<br />
&\qquad \leq \mathrm{(suma lewych stron nierówności (3) i (4))} \leq 4.<br />
\end{split}<br />
\]

Zatem numeracja $ P_1,\ldots, P_n $ czyni zadość warunkowi zadania.
om38_3r_img_18.jpg
2. $ k = 0 $ lub $ k = n $. Wszystkie dane punkty leżą wówczas w jednym z trójkątów $ ABC $, $ CDA $ i zgodnie z lematem możemy je ponumerować $ P_1, \ldots, P_n $, tak że

\[<br />
|AP_1|^2+|P_1P_2|+ \ldots +|P_{n-1}P_n|^2+|P_nC|^2 \leq 2.<br />
\]

Tym bardziej więc

\[<br />
|P_1P_2|+ \ldots +|P_{n-1}P_n|^2 \leq 2.<br />
\]

co w połączeniu z oczywistą nierównością $ |P_nP_1l^2 \leq 2 $ daje żądany warunek

\[<br />
|P_1P_2|+ \ldots +|P_{n-1}P_n|^2+|P_nP_1|^2 \leq 4.<br />
\]

Komentarze

Dodaj nową odpowiedź