Головоломок вишенка в коктейле

Головоломок вишенка в коктейле

Содержание

Blog

Содержание

Вид материала

Глава 1 1
Подсчетом полиаболо практически никто не занимался. Несколько читателей сходятся на том, что число существующих гепта

Подобный материал:

1 2 3 4 5 6 7 8 9 10

^ ГЛАВА 1 1

_{Полигексы и полиаболо}

Обычные паззлы-картинки практически лишены математического интереса: кусочки в них ставятся на место путем проб и ошибок, и при наличии достаточного упорства и терпения рано или поздно картинка будет собрана. Но если головоломка состоит из деталей в форме простых многоугольников, задача составления из них определённой фигуры уже относится к области комбинаторной геометрии, и её решение требует серьёзного математического анализа, а возникающие при этом вопросы порой оказываются совсем не тривиальными. Если при выборе множества многоугольных деталей применить простые правила комбинаторики, задача приобретает изящество, а исследование комбинаторных свойств этого множества оказывается не только способом убить время, но и весьма захватывающим занятием.

У любителей математических головоломок наибольшей популярностью пользуются так называемые «полиомино». Они представляют собой набор квадратных деталей, которые нужно сложить всеми возможными способами. Этой разновидности головоломок посвящено множество работ — в том числе книга Polyominoes («Полиомино») Соломона В. Голомба, профессора университета Южной Калифорнии. Другая хорошо изученная разновидность составных фигур — это «полиамонды», получающиеся при соединении по граням равносторонних треугольников. Гексиамонды (полиамонды, состоящие из шести равносторонних треугольников) рассмотрены в моей книге Sixth Book of Mathematical Games from Scientific American («Шестой книге математических игр от Scientific American»).

Многие читатели, полюбившие задачи с полиомино и поли-амондами, предложили мне другие способы выбора основного набора многоугольников, на основе которых можно придумывать подобные головоломки. В этой главе мы рассмотрим два таких набора, которые чаще всего упоминаются в письмах читателей. Однако до сих пор сведений в печати о них крайне мало.

Так как существует только три типа равносторонних многоугольников, которыми можно заполнить поверхность (квадрат, равносторонний треугольник и правильный шестиугольник), то в первую очередь на ум приходит именно составление различных фигур из набора одинаковых шестиугольников. Два шестиугольника можно соединить всего двумя способами, три — тремя, а четыре — семью. Из-за того что такие фигуры напоминают структурные химические формулы веществ с бензольными кольцами, двое читателей, Элинор Шварц и Джеральд Дж. Клутье, предложили называть их «бензена-ми». Предлагались и другие названия. Однако мне кажется наилучшим вариант «полигексы», предложенный Дэвидом Кларнером, одним из первых исследователей таких фигур. На рис. 58 показаны 7 тетрагексов с названиями, предложенными читателями.

Следующий по числу составных частей набор шестиугольников — пентагекс — имеет 22 разновидности, так что в качестве развлечения несколько громоздок. Гексагексов существует 82, гептагексов — 333, а октагексов — 1448. (Зеркальные отражения не считаются отдельными фигурами.) Подобно случаям полиомино и полиамондов, для вычисления числа полигексов, которые могут быть сложены из данного числа шестиугольников, формула пока не найдена.

Читателю предлагается вырезать набор тетрагексов из картона. Если у вас дома пол выложен шестиугольными плитками, вы можете вырезать детали соответствующего размера, чтобы использовать пол в качестве игрового поля для составления тетрагексов. Из восьми симметричных фигур, представленных на рис. 59, все, кроме одной, можно составить из полного набора (семи тетрагексов). Многие читатели предлагали в своих письмах «ромб», «треугольник» или «башню». «Клякса» и «виноградная гроздь» — изобретения Ричарда Э. Хорвитца, «кольцо» — Клутье, «пирамида» — Кларнера, а «ковер» — Т. Марлоу и Кларнера. Можете ли вы найти здесь фигуру, не составляющуюся из семи тетрагексов? Пока не найдено простого доказательства её невозможности. (Эта фигура — не «башня», хотя сложить её трудно, и существует лишь один способ сделать это, если не считать банальной перестановки двух частей, образующей зеркальное отображение фигуры.) Использовать необходимо все семь деталей. Решения, полученные отражением всей конфигурации, не считаются отдельными.

