LX OM - III - Zadanie 2

Zawody matematyczne:

LX OM, 2008-2009

Etap:

III

Niech $S$ będzie zbiorem wszystkich punktów płaszczyzny o obu współrzędnych całkowitych. Znaleźć
najmniejszą liczbę całkowitą dodatnią $k$ , dla której istnieje 60–elementowy podzbiór zbioru $S$
o następującej własności: Dla dowolnych dwóch różnych elementów $A$ i $B$ tego podzbioru istnieje taki punkt
$C \in S$ , że pole trójkąta $ABC$ jest równe $k$ .

Rozwiązanie

Niech $K$ będzie podzbiorem zbioru $S$ mającym dla zadanej liczby $k$ własność podaną w treści zadania.
Ustalmy dowolne dwa różne punkty $(a, b), (c, d) \in K$ . Wtedy dla pewnych liczb całkowitych
$x, y$ pole trójkąta o wierzchołkach $(a, b)$ , $(c, d)$ , $(x, y)$ wynosi $k$ , czyli zachodzi równość
$\frac{1}{2}|(a - c)(y - d) - (b - d)(x - c)| = k$ . Otrzymujemy stąd warunek, że równanie

$<br /> (1) \qquad |(a - c)(y - d) - (b - d)(x - c)| =2k<br />$

ma dla dowolnych ustalonych i różnych $(a, b), (c, d) \in K$ rozwiązanie w liczbach całkowitych x, y.

Udowodnimy, że jeśli liczba $m$ nie dzieli $2k$ , to zbiór $K$ ma nie więcej niż $m^2$ elementów.
Rozważmy w tym celu pary $(a \mod m, b \mod m)$ reszt z dzielenia współrzędnych punktów zbioru $K$ przez $m$ .
Jest ich $m^2$ , więc jeśli $|K| >m^2$ , to na mocy zasady szufladkowej znajdziemy dwa różne punkty
$(a, b) \in K$ i $(c, d) \in K$ , takie że $a \equiv c \mod m$ i $b \equiv d \mod m$ . Dla takich punktów
równanie (1) nie ma rozwiązania, gdyż lewa jego strona dla dowolnych $x$ i $y$ dzieli się przez $m$ ,
a prawa nie. Zatem $|K|\leqslant m^2$ dla dowolnego $m$ nie będącego dzielnikiem $2k$ .

Z powyższych rozważań wynika, że jeżeli $|K| = 60$ , to $2k$ musi być podzielne przez wszystkie liczby
$m \leqslant 7$ , bowiem $60 > 7^2$ . Łatwo sprawdzić, że najmniejszą liczbą naturalną podzielną przez
2, 3, 4, 5, 6, 7 jest $22 \cdot 3 \cdot 5 \cdot 7 = 420$ , zatem $210|k$ .

Pokażemy, że dla każdego $k$ takiego, że $210|k$ , można skonstruować 60–elementowy zbiór $K$ mający
własność podaną w treści zadania. Niech $K'$ będzie zbiorem wszystkich tych elementów zbioru $S$ ,
których obie współrzędne znajdują się w zbiorze $\{0, 1,..., 7\}$ . Ustalmy dwa dowolne, różne punkty
$A =(a, b)$ i $B=(c, d)$ ze zbioru $K$ . Wtedy $a - c, b - d \in \{-7, -6,..., 6, 7\}$ , zatem jeśli
$a \neq c$ , to $a-c|420$ oraz jeśli $b = d$ , to $b-d|420$ . Bez straty ogólności możemy przyjąć, że $b = d$ .
Wówczas $b - d|2k$ , gdyż $420|2k$ . Punkt $C =(c + \frac{2k}{d-b} ,d)$ jest zatem elementem zbioru $S$ ,
zaś pole trójkąta $ABC$ wynosi

$<br /> \frac{1}{2}\left| (a-c)(d-d) - (b-d)\left(c+ \frac{2k}{d-b} -c \right) \right|=k.<br />$

Ponadto $|K'| = 64 > 60$ . Jako zbiór $K$ można wziąć dowolny 60–elementowy podzbiór zbioru $K$ .

Tym samym pokazaliśmy, że 60–elementowy zbiór mający żądaną własność istnieje tylko dla liczb
całkowitych dodatnich $k$ będących wielokrotnościami 210. Najmniejszą taką liczbą jest 210.