XLI OM - I - Zadanie 4

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

Rozwiązanie

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

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

Pozostaje do pokrycia reszta szachownicy. Proste zawierające pionowe boki prostokąta 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 ; jest to możliwe, bo jest liczbą parzystą.

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

W ten sposób pokryliśmy płytkami całą szachownicę bez pól i . 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.