XXII OM - I - Zadanie 7

Na płaszczyźnie danych jest pięć punktów kratowych (tzn. punktów o współrzędnych całkowitych). Udowodnić, że środek jednego z odcinków łączących te punkty jest również punktem kratowym.

Rozwiązanie

Niech dane będą punkty kratowe $ P_i = (x_i, y_i) $, gdzie $ i = 1, 2, 3, 4, 5 $. Wśród liczb $ x_1 $, $ x_2 $, $ x_3 $, $ x_4 $, $ x_5 $, są co najmniej trzy jednakowej parzystości (tzn. trzy parzyste lub trzy nieparzyste), bo jeśli na przykład co najwyżej dwie są parzyste, to pozostałe są nieparzyste. Niech na przykład liczby $ x_1 $, $ x_2 $, $ x_3 $ będą jednakowej parzystości.

Rozumując podobnie jak poprzednio stwierdzamy, że wśród liczb $ y_1 $, $ y_2 $, $ y_3 $ co najmniej dwie jednakowej parzystości. Niech na przykład liczby $ y_1 $ $ y_2 $ będą jednakowej parzystości. Wtedy liczby $ x_1 + x_2 $ i $ y_1 + y_2 $ będą parzyste, a więc środek odcinka $ P_1P_2 $ będzie miał współrzędne całkowite $ \left(\frac{1}{2}(x_1+x_2), \frac{1}{2}(y_1+y_2) \right) $ czyli będzie punktem kratowym.

Uwaga 1. Prawdziwe jest analogiczne twierdzenie w przestrzeni n-wymiarowej: Jeżeli danych jest w przestrzeni $ n $--wymiarowej $ 2^n + 1 $ punktów o współrzędnych całkowitych, to środek jednego z odcinków łączących te punkty ma współrzędne całkowite.

Uwaga 2. Można też uogólnić zadanie w inny sposób. Jeżeli na płaszczyźnie danych jest $ n $ punktów kratowych, to środki co najmniej $ \displaystyle \binom{\left< \frac{n}{4} \right>}{2} $ odcinków łączących te punkty są punktami kratowymi.
Tu $ \left<x\right> $ oznacza najmniejszą liczbę całkowitą nie mniejszą od $ x $.

Dowód uwagi 2. Podzielmy dane punkty na klasy w zależności od parzystości ich współrzędnych. Są cztery klasy $ (n, n) $, $ (n, p) $, $ (p, n) $ i $ (p, p) $, gdzie $ n $ oznacza, że odpowiednia współrzędna jest nieparzysta, a $ p $ -- że parzysta. W jednej z klas będzie więc co najmniej $ \frac{n}{4} $ punktów, a ponieważ liczba punktów w klasie jest całkowita, więc w jednej z klas będzie co najmniej $ \left< \frac{n}{4} \right> $ punktów.

Ponieważ środek odcinka, którego końce są punktami jednej klasy jest punktem kratowym, a dla $ r $ punktów jest $ \binom{r}{2} $ odcinków je łączących, więc liczba odcinków, których środki są punktami kratowymi jest równa co najmniej $ \displaystyle \binom{\left< \frac{n}{4} \right>}{2} $.

Zauważmy jeszcze, że

\[<br /> \left< \frac{n}{4} \right>=<br /> \left\{<br /> \begin{array}{lll}<br /> k,&\textrm{gdy}& n=4k,\\<br /> k+1,&\textrm{gdy}& n=4k+1,\ 4k+2, \ \textrm{lub}\ 4k+3<br /> \end{array}\right.<br /> \]
  • Wersja do wydrukuWersja do wydruku
  • Podziel się / Zapisz

Komentarze

Dodaj nową odpowiedź