XLI OM - I - Zadanie 4

Zawody matematyczne:

XLI OM, 1989-1990

Etap:

Z szachownicy o wymiarach $8 \times 80$ polach pokolorowanych w zwykły sposób usunięto dwa poła różnych kolorów. Udowodnić, że pozostałe $62$ pola można pokryć 31 prostokątami o wymiarach $2\times 1$ .

Rozwiązanie

Oznaczmy przez $R$ najmniejszy prostokąt zawierający oba usunięte pola $A$ i $B$ . Ponieważ pola te są różnych kolorów i leżą w przeciwległych narożnikach prostokąta $R$ , zatem długości boków $R$ są liczbami naturalnymi różnej parzystości. Nie tracąc ogólności możemy przyjąć, że prostokąt $R$ tworzy $k$ rzędów pionowych i $l$ rzędów poziomych, przy czym $k$ jest liczbą parzystą, a $l$ - nieparzystą (rysunek 2).

Pokażemy, żę prostokąt $R$ bez pól $A$ i $B$ można pokryć płytkami o wymiarach $2 \times 1$ . Gdy $l = 1$ , mamy do pokrycia pasek o długości $k - 2$ i szerokości $1$ ; sposób pokrycia jest oczywisty. Gdy $l> 1$ , wówczas każdy ze skrajnych rzędów pionowych (bez pola $A$ , względnie $B$ ) ma wymiary $(l- 1) \times 1$ i wobec nieparzystości $l$ da się pokryć płytkami $2 \times 1$ , ustawionymi pionowo. Pozostała część prostokąta $R$ jest prostokątem o wymiarach $(k-2) \times l$ (ewentualnie zbiorem pustym, gdy $k = 2$ ) i da się pokryć płytkami ułożonymi poziomo.

Pozostaje do pokrycia reszta szachownicy. Proste zawierające pionowe boki prostokąta $R$ odcinają dwa pasy prostokątne, biegnące przez całą wysokość szachownicy; w szczególnych przypadkach jeden z nich (lub oba) może być zbiorem pustym. Każdy z tych pasów pokrywamy pionowymi płytkami $2 \times 1$ ; jest to możliwe, bo $8$ jest liczbą parzystą.

Część szachownicy pomiędzy wspomnianymi prostymi, po usunięciu z niej prostokąta $R$ , rozpada się na dwa prostokąty (górny i dolny), każdy o szerokości $k$ ( znów: jeden z nich - lub oba - może być zbiorem pustym). Ponieważ $k$ jest liczbą parzystą, potrafimy i te obszary pokryć płytkami $2 \times 1$ , ułożonymi poziomo.

W ten sposób pokryliśmy płytkami $2 \times 1$ całą szachownicę bez pól $A$ i $B$ . Nie jest to jedyny możliwy sposób; istnieje wiele innych. Zauważmy jeszcze, że opisana tu metoda jest skuteczna w przypadku dowolnej szachownic o wymiarach parzystych.