Artykuł źródłowy w wersji do druku [application/pdf]: (261 KB)
Udowodnić, że dla dowolnej kwadratowej siatki istnieje takie pokrycie płytkami w kształcie litery złożonymi z trzech kwadratów, które pozostawia jeden z czterech centralnych kwadratów odkryty (przypadki oraz poniżej).
Rozwiązanie
Rysunek dla przypadku sugeruje pewną metodę wypełniania, ale Czytelnik szybko przekona się, że metody tej nie da się powtórzyć dla My zaś rozwiążemy problem, dowodząc, że można znaleźć takie pokrycie, dla którego dowolnie z góry wybrany kwadrat pozostanie odkryty. Z tego oczywiście natychmiast wynika pozytywne rozwiązanie problemu. Rozumowanie przebiega oczywiście indukcyjnie względem i przypadek jest oczywisty.
W kroku indukcyjnym ustalmy dowolne i kwadrat podzielmy na cztery mniejsze kwadraty, jak na rysunku poniżej. Pomarańczowy kwadrat to nasze dowolnie wybrane, ale ustalone pole, którego nie możemy przykryć. W trzech kwadratach z podziału, które nie zawierają wyróżnionego pomarańczowego pola, zaznaczamy te płytki, które są narożnymi polami centralnego bloku Korzystamy teraz z indukcji i wypełniamy wszystkie cztery kwadraty płytkami tak, aby nie nakryć pól pomarańczowego i szarych. Następnie szare pola nakrywamy pojedynczą płytką. Dowód jest zakończony.
Rysunki poniżej prezentują odpowiednie wypełnienie metodą indukcji dla przypadków oraz Każda szara płytka odpowiada tej wykorzystanej w dowodzie indukcyjnym.
Uwaga
Przedstawione rozumowanie jest w swojej naturze zbliżone do tego z Zadania 1: bez problemu radzimy sobie z indukcją w sytuacji ogólnej, natomiast przypadek szczególny (niezakryte pole w centrum kwadratu) nas przerasta. Oczywiście moglibyśmy konstruować odpowiednie wypełnienia, jak to zrobiliśmy w przypadkach oraz ale jak się przekonaliśmy powyżej, konstrukcja w jednym przypadku nie przenosi się na kolejne.