Оригинал доступен на сайте nstarr.people.amherst.edu. Автор — Нортон Старр

О головоломке – физической и виртуальной

v-21 puzzleБазовая головоломка состоит из: 21 прямоугольной фигуры («плитки») указанного вида, состоящих из трех квадратов, одной дополнительной одинарной квадратной плитки и плоскости с сеткой 8×8 квадратов, у которых такой же размер, что и у квадратов плиток. В общей сложности плитки занимают 3 × 21 + 1 = 63 + 1 = 64 квадрата — столько же, сколько на шахматной доске. В дальнейшем мы будем называть эти угловые фрагменты тримино, в качестве простейшего из нескольких названий, используемых для них, среди которых есть «L-тримино», «L-тримино» и «V-тримино».

Чтобы сыграть в физическую версию этой головоломки — используя 21 настоящую плитку тримино, одну квадратную деталь и основу, похожую на шахматную доску размером 8×8 – для начала поместите единственную квадратную плитку в любую из 64 квадратных ячеек на поле. Затем заполните оставшиеся 63 ячейки используя тримино так, чтобы не получилось перекрытия или незаполненной ячейки. Такое решение головоломки называется мозаичной облицовкой квадрата 8×8. Как вариант, начните с последовательного размещения тримино на поле шахматной доски (каждая такая плитка занимает только три квадрата сетки), а когда все 21 расположены, поместите единичную квадратную плитку в ту ячейку, которая осталась доступной.

Вот предыстория коммерческой версии этой головоломки, продаваемой  Kadon Enterprises. На ежегодном собрании Математической ассоциации Америки в январе 2000 года Артур Бенджамин получил премию Haimo за выдающееся преподавание в колледже. В своей благодарственной речи он набросал свое любимое доказательство по методу индукции. Данная аргументация гарантирует, что квадрат 2n×2n клеток (то есть универсальная разграфленная доска с квадратами в количестве 2n по каждой стороне) с одной занятой ячейкой всегда может быть выложена плитками тримино. Через три года после того, как я услышал комментарии Бенджамина, я давал лекцию по индукции и вспомнил его любимое доказательство. В дополнение к моим подготовленным примерам я привел этот классический аргумент из-за Соломона Голомба. Посчитав, что реально существующая головоломка такого рода добавит подлинности и сможет вызвать интерес к методу индукции, я отправил письмецо Kadon, ведущему производителю головоломок, чтобы узнать, есть ли у них что-нибудь, что я могу купить. У них такого не было, поэтому я спросил, сделают ли они несколько согласно заданными мной характеристиками. Ряд электронных писем в переписке с Кейт Джонс, президентом Kadon, привела к головоломке, подобной той, что изображена слева вверху. Она предложила использовать несколько разных цветов для плиток тримино, что сделало эту головоломку более интересной, чем я предполагал. Я сделал выбор в пользу более полупрозрачных плиток холодных оттенков, а не цветастых непрозрачных, и предпочел для тримино синий, цвет морской волны и аметистовый.

Кейт спросила, позволю ли я Kadon добавить головоломку ко множеству предметов, которые они продают, и я с готовностью согласился – мне нужны были только несколько штук для моего личного пользования. К моему удивлению, она заявила, что я буду получать авторские отчисления. Это никогда не было моей целью, и все мои авторские отчисления пожертвованы  Коледжу Амхерста и Математической ассоциации Америки.

Kadon выпустил головоломку под названием «Vee-21»; см. по ссылке www.gamepuzzles.com/polycub2.htm#V21. Эта коммерческая версия, в трех ярких, полупрозрачных акриловых цветах, идет с брошюрой на сорок страниц, предлагающей множество улучшений к основной загадке. Кейт внесла в головоломку некоторые дополнения, несколько стратегических игр, рассчитанных на двух человек и предложила требования к разделению элементов по цвету для мощения мозаикой с первой попытки. Она также открыла эстетические варианты в создании симметричных узоров. Кейт пригласила Ориэля Максиме для решения некоторых из его лабиринтообразных задач, связанных с покрытием плитками тримино; также в брошюру включены разнообразные прямоугольные шаблоны со стратегически выбранными линиями решеток, с затемненными ячейками, для указания рамок, где нельзя размещать тримино.

