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

_{Рис. 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) оказывается четным. И это не совпадение. Мне удалось вывести следующий тривиальный закончик. Когда порядок доски — четный, количество свободных тримино при покрытии — нечетное, и наоборот: когда порядок доски — нечетный, число свободных тримино должно быть четным.

Доказать эти равенства просто. Если доска имеет четный порядок, то после удаления одной клетки количество тримино при любом способе покрытия составит величину, равную (n²–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).