Докажите, что при любом n квадрат размера 2^n на 2^n без одной угловой клетки можно разбить на уголки из трёх клеток

Question

Алгебра: Докажите, что при любом n квадрат размера 2^n на 2^n без одной угловой клетки можно разбить на уголки из трёх клеток

bossobychnyy · Answer

База индукции: Квадрата два на два, у которого отсутствует одна угловая клетка, естественным образом разбивается на уголки из трёх клеток (Рис. 3).

Индукционное предположение: Квадрат 2^k на 2^k с отсутствующей угловой клеткой можно разбить на уголки из трёх клеток.

Индукционный шаг: Пусть есть квадрат $2^{k+1}$ на $2^{k+1}$ , разобъем его на четыре части так, как указано на Рис. 1. Получим четыре квадрата 2^k на 2^k и четыре незаполненных клетки, три из которых можно заполнить уголком (на Рис. 2 синий). Квадраты же 2^k на 2^k без угловных клеток мы можем заполнить согласно индукционному предположению.