Komentarz

XXIX OM - III - Zadanie 2

Na płaszczyźnie dane są punkty o współrzędnych całkowitych, z których co najmniej jedna jest niepodzielna przez A. Dowieść, że punktów tych nie można tak połączyć w pary, aby odległość punktów każdej pary była równa 1; to znaczy nieskończonej szachownicy z wyciętymi polami o współrzędnych podzielnych przez 4 nie można pokryć kostkami domina.

Rozwiązanie

Rozważmy zbiór $ A $ punktów na płaszczyźnie o współrzędnych całkowitych $ (i, j) $, gdzie $ 0 \leq i, j \leq 4k $. Zauważmy, że jeżeli połączymy punkty w pary zgodnie z warunkami zadania, to suma współrzędnych jednego punktu każdej pary będzie liczbą nieparzystą, a drugiego parzystą.

Zbiór $ A $ ma $ (4k + 1)^2 $ punktów, w tym $ (k + 1)^2 $ punktów ma obie współrzędne podzielne przez $ 4 $ i na mocy warunków zadania punktów takich nie bierzemy pod uwagę. Liczba punktów zbioru $ A $, których suma współrzędnych jest parzysta, jest o $ 1 $ większa od liczby punktów zbioru $ A $, których suma współrzędnych jest nieparzysta. Zatem liczba tych pierwszych punktów jest równa $ 8k^2 + 4k + 1 $, a drugich $ 8k^2 + 4k $.

Na brzegu kwadratu wyznaczonego przez punkty zbioru $ A $ jest $ 8k $ punktów o nieparzystej sumie współrzędnych (po $ 2k $ na każdym boku kwadratu).

Zgodnie z warunkami zadania $ (8k^2 + 4k) - 8k = 8k^2 - 4k $ punktów zbioru $ A $ o nieparzystej sumie współrzędnych, które leżą wewnątrz rozważanego kwadratu, należy połączyć w pary z pewnymi z $ (8k^2 + 4k + 1) - (k + 1)^2 = 7k^2 + 2k $ punktów należących do zbioru $ A $ o parzystej sumie współrzędnych, lecz nie o obu współrzędnych podzielnych przez $ 4 $.

Jeżeli więc można by było połączyć punkty płaszczyzny w pary zgodnie z warunkami zadania, to dla każdej liczby naturalnej $ k $ zachodziłaby nierówność

\[<br /> 8k^2 -4k \leq 7k^2 + 2k,<br /> \]

czyli $ k^2 \leq 6k $. Jednak już dla $ k = 7 $ nierówność ta nie zachodzi.

Wobec tego nie można połączyć danych punktów w pary zgodnie z warunkami zadania.

Uwaga. Jeżeli pola szachownicy są na przemian koloru białego i czarnego i jedno z wyciętych pól jest czarne, to wszystkie wycięte pola są czarne. Ponieważ kostka domina pokrywa jedno pole białe i jedno czarne, więc liczba pól każdego koloru pokrytych kostkami domina jest taka sama. Jeżeli więc rozpatrujemy odpowiednio dużą część skończoną szachownicy nieskończonej, to będzie tam zbyt dużo pól białych, by można było wszystkie pokryć kostkami domina. Na tej myśli jest oparte podane wyżej rozwiązanie.

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

Dodaj komentarz