Из 22 пентагексов (рис. 60) можно получить множество удивительных симметричных фигур. «Ковер» (который можно разделить на две части и составить из них более длинный и узкий ковер) придумал Роберт Дж. Кларнер (отец Дэвида Кларнера). Другие фигуры присланы Кристофом М. Хоффманом из Гамбурга. Обратите внимание на то, что два ромба можно сложить иначе и получить «ромб» (точнее сказать, параллелограмм) размером 5 х 22 шестиугольника. (Марлоу предложил различные способы составления такого двойного ромба и ромба, состоящего из двух треугольников.) Но ни из тетра-, ни из пентагексов нельзя составить шестиугольник. Однако Марлоу и мисс Шварц предложили способ составления этой фигуры со стороной 4 из семи тетрагексов и трёх тригексов.

Взяв неправильные многоугольники, мы увидим, что самые простые из них — это равнобедренные прямоугольные треугольники. Их можно соединять друг с другом катетами или гипотенузами. Мы будем называть катеты сторонами s, а гипотенузы — сторонами А. Первым описал эту группу фигур в литературе Томас О'Бирн (New Scientist, декабрь 1961). Воспользоваться деталями такой формы ему предложил житель английского Бристоля С. Дж. Коллинз, предложивший называть фигуры, состоящие из четырёх треугольников,

«тетраболо». Отсюда возникло общее название — «полиаболо». Существует три варианта диаболо, четыре триаболо, 14 тетраболо, 30 пентаболо и 107 гексаболо.

Набор из 14 тетраболо, представленный на рис. 61, имеет общую площадь в 28 квадратов со стороной s, или в 14 со стороной А. Так как оба эти числа не являются квадратами, составить из полного набора тетраболо квадрат невозможно. Квадрат размером 2s у. 2s имеет площадь, соответствующую площади двух тетраболо, — однако доказано, что составить его из них невозможно. Существует три квадрата, которые можно составить из неполного набора тетраболо (см. рис. 62).

£2*

wkm

1 шш Ш

Если вы вырежете из картона полный набор тетраболо, то наверняка получите удовольствие, составляя из них эти квадраты. Для самого маленького из них имеется лишь два решения, а для остальных найдены ещё далеко не все.

На рис. 63 показаны все прямоугольники со сторонами из отрезков s, площадь которых такова, что позволяет составить их из полного или неполного набора тетраболо. На рис. 64 — прямоугольники со сторонами из отрезков И. (Очевидно, что получить прямоугольник с двумя сторонами, равными И, невозможно, за исключением квадрата hxh.) Обратите внимание на то, что наибольшие по площади прямоугольники каждого типа, для составления которых необходим полный набор тетраболо, считаются неразрешимыми. Ниже я приведу замечательное доказательство этого, найденное О'Бирном и опубликованное им в собственной колонке в журнале New Scientist от 18 января 1962 года.

Большинство доказательств невозможности существования по-лиомино базируются на раскрашивании фигур по типу шахматной доски. Но в данном случае этот способ не помогает. Доказательство О'Бирна основано на числе сторон h, которые имеются у полного набора деталей. Если каждую деталь разместить таким образом, чтобы катеты составляющих её треугольников располагались по горизонтали и по вертикали, как на рис. 61, то их гипотенузы будут направлены либо наклонно влево, либо наклонно вправо. У фигуры А нет сторон, образованных гипотенузами (отрезками И). Эта и следующие восемь фигур (В, С, D, Е, F, G, Н, I) называются «четными», так как в каждой из них четное число отрезков h_y направленных в обе стороны. (Ноль также считается четным числом.) Остальные пять фигур (J, К, L, М, N) называются «нечетными», так как у них по нечетному числу отрезков h каждого направления.

Из того, что существует нечетное число «нечетных» фигур, следует, что неважно, каким способом составлена фигура со сторонами из отрезков s, ориентированных ортогонально. В ней все равно будет иметься нечетное число сторон из отрезков Л, направленных наклонно в обе стороны.

Теперь рассмотрим два прямоугольника, для построения которых требуется полный набор из 14 тетраболо. Очевидно, что в каждом прямоугольнике должно быть четное число отрезков h, направленных в обоих направлениях. Внутри такого прямоугольника любой отрезок И имеет пару — такой же отрезок, направленный в ту же сторону. Таким образом, полное число внутренних отрезков h обоих

	_\	_N
		_\	_\
2X4

	_\			_/
		_\	_/	_/
			_/
3X6

3X8