Здесь представлены две интерактивные компьютерные головоломки.  Головоломка 8 на 8 была разработана двумя моими студентами, в то время как коллега по кафедре разработал головоломку M-by-N. Головоломка M-by-N (воспроизводится в большинстве систем, но может медленно загружаться) несколько более гибкая, позволяющая выбирать любое количество строк и столбцов от 2 до 32 включительно. У головоломки 8 на 8 (лучше всего работает на ПК с Internet Explorer) имеется иное действие мыши, а также она эффективно ограничена тремя цветами тримино. Направления даны с каждым. И онлайн-версии, и версии Kadon обладают необычайной степенью привлекательности и интригуют как четырехлеток, так и маститых любителей головоломок.

История

Доказательство того, что при любом натуральном числе n квадрат 2n×2n с одной занятой ячейкой («некомплектным» квадратом) всегда может быть выложен плитками тримино, принадлежит Соломону Голомбу. Он опубликовал его в своей статье 1954 года [9] в American Mathematical Monthly. Как отмечалось выше, головоломка была создана для наглядной иллюстрации аргумента Голомба о некомплектном квадрате, которым была укомплектована головоломка 2n×2n. Та же его статья ввела в обиход термин тримино и его обобщенный вариант — полиомино. Поломино – это связная структура из идентичных квадратов, обладающая таким свойством, что любые два квадрата либо не касаются друг друга, либо соприкасаются по всей длине общего ребра. Единственно возможные две формы тримино — это три квадрата подряд и L-образная форма данной головоломки, и здесь имеется в виду исключительно вторая форма «тримино».

Доказательство Голомба является первоклассным примером математической индукции. Помимо очевидной простоты аргументации, это редкий случай нечислового применения метода. Оно отличается от примеров и упражнений, часто встречающихся в интерпретациях индукции (приведенных в учебниках), которые обычно состоят из множества формул для конечных сумм, неравенств и тому подобного. Первое появление доказательства в массовом издании – это Recreational Mathematics Magazine (RMM) Джозефа Мадачи, где Голомб включил его в первую из четырех статей о полимино, опубликованных в RMM [10]. В судьбоносной статье Мартина Гарднера, опубликованной в мае 1957 года в журнале Scientific American, в которой полимино были представлены для широкой публики, он отметил, что «доска с одним квадратом, пропущенным в любой точке, может быть покрыта 21 правильными тримино» [6, с. 154]. В своей первой книге, состоящей из колонок, опубликованных в Mathematical Games, Гарднер объяснил, что «гениальная аргументация индукции демонстрирует, что 21 правильное тримино и одно мономино покроют доску 8 на 8 независимо от того, где размещено мономино» [8, с. 126].

Аргументация  выкладывания для некомплектных шахматных досок с помощью тримино, а также общая теорема 2n×2n после статей в Monthly и RMM появились в ряде книг. Это было объяснено в классических «Полимино» Голомба [11, 1965, с. 21-22] и во втором издании данной книги [11, 1994, с. 5]. Второе издание содержит богатую историю и обширный обзор этой интригующей темы, и наполнено иллюстрациями и головоломками. Его 22 страницы со ссылками на книги и статьи являются дополнительным бонусом. Именной указатель включает 81 человека, немало из которых упомянуты в тексте книги более одного раза. Многие из них будут узнаны страстными поклонниками игр и математиками-любителями, а также профессионалами в любой области. Описание книги дано в обзоре [17] Джорджа Мартина. В 1976 году Росс Хонсбергер дал понятное и подробное применение аргументации Голомба для шахматной доски в своих «Математических сокровищах II» [13, с. 61]. Основная идея доказательства упоминается также  в книге Джорджа Э. Мартина, посвященной мозаикам полимино [16, с. 27-28]. Рецензия Дэвида Сингмастера [22] на эту последнюю книгу особенно интересна, так как она дает великолепный очерк предмета и его истории.

