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

$ \sum_{i=1}^{k+1}|P_{i-1}P_i|^2 \leq 2 a^2 $

(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

$ |B_0E_0| = \frac{1}{2} |A_0C_0| \leq \frac{1}{2} |AC| = \frac{1}{2} \sqrt{2a}. $

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

$ (1) \qquad |A_0P_1l^2+|P_1P_2|^2+\ldots+|P_kB_0|^2 \leq 2|B_0E_0|^2 \leq a^2, $

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

Zauważmy teraz, że

$ |P_kB_0|^2+|B_0P_{k+1}|^2 \geq |P_kP_{k+1}|^2 $

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

$ |AP_1| \geq |A_0P_1|, \quad |P_mC| \geq |P_mC_0|| $

(rysunek 17). Wobec tego

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

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.

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:

$ (3) \qquad |AP_1|^2+ \ldots +|P_kC|^2 \leq 2, $

$ (4) \qquad |CP_{k+1}|^2+ \ldots +|P_nAl^2\leq 2. $

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

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

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

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

Zatem numeracja $P_1,\ldots, P_n$ czyni zadość warunkowi zadania.

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