LX OM - III - Zadanie 2

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.

  • Wersja do wydrukuWersja do wydruku
  • Podziel się / Zapisz

Komentarze

Dodaj nową odpowiedź