XXII OM - I - Zadanie 7

Zawody matematyczne:

XXII OM, 1970-1971

Etap:

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

$ \left< \frac{n}{4} \right>= \left\{ \begin{array}{lll} k,&\textrm{gdy}& n=4k,\\ k+1,&\textrm{gdy}& n=4k+1,\ 4k+2, \ \textrm{lub}\ 4k+3 \end{array}\right. $