Делать или думать?

Сегодня мы продолжим начатый в прошлый раз разговор о методе математической индукции и рассмотрим классическую дилемму - уже делать то, что поняли, или ещё чуть-чуть подумать. Метод математической индукции - это очень мощный и эффективный подход, после освоения которого можно смело говорить, что человек «видел паровоз» (в том смысле, что его уже не так легко чем-то удивить). В обычной школьной практике можно столкнуться со скучными алгебраическими задачками, которые не приносят радости, но по первости запутывают. Поэтому я сторонник того, что можно представить и пощупать - это даёт возможность почувствовать метод, ощутив к нему интерес, а не отвращение.

Итак, у нас есть триминошки (г-образные фигурки из трёх клеток) и поле 128 на 128, из которого вырезали одну клетку. Как быстро убедиться, что это поле можно покрыть триминошками? Полный перебор отпадает, потому что поле очень большое.

Глядя на триминошку, легко заметить, что её можно сложить из четырёх меньших триминошек. Это - первый шаг нашего решения. Кто-то, увидев этот рисунок, сразу всё понял. После этого есть два естественных решения:
1) больше формулировать, но меньше думать - не самое красивое, но работающее решение,
2) меньше писать и рисовать, но чуть больше думать - это изящное решение
(кстати, такая дилемма в математике бывает очень часто).

Изложу оба подхода:

Квадрат 128 на 128 можно разрезать на четыре квадрата 64 на 64 клетки. В одном из них будет вырезанная клетка (это по условию), а из остальных как раз получается здоровенная г-образная фигура. Теперь у нас есть две важные сюжетные линии, так как надо справиться с оставшимся квадратиком 64х64 (с вырезанной клеточкой) и г-образной фигурой.

Как мы уже поняли, фигуру эту можно разрезать на четыре г-образные фигуры в два раза меньше (у них максимальная ширина будет 64). Но и эти фигурки можно разрезать на 4 фигурки в два раза меньше (со шириной 32). Далее аналогично - режем на 4 меньших фигурки с шириной 16, потом - 8, потом - 4, потом - 2, пока не доходим до исходной триминошки.

Всё это можно было сформулировать в терминах математической индукции:
Теорема 1. Г-образную фигуру (квадрат со стороной 2^k, из которого вырезали одну четверть - угловой квадрат со стороной 2^k-1), можно покрыть триминошками.
Доказательство: Применим метод математической индукции.
База индукции - при k=1 утверждение верно, так как исходная г-образная фигура совпадает с триминошкой.
Шаг индукции - Предположим, что утверждение верно при k=n-1. Тогда при k=n нам достаточно просто разрезать фигуру на 4 вдвое меньших - а их мы уже разрезать умеем (согласно предположению). Что и требовалось доказать.

С большой г-образной фигурой мы справились, а что делать с оставшимся от разрезания квадратом 64х64? Полагаю, уже ясно, что с ним можно проделать такое же разрезание, выделив две фигуры: квадрат 32х32 с дыркой и г-образную фигуру (про которую у нас уже есть теорема).

Решение получилось длинное и занудное, потому что мы бросились излагать его, чуть-чуть не додумав.

Пришло время для изящного решения:

Теорема 2. Для квадрата со стороной 2^k, из которого вырезали одну клетку в произвольном месте, существует покрытие г-образными триминошками.
Доказательство: Опять применяем метод математической индукции:
1) База такая же, как и в предыдущей теореме: квадрат со стороной 2, из которого вырезали одну клетку, можно покрыть одной триминошкой, потому что они совпадают по форме.
2) Шаг индукции: Пусть нам известен способ покрыть любой квадрат без одной клетки, у которого сторона 2^k-1. Тогда квадрат со стороной 2^k без одной клетки можно разрезать на 4 квадрата со стороной 2^k-1, каждый из которых тоже будет без одной клетки (с ними мы умеем справляться по предположению). Причём мы сгруппируем три новых дырки так, чтобы в них можно было вставить одну триминошку (как на рисунке).
Что и требовалось доказать.

Ну а раз мы имеем утверждение для любого квадрата со стороной 2^k, то и для квадрата со стороной 128 оно тоже верно. Кстати, это нам показывает, что иногда существовании чего-то частного проще обосновать, доказав существование чего-то общего.

Закончим сегодня ещё одной задачкой на метод математической индукции.

Дана плоскость, разделенная на части n прямыми. Надо определить минимальное количество цветов, которого заведомо хватит, чтобы раскрасить эти части таким образом, что куски, имеющие общее ребро, будут окрашены в разные цвета.

В следующий раз мы закончим с этой темой, а пока я желаю удачи в решении этой задачки и отдельно благодарю Александра за изложение своего решения к предыдущей.

Хороших вам выходных!