XLI OM - I - Zadanie 4

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.

om41_1r_img_2.jpg
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.

Komentarze

Dodaj nową odpowiedź