Cięcie

[mol_ksiazkowy]

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.

[Samouk1]

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

[Jan Kraszewski]

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

[Slup]

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.