₁	■			■—1		: т 'f^,J,,lf; ■ 11	\| ! ,\|
т ■■' 1 1					¹_!._г₁_.А_,1₁	it

2Х(7... 14)

_\	\
	_/
_\	_А
А	\ X .	_/ 5

Рис. 63.

Прямоугольники из тетраболо со сторонами из отрезков s. Доказано, что серые прямоугольники невозможно составить из существующих тетраболо.

4X6

4X7

типов должно быть четным. В треугольнике же, стороны которого состоят из отрезков И, отрезков каждого типа по периметру также будет четное число. Таким образом, нельзя сложить прямоугольник из полного комплекта 14 тетраболо. Это доказательство нельзя применять для всех билатерально симметричных фигур. Возможно, вам будет интересно самостоятельно доказать это, попробовав сложить такую фигуру из 14 тетраболо.

Закрашенные серым прямоугольники на рис. 63, имеющие в высоту четное число отрезков s, а в длину 7 и более таких отрезков, не могут быть составлены из тетраболо. Это можно доказать, попробовав поместить внутрь такого прямоугольника шесть тетраболо (В, D, Е, G, М, N). Мы увидим, что это невозможно сделать, если не разбивать прямоугольник на две части, которые не будут представлять собой набор из квадратов со стороной s. Таким образом, эти тетраболо не могут входить в состав прямоугольника. Из оставшихся же тетраболо можно составить фигуру, максимальная величина периметра у которой будет равн# \7s. Однако прямоугольник размером 2x7 имеет периметр, равный 1 Ss, что на один отрезок s больше, чем имеется в частичном наборе из восьми тетраболо.

На рис. 63 и 64 показано разбиение на составные части всех прямоугольников, для которых известны эти способы (на основе тетраболо). Существуют ли четыре незаполненных прямоугольника? Для построения каждого из них требуется 12 тетраболо, то есть из полного набора должны быть исключены одна «четная» и одна «нечетная» фигура. Прямоугольник со сторонами 3x8, вероятно, невозможно составить из имеющихся тетраболо, так как его большой периметр значительно ограничивает число способов, которыми можно соединить составные части. Тем не менее ни для одного из этих четырёх четырёхугольников не найдено доказательства невозможности. И в то же время решения для них также пока не известны.

Читатели, уверенные в своих математических талантах, могут попробовать сложить непростую фигуру — квадрат, предложенный О'Бирном. Из полного набора тетраболо исключаются шесть симметричных фигур, не изменяющихся при перевертывании, и используются только оставшиеся восемь несимметричных (D, F, Н, 1, J, К, М, N). Так как их общая площадь равна 16 квадратам со стороной s, они могли бы составить квадрат со стороной 4s. Однако у такого квадрата по краям должны располагаться 16 одинарных s-ква-дратов, а из восьми данных тетраболо можно получить только 12 таких квадратов, расположенных по периметру. Но если брать не толь

ко сами восемь несимметричных тетраболо, но и их зеркальные отражения, то картина меняется. В данном случае мы имеем 16 деталей, которые нельзя переворачивать, то есть для решения нужно использовать обе зеркальные формы тетраболо. Все 16 деталей имеют общую площадь в 16 квадратов со стороной А. Можно ли получить из них квадрат со стороной в 4Л? О'Бирн доказал возможность этого. Однако построения оказались очень сложны и не были опубликованы.

С помощью тетраболо также можно найти ответ на необычный вопрос, поставленный К. Дадли Лэнгфордом из шотландского Эйршира и переданный мне британским математиком X. Мартином Канди. Лэнгфорд спрашивает, существуют ли такие четыре фигуры одинаковой площади, но разной формы (зеркальные отображения разными не считаются), которые можно сложить четырьмя различными способами так, чтобы получились четыре фигуры той же формы, но большей площади, чем исходные? В каждой большой фигуре должны присутствовать все четыре маленьких. Мне удалось найти простое решение этой задачи с применением четырёх тетраболо. Можете ли вы найти эти четыре фигуры и показать, как они складываются?

ДОПОЛНЕНИЕ

В Европе производились и продавались головоломки-тетрагексы, однако в США мне ничего подобного не попадалось. В 1971 году в продажу поступил набор пласт/массовых полигексов (из 10 деталей: трёх тригексов и семи тетрагексов) с прилагающимся буклетом задач Стюарта Т. Коффина под названием «Снежинка».

