Страница 31 из 54
Посмотрев на рис. 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… Понятно, что эта методика дает нам бесконечное количество покрываемых досок, длина сторон которых удваивается (это своего рода удваивающийся ряд). Просто располагайте в левом верхнем углу любой доски заведомо покрываемый квадрат со стороной, которая меньше стороны исходной доски либо равна ей. Если оставшуюся снизу и сбоку область большой доски вам удастся покрыть — значит, и большая доска покрываема.
Обычно труднее всего покрыть доски, у которых длина сторон — простое число. Проблему доски 17-го порядка удается решить, поместив в ее угол квадрат со стороной 13 и оставив внизу и сбоку область шириной 4. Проблему доски 19-го порядка — поместив в ее угол квадрат 14-го порядка (доказательство его покрываемости основано, в свою очередь, на таком же свойстве квадрата 7-го порядка) и получив угловую область шириной 5 (см. рис. 8).
ПОЛНЫЙ И УНИВЕРСАЛЬНЫЙ РЕЗУЛЬТАТ
Занимаясь разбиением этих фигур, я подобрался (но пока недостаточно близко) к тому, чтобы вывести индуктивное доказательство того, что все дефицитные квадраты покрываемы, за исключением квадрата 5-го порядка. Это доказательство в конце концов получили И. Пинг Чу и Ричард Джонсонбау[77]. Чу и Джонсонбау позаботились не только обо всех дефицитных квадратах, но и обо всех дефицитных прямоугольниках! Их индуктивное доказательство — слишком специальное, чтобы его здесь приводить. Коротко говоря, они продемонстрировали покрываемость для всех прямоугольников m×n (включая и квадраты — случай, когда m=n) с числом клеток, кратным 3 после удаления одного поля. Подобные доски покрываемы, если выполняются все четыре необходимых и достаточных условия:
1) m ≥ 2,
2) n ≥ m,
3) если m=2, n должно тоже равняться 2,
4) m ≠ 5.
Прямоугольник 4×7 — самый маленький дефицитный прямоугольник (не квадрат), который можно покрыть с помощью L-тримино. Вот еще одно упражнение: много ли у вас уйдет времени на то, чтобы покрыть такую фигуру с помощью тримино и двух элементов 2×3, если недостающая клетка у этой фигуры располагается в углу?
Кристофер Йенсен показал в своей неопубликованной статье, что если в углу любой доски убрать две клетки, как показано на рис. 9. получившуюся доску нельзя будет покрыть с помощью тримино. Однако, если исключить приведенные пять случаев, доску с длинами сторон 3m–1 и 3n+1 и с любыми двумя недостающими клетками окажется возможным покрыть при следующем необходимом и достаточном условии: либо если n=1, либо если m ≥ 3 и n ≥ 3.
Заключение
Кейт Джонс, основавшая и возглавляющая фирму «Kadon Enterprises», которая выпускает и продает разные симпатичные механические головоломки и другие забавные математические предметы, выпустила на рынок игру под названием «V-21»[78]. Буква V здесь — от «V-тримино», а 21 — число тримино в наборе, где кроме ярко раскрашенных фишек имеется также доска 8-го порядка, на которую их можно класть. Первое задание — положить мономино (квадрат 1-го порядка) в произвольное место доски, а затем покрыть оставшуюся площадь с помощью тримино (т. е. решить задачу для доски 8-го порядка). К игре прилагается сорокастраничное руководство. В нем напечатана короткая статья Нортона Старра «Дефицитная шахматная доска» и приводятся изображения прямоугольных досок и задачи к ним.
Завершим наш рассказ красивейшим симметричным покрытием стандартной шахматной доски (рис. 10).
А вот и ответ на задачу, которую я предложил вам на с. 197:
Глава 12
Ay, мистер Херш, вы «здесь»?
Рубен Херш принадлежит к небольшой группе математиков, убежденных, что математика реальна лишь в контексте человеческой цивилизации. А я — бесстыжий платоник и предпочитаю иной язык мышления, предполагающий, что если из Вселенной исчезнут все разумные существа, то математические объекты и теоремы в каком-то смысле никуда не денутся — даже если не останется никого, кто смог бы писать или говорить о них. Гигантские простые числа продолжают быть простыми, хоть никто и не доказывал, что они являются таковыми. Как выразился однажды Бертран Рассел, даже в центре Солнца дважды два — четыре.
77
L.P. Chu and R. Johnsonbaugh, «Tiling deficient boards with trominoes», Mathematics Magazine 59:34–40,1986.
78
K. Jones, Vee-21 available at www.gamepuzzles.com/polycub2.htm#V21.