Книга "Когда ты была рыбкой, головастиком - я..." и другие размышления о всякой всячине - Мартин Гарднер

Рис. 3. Голомбово индуктивное доказательство

Порядки 5 и 7

Далее нас ждет доска 5-го порядка, поскольку 5 — следующее число в последовательности (1), для которого мы пока не вывели доказательства. Если убрать центральную клетку, полученную фигуру можно покрыть очень аккуратно и симметрично (как показано на рис. 4. слева). Я покрыл эту доску четырьмя элементами 2×3. Каждый из них можно в свою очередь двумя различными способами покрыть двумя тримино. Покрытия 2×3 — очень полезный инструмент при решении задач с тримино. Когда недостающая клетка расположена, как показано черным на рис. 4 (средний квадрат), клетку над ней, как нетрудно убедиться, приходится покрывать с помощью тримино, примыкающего слева или справа. В любом случае у нас появятся две свободное клетки (они обозначены как 1 и 2), которые нельзя покрыть тримино. И в самом деле, квадрат 5-го порядка можно покрыть тримино, только если недостающая клетка находится в одной из позиций, обозначенных черным на рис. 4. справа. Вот вам приятное упражнение: посмотрите, удастся ли вам покрыть доску, если вырезанная клетка находится в углу.

Рис. 4. Квадрат 5-го порядка

Доску 7-го порядка анализировать гораздо труднее. Я не сумел придумать одиночную диаграмму, которая доказывала бы, что такую доску можно покрыть тримино, однако Голомб прислал мне свое неопубликованное доказательство, где он использует три диаграммы.

Рис. 5. Квадрат 7-го порядка можно покрыть тримино (доказательство Голомба)

Его доказательство развивается так. На рис. 5 показаны три способа покрытия доски 7-го порядка. Очевидно, что при каждом таком покрытии квадрат 2×2 можно покрыть с помощью тримино, если недостающая клетка находится в любом из его четырех углов. Поворачивая эти три фигуры, можно добиться того, чтобы недостающая клетка приходилась на любое место доски.

Несколько труднее придумать, как покрыть доски с помощью максимального количества элементов 2×3. Вот вам задачка: сможете ли вы покрыть доску 7×7 с помощью шести элементов 2×3 и четырех тримино (рис. 6)? Решение — единственное (если не считать его зеркального отражения). (Это решение приводится на с. 204).

Рис. 6. Задача

Посмотрев на рис. 5, можно отметить, что для каждого приведенного разбиения количество свободных тримино (не входящих в элементы 2×3) оказывается четным. И это не совпадение. Мне удалось вывести следующий тривиальный закончик. Когда порядок доски — четный, количество свободных тримино при покрытии — нечетное, и наоборот: когда порядок доски — нечетный, число свободных тримино должно быть четным.

Доказать эти равенства просто. Если доска имеет четный порядок, то после удаления одной клетки количество тримино при любом способе покрытия составит величину, равную (n2–1)/3, т. е. нечетное число. В каждом элементе 2×3 содержится два тримино, а значит, общее количество тримино, входящих в состав элементов 2×3, неминуемо окажется четным. Если вычесть это четное число из общего числа тримино (а оно — нечетное), мы получим нечетное число тримино, не входящих ни в один элемент 2×3.

Пусть доска имеет нечетный порядок. После удаления одной клетки на доске останется четное число клеток. «Вычтем» из него четное число тримино, входящих в элементы 2×3, и получим четное число тримино, в такие элементы не входящих.

Выше 7-го порядка

Индуктивное доказательство Голомба применимо к бесконечному числу рядов, чьи элементы удваиваются. В частности, после того как мы успешно покрыли доску 7×7, можно понять, как покрываются доски размером n×n, где n = 2k·7. К примеру, возьмем доску 14-го порядка. Разобьем ее на области, расположив зачерненную доску 7-го порядка в левом верхнем углу и положив одно тримино у нижнего правого угла этой зачерненной доски, подобно тому, как мы проделывали раньше (см. рис. 3, справа). Поскольку доску 7-го порядка можно покрыть, из этого с очевидностью вытекает доказательство для доски 14-го порядка, а далее, по индукции, доказательства для порядков 28, 56, 112…

Подобное доказательство нельзя вывести для доски 10-го порядка, расположив в ее углу квадрат 5-го порядка, поскольку его не всегда удается покрыть (см. рис. 4). Однако с этой сложностью легко справиться, применив несколько иной подход. Разместим в левом верхнем углу квадрат 8-го порядка — его, как нам известно, можно покрыть. Остается угловая область, имеющая ширину 2 и занимающая низ и правую часть большого квадрата (см. рис. 7). Путем поворотов и отражений любую недостающую клетку в квадрате 8-го порядка удается расположить в любом месте этой доски. Таким же образом получаем доказательство для порядков 20, 40, 80 и т. д. Сходное доказательство существует для доски 11-го порядка: квадрат 7-го порядка располагаем в ее углу, и тогда угловая область, занимающая нижнюю и боковую часть большого квадрата, будет иметь ширину 4. Индукция позволяет вывести доказательства и для порядков 22, 44, 88… Понятно, что эта методика дает нам бесконечное количество покрываемых досок, длина сторон которых удваивается (это своего рода удваивающийся ряд). Просто располагайте в левом верхнем углу любой доски заведомо покрываемый квадрат со стороной, которая меньше стороны исходной доски либо равна ей. Если оставшуюся снизу и сбоку область большой доски вам удастся покрыть — значит, и большая доска покрываема.

Рис. 7. Доску 19-го порядка можно покрыть.

Обычно труднее всего покрыть доски, у которых длина сторон — простое число. Проблему доски 17-го порядка удается решить, поместив в ее угол квадрат со стороной 13 и оставив внизу и сбоку область шириной 4. Проблему доски 19-го порядка — поместив в ее угол квадрат 14-го порядка (доказательство его покрываемости основано, в свою очередь, на таком же свойстве квадрата 7-го порядка) и получив угловую область шириной 5 (см. рис. 8).