Многие читатели смогли найти доказательства единственности способа построения «башни» из тетрагексов (в двух зеркальных вариантах). Во всех доказательствах ключевым моментом является положение «пропеллера».

Эндрю К. Кларк из английского Чешира написал, что из любых полигексов 4-го и 5-го порядков можно составить непрерывную поверхность, а среди гексагексов таким свойством обладают все, кроме четырёх фигур. Также он указывает на то, что поверхность можно «замостить» любым полиаболо четвертого порядка. Для пятого порядка исключений уже четыре, для шестого — 19. Но эти результаты никем не подтверждены.

В.Ф. Ланнон, сотрудник Атласской компьютерной лаборатории в Чилтоне, Англия, подсчитал число существующих полигексов до 12-го порядка. Эти сведения опубликованы в статье Counting Hexagonal and Triangular Polyominoes («Подсчет шестиугольных и треугольных полиомино»), опубликованной в сборнике Graph Theory and Computing, под редакцией Р.К. Рида в 1972 году. Число существующих полигексов от 9-го до 12-го порядка равно соответственно 6572, 30 490, 143 552 и 683 101.

^ Подсчетом полиаболо практически никто не занимался. Несколько читателей сходятся на том, что число существующих гепта

боло — 318. Чарльз В. Тригг насчитал 1106 октаболо, а Роберт Оливер — 3671 нонаболо.

ОТВЕТЫ

Несуществующая фигура-тетрагекс из представленных на рис. 59 — треугольник. Доказательство невозможности его существования, представленное Дэвидом Кларнером, начинается с рассмотрения ограниченного числа положений, в которых может находиться «пропеллер».

На рис. 65 показано предложенное Кларнером решение для самой сложной фигуры — «башни». Обратите внимание, что закрашенная часть фигуры имеет ось симметрии, относительно которой её можно отобразить зеркально, и таким образом получить второе решение.

Один из способов составить квадрат из восьми асимметричных тетраболо и их зеркальных отображений (без переворачивания деталей) был найден независимо друг от друга в 1962 году двумя британскими энтузиастами — Р.А. Селтерингтоном из Таунтона и Э.Ф. Спинксом из Летчфорта (см. рис. 66). Детали G, H и М обра-

зуют фигуру, которая может быть зеркально повернута. Группы JKN и FJ К также можно повернуть, а СЕ можно поменять местами с MP, что даст нам различные варианты решения. Томас О'Бирн из Глазго недавно нашел новый способ размещения А, В, С, D, Е, F, G и Н, при котором из них составляется искомый квадрат, внутри которого в результате поворотов деталей вокруг своей оси и их взаимного обмена местами возможны и другие варианты решения. Одним словом, полный набор решений не только не найден, но и не подсчитан.

Из четырёх тетраболо можно составить фигуры, повторяющие по форме каждую из составных частей (см. рис. 67). Для этого необходимо лишь переместить треугольник. Обратите внимание, что при перемещении треугольника в другие позиции возникают фигуры, повторяющие очертания ещё четырёх тетраболо. В результате получается восемь различных фигур, то есть более половины всего набора тетраболо. Уэйд Э. Филпотт и другие заметили, что такая же задача может быть решена и для тетраболо С, I, К и L.

Имеются ли другие наборы из четырёх различных составных частей, обладающие теми же характеристиками? Морис Дж. Пова из Блэкберна, Англия, доказал, что их существует бесконечное число. Его доказательство основывается на решении, показанном на рис. 68, слева, где из четырёх октомино получается четыре различные фигуры большего размера, но тех же очертаний. При аффинном преобразовании, изменяющем углы, получаем бесконечное множество решений.

Пова также нашел решение для задачи с четырьмя гексамино (см. рис. 69). Эти детали соединяются в 15 различных гексамино, в том числе и в подобные себе. Пова считал, что для гексамино других решений не существует. Самое большее, чего он добился с пентамино, это четыре «укрупненные» детали, которые ему удалось сложить из четырёх исходных форм (правда, подобием форм пришлось пожертвовать).

_г

Рис. 69.

Решение задачи с получением подобных фигур из гексамино

Подборку задач с четырьмя прямоугольниками из тетраболо разрешил Джон Харрис, изящно доказав, что ^-прямоугольники размеров Зх8и4х6не могут быть составлены из существующих тетраболо, и найдя решения для двух Л-прямоугольников 2 х 6 и 3 х 4.

h.-l„ .1