Когда ты была рыбкой, головастиком - я...
Шрифт:
А 1953 году Голомб, «отец» полимино (он придумал для них название и первым начал изучать их), вывел индуктивное доказательство, продемонстрировав, что все доски со сторонами, отвечающими прогрессии 2, 4, 8, 16…) можно покрыть с помощью тримино, когда отсутствует произвольная клетка доски. Впервые доказательство было опубликовано в 1938 году [73] . Позже его повторил Э.Б. Эскотт (см. статью в журнале «Open Court» [74] ). С тех пор математики включают это доказательство в свои книги, часто без ссылки на Голомба. Роджер Нельсен приводит Голомбово доказательство в виде единственной диаграммы,
73
S.W. Golomb, «Checker boards and polyominoes», American Mathematical Monthly 61: 675–682, 1954.
74
S.W. Golomb, Polyominoes (New York: Scribner, 1965).
75
R.Nelsen, Proofs Without Words II: More Exercises in Visual Thinking (Washington, D.C.: Mathematical Association of America, 2000).
76
При этом недостающая клетка может находиться в любом месте квадрата 4-го порядка (аналогично рассмотренному выше случаю с досками 2 и 4-го порядка).
Порядки 5 и 7
Далее нас ждет доска 5-го порядка, поскольку 5 — следующее число в последовательности (1), для которого мы пока не вывели доказательства. Если убрать центральную клетку, полученную фигуру можно покрыть очень аккуратно и симметрично (как показано на рис. 4. слева). Я покрыл эту доску четырьмя элементами 2x3. Каждый из них можно в свою очередь двумя различными способами покрыть двумя тримино. Покрытия 2x3 — очень полезный инструмент при решении задач с тримино. Когда недостающая клетка расположена, как показано черным на рис. 4 (средний квадрат), клетку над ней, как нетрудно убедиться, приходится покрывать с помощью тримино, примыкающего слева или справа. В любом случае у нас появятся две свободное клетки (они обозначены как 1 и 2), которые нельзя покрыть тримино. И в самом деле, квадрат 5-го порядка можно покрыть тримино, только если недостающая клетка находится в одной из позиций, обозначенных черным на рис. 4. справа. Вот вам приятное упражнение: посмотрите, удастся ли вам покрыть доску, если вырезанная клетка находится в углу.
Доску 7-го порядка анализировать гораздо труднее. Я не сумел придумать одиночную диаграмму, которая доказывала бы, что такую доску можно покрыть тримино, однако Голомб прислал мне свое неопубликованное доказательство, где он использует три диаграммы.
Его доказательство развивается так. На рис. 5 показаны три способа покрытия доски 7-го порядка. Очевидно, что при каждом таком покрытии квадрат 2x2 можно покрыть с помощью тримино, если недостающая клетка находится в любом из его четырех углов. Поворачивая эти три фигуры, можно добиться того, чтобы недостающая клетка приходилась на любое место доски.
Несколько труднее придумать, как покрыть доски с помощью максимального количества элементов 2x3. Вот вам задачка: сможете ли вы покрыть доску 7x7 с помощью шести элементов 2x3 и четырех тримино (рис. 6)? Решение — единственное (если не считать его зеркального отражения). (Это решение приводится на с. 204).
Посмотрев на рис. 5, можно отметить, что для каждого приведенного разбиения количество свободных тримино (не входящих в элементы 2x3) оказывается четным. И это не совпадение. Мне удалось вывести следующий тривиальный закончик. Когда порядок доски — четный, количество свободных тримино при покрытии — нечетное, и наоборот: когда порядок доски — нечетный, число свободных тримино должно быть четным.
Доказать эти равенства просто. Если доска имеет четный порядок, то после удаления одной клетки количество тримино при любом способе покрытия составит величину, равную (n 2–1)/3, т. е. нечетное число. В каждом элементе 2x3 содержится два тримино, а значит, общее количество тримино, входящих в состав элементов 2x3, неминуемо окажется четным. Если вычесть это четное число из общего числа тримино (а оно — нечетное), мы получим нечетное число тримино, не входящих ни в один элемент 2x3.
Пусть доска имеет нечетный порядок. После удаления одной клетки на доске останется четное число клеток. «Вычтем» из него четное число тримино, входящих в элементы 2x3, и получим четное число тримино, в такие элементы не входящих.
Выше 7-го порядка
Индуктивное доказательство Голомба применимо к бесконечному числу рядов, чьи элементы удваиваются. В частности, после того как мы успешно покрыли доску 7x7, можно понять, как покрываются доски размером nxn, где 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… Понятно, что эта методика дает нам бесконечное количество покрываемых досок, длина сторон которых удваивается (это своего рода удваивающийся ряд). Просто располагайте в левом верхнем углу любой доски заведомо покрываемый квадрат со стороной, которая меньше стороны исходной доски либо равна ей. Если оставшуюся снизу и сбоку область большой доски вам удастся покрыть — значит, и большая доска покрываема.
Обычно труднее всего покрыть доски, у которых длина сторон — простое число. Проблему доски 17-го порядка удается решить, поместив в ее угол квадрат со стороной 13 и оставив внизу и сбоку область шириной 4. Проблему доски 19-го порядка — поместив в ее угол квадрат 14-го порядка (доказательство его покрываемости основано, в свою очередь, на таком же свойстве квадрата 7-го порядка) и получив угловую область шириной 5 (см. рис. 8).
ПОЛНЫЙ И УНИВЕРСАЛЬНЫЙ РЕЗУЛЬТАТ
Занимаясь разбиением этих фигур, я подобрался (но пока недостаточно близко) к тому, чтобы вывести индуктивное доказательство того, что все дефицитные квадраты покрываемы, за исключением квадрата 5-го порядка. Это доказательство в конце концов получили И. Пинг Чу и Ричард Джонсонбау [77] . Чу и Джонсонбау позаботились не только обо всех дефицитных квадратах, но и обо всех дефицитных прямоугольниках! Их индуктивное доказательство — слишком специальное, чтобы его здесь приводить. Коротко говоря, они продемонстрировали покрываемость для всех прямоугольников mxn (включая и квадраты — случай, когда m=n) с числом клеток, кратным 3 после удаления одного поля. Подобные доски покрываемы, если выполняются все четыре необходимых и достаточных условия:
77
L.P. Chu and R. Johnsonbaugh, «Tiling deficient boards with trominoes», Mathematics Magazine 59:34–40,1986.