Эта тема также становится все более обычной частью в учебниках и задачниках. К примеру, она появляется в учебниках по дискретной математике Сюзанны Эпп [5, с. 234], Ричарда Джонсонбо (который упоминает триминовые прямоугольники как такие, что появляются в VLSI моделях) [14, с. 58-59] и Кеннет Розен [20, с. 247-8]. Создание мозаик посредством тримино рассматривается также  в книге Дэниела Веллемана о построении доказательств [26, с. 271-275] и задачниках Джона П. Д’Анджело и Дугласа Б. Веста [1, с. 75], а также Иржи Германа, Радана Кучеры и Яромера Жимжи [12, с. 271]. Наиболее яркой иллюстрацией аргументации Голомба является дополнительное «доказательство без слов» Роджера Нельсена, приведенное во второй части книги с таким же названием [19, с. 123].

Данная область развлекательной математики извлекла выгоду из непрерывного потока исследований и предложенных проблем. В 1985 и 1986 годах И-Пинг Чу и Ричард Джонсонбо изучали вопрос о выкладывании мозаикой некомплектных n×n полей (где n больше не обязано быть во второй степени) и, в более широком смысле, о некомплектных и комплектных прямоугольных полях [3, 4]. Книга Джорджа Мартина включала в себя целую главу, посвященную выкладыванию мозаики посредством тримино [16, с. 23-37]. Вопросы колористики относительно плиток тримино рассматриваются Илварсом Мизниксом, который признает, что страница Kadon с выбором цвета для Vee-21 вдохновила его на исследование [18]. Статья Дж. Маршалла Эша и Соломона Голомба о мощении тримино некомплектных прямоугольников, опубликованная в 2004 году, содержит несколько новых и базовых результатов, один из которых отвечает на давний вопрос Чу и Джонсонбо. Эш и Голомб завершают статью открытым вопросом касательно 2-некомплектных прямоугольников (прямоугольников, где удалены две клетки).

Интернет – хороший источник в плане демонстрации и информации о создании мозаик. Например, поиск по «tromino» и «tiling» приводит к появлению апплетов, таких как апплеты Александра Богомольного www.cut-the-knot.org/Curriculum/Games/TrominoPuzzle.shtml и Кристофера Маваты www.utc.edu/Faculty/Christopher-Mawata/trominos/, демонстрирующие пазлы Тромино нескольких размеров.

Вариации

Вот некоторые расширения головоломки тримино, которые читатели могут рассмотреть. Первое было предложено моим братом Раймондом (Питом), который спросил, как можно расположить тримино в сетке 8×8 таким образом, чтобы максимизировать число незанятых квадратов. Это может быть рассмотрено более подробно: один способ предполагает, что плитки и сетка расположены таким образом, чтобы оставаться на месте, а альтернативный способ может позволить плиткам скользить так, чтобы позволить втиснуть как можно больше плиток (всегда в пределах линий сетки). Пит был не в курсе, что версия с фиксированным расположением представляет собой вариацию головоломки с размещением пентамино, которая принадлежит Голомбу и описанна Гарднером [7, с. 128], [8, с. 133]. Голомб применил эту головоломку для игры пентамино, рассчитанную на двух человек [7, с. 128] и [8, с. 133-135], правила которой могут быть применены и к головоломке тримино. Дэвид Кларнер рассказал об игре пентамино для двоих – Pan-Kāi (разработанной Алексом Рэндольфом и опубликованной в 1961 году силами Phillips Publishers), – которая  содержала следующее ограничение: «Самое важное правило состоит в том, что запрещено размещать плитку внутри закрытой области доски, если незанятыми остаются менее 5 ячеек, за исключением того случая, когда в результате хода участок полностью закрывается [15, с. 8] (для более дополнительной информации о Рэндолфе и Pan-Kāi см. [21, стр. 75]).

