Решение. Пазл из уголков (#76)
1 min readFeb 14, 2019
Докажем методом математической индукции, что если из квадрата 2ⁿ x 2ⁿ вырезали одну клетку (n = 1, 2, …), то полученную фигуру можно замостить уголками.
1. При n = 1 утверждение очевидно.
2. Делаем предположение индукции, то есть при всех k < n квадрат 2ᵏ x 2ᵏ с вырезанной клеткой можно замостить уголками.
Рассмотрим квадрат 2ⁿ x 2ⁿ и вырежем из него клетку. Разрежем квадрат на четыре квадрата и положим один уголок так, как показано на рисунке.
В итоге, мы получим четыре квадрата 2ⁿ⁻¹ x 2ⁿ⁻¹ с одной вырезанной клеткой в каждом. По предположению индукции, мы можем их замостить уголками, а вместе с этим и наш первоначальный квадрат. Следовательно, мы провели шаг индукции и завершили наше доказательство.
