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.)

Obtížnost: Snadná úloha (řešená úvahou nebo přímo z definic)
Úloha na dokazování, ověřování
En translation
	Zaslat komentář k úloze