Еще одно направление – трехмерное. Рассмотрим куб с длиной стороны 2n, содержащий 23n элементарных ячеек, одна из которых занята (единичная прореха). Могут ли остальные ячейки быть заполнены трехмерными тримино (три куба в форме буквы L, два из которых встречаются с третьим на двух смежных гранях последнего)? Необходимое условие 2n = 3k + 1 оказывается достаточным в той же мере [23, Глава 6: Трехмерная мозаика Тримино Нортона Старра], [24, с. 72-87], [25]. В случае с кубом 4×4×4 возникают некоторые незначительные трудности, которые могут развлечь юных любителей головоломок.

Более простые задачи вполне очевидны и были рассмотрены многими другими. Например, можно ли выложить тримино квадратные массивы 3×3 и 6×6? Можно ли выложить тримино некомплектное поле в 5×5 или 7×7 квадратов? Эти последние две головоломки являются более сложными, чем случаи с полными 3×3, 6×6 и некомплектным 8×8. Далее читатели могут рассмотреть создание мозаики из различных прямоугольных массивов – см. Ссылки, указанные ниже. При использовании версии с более чем одним цветом тримино, такой, как Vee-21 от Kadon, учитывайте различные цветовые ограничения. Например, попробуйте расположить плитки так, чтобы две плитки одного цвета никогда не имели общую грань. И наоборот, попытайтесь сгруппировать как можно больше плиток одного цвета. При создании паттернов обоих указанных типов размещения попробуйте сделать так, чтобы мозаика выглядела симметрично относительно диагонали либо же относительно горизонтальной или вертикальной линии. Существует множество возможностей для веселья и открытий. Прямоугольники разных размеров можно изучить, кликнув на  головоломку M-by-N. Для экспериментов с цветными схемами лучше всего подойдет головоломка Kadon.

