Dláždění
Úloha číslo: 3300
Na šachovnici \(2^n \times 2^n\) jedno náhodně vybrané políčko chybí. Ukažte, že zbylou plochu lze vydláždit dlaždicemi, která mají tvar „L“ a přitom zabírají tři políčka.
Řešení
Dokazujeme indukcí podle \(n\).
Tvrzení platí pro šachovnici \(2\times 2\) (dokonce i pro \(1\times 1\)).
Indukční krok od \(n\) k \(n+1\):
Šachovnici \(2^{n+1}\times 2^{n+1}\) si rozdělíme na čtvrtiny. Chybějící políčko bude v jedné z těchto čtvrtin \(2^n\times 2^n\), na ni použijeme indukční předpoklad.
Nyní beze zbytku vydláždíme zbývající tři čtvrtiny původní šachovnice. Ze středu šachovnice vyjmeme jednu dlaždici tvaru „L“ tak, aby tato dlaždice zasáhla do každé ze zbývajících tří čtvrtin jen jedním políčkem. Nyní zbývají tři šachovnice \(2^n\times 2^n\), každá bez rohového políčka, a ty lze podle indukčního předpokladu také vydláždit.
Hledané vydláždění celku je sjednocení dláždění všech čtyř částí spolu se středovou dlaždicí. \bigskip
Alternativní způsob provedení indukčního kroku:
Políčka šachovnice \(2^{n+1}\times 2^{n+1}\) sloučíme do buněk velikosti \(2\times 2\), tyto nové buňky tvoří šachovnici \(2^n\times 2^n\).
Zbytek buňky, v níž jsme v původní šachovnici odebrali políčko, je dlaždice tvaru „L“ a tu použijeme pro vydláždění. Odpovídající buňku odebereme z šachovnice \(2^n\times 2^n\) a na zbylou část šachovnice \(2^n\times 2^n\) použijeme indukční předpoklad.
Získáme vydláždění šachovnice \(2^n\times 2^n\) bez jedné buňky pomocí „velkých“ dlaždic. Každá taková „velká“ dlaždice se sestává ze tří buněk uspořádaných ve tvaru „L“, neboli z 12 původních políček. Každou „velkou“ dlaždici rozdělíme na čtyři „malé“ podle nákresu na obrázku:
Spolu s již dříve zmíněnou dlaždicí z odebrané buňky tak získáme hledané dláždění zbytku šachovnice \(2^{n+1}\times 2^{n+1}\).
(Jako cvičení z programování si zkuste napsat rekurzivní program pro řešení této úlohy ať prvním nebo druhým způsobem.)