Matematyka.pl

Na szachownicę \(\displaystyle{ 6 \times 6}\) nałożono osiemnaście rozłącznych kostek domino ( \(\displaystyle{ 2 \times 1}\)). Wykazać, że szachownicę tę można podzielić na dwie części linią poziomą lub pionową nieprzecinającą wnętrza żadnej z tych kostek.

Czy są jakieś zasady ustawiania tych kostek domino? Muszą się łączyć liczbami czy jakoś inaczej? Bo jeśli nie, to rozwiązanie jest banalne.

Ale wiesz, że to jest twierdzenie ogólne? Masz udowodnić, że dla dowolnego rozłożenia kostek istnieje taka linia. Jeżeli to jest banalne, to pokaż uzasadnienie.

JK

Oglądając swój rachunek za prąd zastanawiałem się, jak to zadanie rozwiązałaby pani Hennig-Kloska i wtedy wymyśliłem takie rozwiązanie.

Niech \(\displaystyle{ L}\) będzie zbiorem \(\displaystyle{ 10}\) linii wewnętrznych na szachownicy \(\displaystyle{ 6\times 6}\). Zaś niech \(\displaystyle{ K}\) będzie zbiorem \(\displaystyle{ 18}\) kostek domina \(\displaystyle{ 2\times 1}\) jakoś ułożonych na szachownicy. Dla \(\displaystyle{ l \in L}\) oraz \(\displaystyle{ k \in K}\) definiujemy
$$l\&k\, \Leftrightarrow \mbox{ linia }l\mbox{ dzieli kostkę }k\mbox{ na dwie części o rozmiarach }1\times 1$$
Zauważmy, że zachodzą dwa fakty.
1. Dla każdej kostki \(\displaystyle{ k \in K}\) istnieje dokładnie jedna linia \(\displaystyle{ l\in L}\) taka, że \(\displaystyle{ l\&k}\).
2. Dla każdej linii \(\displaystyle{ l \in L}\) zbiór
$$K_l = \big\{k\in K\,\big|\,l\&k\big\}$$
ma parzystą liczbę elementów.

Z pierwszego faktu wynika, że
$$18 = |K| = \sum_{l \in L}|K_l|$$
Z drugiego zaś otrzymujemy, że składniki sumy po prawej stronie równości są wszystkie parzyste. Tych składników jest \(\displaystyle{ 10}\). Stąd wynika, że dla pewnego \(\displaystyle{ l\in L}\) zachodzi \(\displaystyle{ |K_l| = 0}\) czyli \(\displaystyle{ K_l = \emptyset}\). Linia \(\displaystyle{ l}\) jest poszukiwaną linią, która nie przecina żadnej kostki.