Ссылки:

  1. Дж. П. Д’Анджело и Д. Б. Уэст, Математическое мышление: Решение задач и доказательства, второе издание, Prentice Hall, Аппер-Седл-Ривер, Нью-Джерси, 2000.
  2. Дж. М. Эш и С. В. Голомб, Черепица дефектных прямоугольников с тримино, Math. Mag., 77 (2004), стр. 46-55. (Доступно здесь – math.depaul.edu/~mash/TileRec3b.pdf)
  3. И. П. Чу и Р. Джонсонбо, Выкладывание некомплектных полей с помощью тримино, Math. Mag, 59 (1986), стр. 34-40.
  4. И. П. Чу и Р. Джонсонбо, Выкладывание полей с помощью тримино, J. Recreational Math., 18 (1985-86), стр. 188-193.
  5. С. С. Эпп, Дискретная математика с приложениями, Третье издание, Томсон, Белмонт, Калифорния, 2004.
  6. М. Гарднер, О поразительном сходстве между Икосиан и Ханойской башней, Scientific American, 196, (май 1957), стр. 150-156. Эта колонка была изначально посвящена схемам Гамильтона, но заканчивается разделом о проблемах при выкладывании мозаикой шахматной доски: Гарднер заявляет, что проблема шахматной доски/домино в февральской колонке «побудила Октава Левеншпиля из Бакнельского университета обратить мое внимание на замечательную статью С. В. Голомба в American Mathematical Monthly за декабрь 1954 года».
  7. М. Гарднер, «Больше о сложных домино плюс ответы на головоломки прошлого месяца», Scientific American, 197 (декабрь 1957), стр. 126-140. Эта колонка «Математических игр» начинается с сообщения о взрывном влиянии краткого отчета майской колонки о работе Голомба [6]: «За год, прошедший после открытия этой кафедры, он получил больше писем об одном из математических воссозданий, чем какая-либо иная… задача “пентамино”… Сотни корреспондентов прислали самые различные решения. Многие засвидетельствовали о странном увлечении этой задачей».
  8. М. Гарднер, Американская научная книга математических головоломок и увеселений, Simon and Schuster, Нью-Йорк, 1959. (Перепечатано и обновлено как Гексафлексагон и прочие математические увеселения, University of Chicago Press, 1988) [Глава 13 этого первого сборника подобного рода объединяет материал по созданию мозаики [6] и [7] и называется «Полимино»].
  9. С. В. Голомб, «Шахматные доски и полимино», Amer. Math. Monthly, 61 (1954), стр. 675-682.
  10. С. В. Голомб, «Общая теория полимино. Часть I – Домино, пентамино и шахматная доска», Recreational Math. Mag., Выпуск № 4 (август 1961 года), стр. 3-12.
  11. С. В. Голомб, Полимино, Scribner’s, Нью-Йорк, 1965. (Второе издание: Полимино, головоломки, схемы, вопросы и укладка, Princeton University Press, Принстон, 1994).
  12. И. Герман, Р. Кучера и Я. Жимжа. Подсчеты и конфигурации: проблемы комбинаторики, арифметики и геометрии (Карл Дилчер, переводчик), Springer-Verlag, Нью-Йорк, 2003.
  13. Р. Хонсбергер, Математические сокровища II, Математическая ассоциация Америки, Вашингтон, округ Колумбия, 1976.
  14. Р. Джонсонбо, Дискретная математика, шестое издание, Pearson Prentice Hall, Аппер-Седл-Ривер, Нью-Джерси, 2005.
  15. Д. Кларнер, Головоломка с собиранием коробки. Многочисленные заметки, Университет Ватерлоо, Онтарио, 1973-74; 42 страницы + титульный лист (частично они подытожены у Хонсбергера в 8 Главе [13]).
  16. Дж. Э. Мартин, Полимино, Руководство по головоломкам и вопросам по сборке, Математическая ассоциация Америки, Вашингтон, округ Колумбия, 1991.
  17. Дж. Э. Мартин, обзор Полимино С. Голомба (издание 1994 года), Mathematical Reviews, MR1291821 (95k: 00006), 1995.
  18. И. Мизникс, Компьютерный анализ трехцветной задачи для V-образных форм», Acta Societatis Mathematicae Latviensis, Тезисы 5-й Латвийской математической конференции, 6-7 апреля 2004 года, Даугавпилс, Латвия. (Доступно по ссылке http://www.de.dau.lv/matematika/lmb5/tezes/Mizniks.pdf)
  19. Р. Б. Нельсен, Доказательства без слов II, Больше упражнений в визуальном мышлении, Математическая ассоциация Америки, Вашингтон, округ Колумбия, 2000.
  20. К. Х. Розен, Дискретная математика и ее приложения, издание пятое, McGraw-Hill, Нью-Йорк, 2003. (Появится в качестве примера №13, в разделе 4.1, в шестом издании, 2007 г.)
  21. Дж. Н. Сильва (ред.) Коллоквиум I по занимательной математике (Труды конференций, 29 апреля – 2 мая 2009 года, Университет Эвора), Associação Ludus, Лиссабон, 2010.
  22. Д. Сингмастер, Обзор Полимино Г. Е. Мартина, Mathematical Reviews, MR1140005 (93d: 00006), 1993.
  23. А. Сойфер, Геометрические этюды в комбинаторной математике, издание второе, Springer, Нью-Йорк, 2010.
  24. Н. Старр, Сборка некомплектных кубов с длиной стороны 2n посредством тримино, Geombinatorics XVIII (2) (2008), стр. 72-87.
  25. Н. Старр, Сборка некомплектных кубов с длиной стороны любого размера посредством тримино, http://arxiv.org/abs/0806.0524, 3 июня 2008 года.
  26. Д. Дж. Веллеман, Как это доказать: структурированный подход, издание второе, Cambridge University Press, Нью-Йорк, 2006.