22
С. Адеев
Регуляное полимино
Имя С. В. Голомба — американского ученого, специалиста в области теории информации и статистики — хорошо известно любительям занимаетельной математики. Голомб изобрел замечательную серию игр, который он дал общее название «полимино». Этот игр посвязывано множество публикаций в самых различных журнальных журналах. «Квант» также неоднократно обращался к этой теме, а в 1975 году в издательстве «Мир» вышла книга самого автора этого изобретения, содержащая много красивых и занимаательных математических задач *).
Вот пример «полиминошной» задачи (она была помещена в одном из номеров «Кванта»): Докажите, что из трех уголков и соответствующего числа плиток, но доказать это черезчайно трудно. Как правило, подобные задачи не могут исследовать метод перебора даже быстроеstruzione ЭВМ. Поэтому для их решения приходит到 весма хитроумные методы. Об одном из них, основном на раскрасках, рассказываясь в «Кванте» № 11 за 1972 год. В этой заметке мы рассекем о совсем другом подходе, связанном с … географией и игральнойкостью.
География на клетчатой бумаге и игральнаякость
Все дальнейшие события в нашей статье будут происходить на клетчатой бумаге, сабженной «географический ориентировкой» (рис. 2). По этой клетчатой бумаге мы будем перекатывать по определенным правилам обикновенную игральнуюкость — кубик с ребром единчной длины и пропумерованным гранями. Кубик всегда будет расположен на бумаге так, чтобы центр его нижней грани совпадал с узлом сетки, а боковые грани были параллельны линям сетки. Каждому положению кубика на клетчатой бумаге поставим в соответствии два числа — номера южной и верхней граней. Изовем эту пару чисел орientацией кубика.
Уражнение 1. Сколько существует различных ориентиций кубика?
Пусть задан путь Γ, соединяющий узлы A и B сетки. Мы, разумется, будем рассматривать пути, индические только по линям сетки. Если кубик стоит на узле A, то его можно
*) «Полимино» (М., «Мир», 1975)
Рис. 1.
Рис. 2.
23
перекатить вдоль пути Γ на узел B (рис. 3). При этом его начальная ориентация α заменится на некоторую ориентацию β. Будем записывать это следующим образом: β = Γ(α).
У разженние 2. Пусть зафиксированы узлы A и B и начальная ориентация α. Докажите, что, перекатывая кубик по всевозможным пути из A в B, можно получить не больше половины ориентации кубика. Убедитесь, что пользовну ориентацию получить всегда можно.
Если конец пути Γ₁ совпадает с началом пути Γ₂, то возникает путь Γ₂°Γ₁, составленный из этих двух путей (рис. 4). Кроме того, для каждой пути Γ естественно определяется «обратный» путь Γ⁻¹, получающийся заменой направления вдоль пути Γ на обратное. Легко убедиться (сделайте это), что (Γ₂°Γ₁)(α) = Γ₂(Γ₁(α)) и Γ⁻¹(Γ(α)) = α.
Назовем путь Γ резуллярным, если Γ(α) = α для некоторой ориентации α.
У разженние 3. Докажите, что a) если Γ — резуллярный путь, то Γ(β) = β для любой ориентации β;
б) если Γ — резуллярный путь, то и Γ⁻¹ — резуллярный путь;
в) если Γ₁ и Γ₂ — резуллярные пути и путь Γ₂°Γ₁ определяен, то и Γ₂°Γ₁ — резуллярный путь.
У разженние 4. Докажите, что всякий резуллярный путь имеет четную длину, и приведите пример нерезуллярного пути четной длины.
Регулярное полимно
Тепер вернемся к полимно. Напомним, что полимно — это много-
году гольник, составленный из одноклеточных квадратов, причем любой квадрат примыкает хотя бы к одному соседнему по стороне (то есть шахматная ладья может пройти с любой клетки полимно на любую другую). Общная задача из теории полимно формулируется так: можно ли из данного набора полимно сложить данную фигуру? Мы сумем решить целый класс таких задач. Будем рассматривать полимно как многоугольник, нарисованный на нашей клетчатой бумаге. Hazовем полимно регулярным в узле A, если регулярен путь, ищущий по его контуру с началом и концом в узле A, лежащем на этом контуре. Оказывается, это определение не зависит от выбранного узла.
У разженние 5. Если полимно регулярно в некотором узле его контура, то оно регулярно и в любом другом его узле. Докажите.
Упражнение 5 дает нам возможность говорить просто о регулярных полимно. Несколько таких полимно приведено на рисунке 5.
У разженние 6. Докажите, что эти полимно регуляры.
Оказывется, из регулярных полимно нельзя использовать негулярное полимно. Чтобы убедиться в этом, достаточно доказать следующее:
Теорема о сумме. Если полимно P и Q резуллярны и полимно T сложено из них, то оно может резуллярно.
Пояснения к доказательству этой теоремы даны на рисунке 6.
Можно доказать и теорему о разности: если полимно T, сложенное из полимно P и Q, резуллярно и полимно P резуллярно, то и полимно Q резуллярно.
У разженние 7. Докажите теорему о разности полимно.
У разженние 8. Докажите, что прямоугольное полимно регулярно тогда и только тогда, когда его площадь кратна четырем.
Из теоремы о сумме и упражнения 6 и 8 сразу вытекает решение задачи, похожей на задачу про узолки, — доказать, что из любого количества полимно, приведенных на рисунке 5, нельзя сложить прямоугольника с площадью, не кратной четырем.