Головоломок вишенка в коктейле
| Вид материала | Документы |
- Психологическое сопровождение замещающих семей, 219.46kb.
- Психологическая коррекция агрессивного поведения детей, 219.57kb.
- С. В. Левина Н. А. Задворочнова публичный доклад, 193.66kb.
- Проектный метод в деятельности доу, 187.91kb.
- Проектный метод в деятельности доу, 214.46kb.
- Альтергот Оксана Петровна. Детский сад является юридическим лицом, имеет полный пакет, 211.9kb.
Цветные треугольники и кубики
В 1967 году Франц О. Армбрастер, программист из Калифорнии, придумал новую модификацию головоломки, которая продавалась в разнообразных видах на протяжении уже более полувека. Он снабдил её краткой понятной инструкцией и дал название «Мгновенное помешательство» (Instant Insanity). Она имела поистине мгновенный успех. Распространением головоломки занялась компания Parker Brothers, и продажи в 1968 году достигли невероятного уровня. Головоломка состояла всего лишь из четырёх пластмассовых кубиков одинакового размера, с гранями, выкрашенными в четыре разных цвета. Цель головоломки — поставить кубики в ряд так, чтобы на каждой из сторон ряда были видны все четыре цвета.
^ Я уже упоминал об этой головоломке в главе «24 цветных квадрата и 30 цветных кубиков» книги New Mathematical Diversions from Scientific American (1966), но наиболее полный её анализ можно найти в главе 7 книги Puzzles and Paradoxes (1965) Томаса О'Бирна. Он подсчитал вероятность случайного совпадения головоломки Арм-брастера — она составила 1 к 41 472! Томас пишет, что наиболее привлекательная черта этой головоломки в том, что её «можно вытаскивать на свет божий снова и снова, внося самые мелкие изменения, в то время как множество других неплохих головоломок, появившись раз, так и исчезают навсегда либо, в лучшем случае, остаются известными лишь узкому кругу любителей».
«Мгновенное помешательство» можно отнести к тому обширному классу комбинаторных задач, в которых требуется собрать в определённом порядке многогранники или многоугольники со сторонами или гранями, различающимися по цвету или как-то иначе. Один из первопроходцев комбинаторной математики, майор Перси Александр Макмахон, скончавшийся в 1929 году, уделял таким головоломкам много внимания. Макмахон, профессор физико-математических наук, написал классический двухтомный труд Combinatory Analysis («Комбинаторный анализ»), 1915 и 1916 годов издания, и замечательную вводную статью об этом же предмете для одиннадцатого издания «Британники». Но помимо этого его перу принадлежит малоизвестный и ставший библиографической редкостью труд New Mathematical Pastimes («Новые математические игры») 1921 года, в котором он исследует разнообразные головоломки, относящиеся к тому же общему типу.
Рассматривая в своей книге 30 цветных кубиков (Макмахон также обсуждает их в своих «Новых математических играх»), я говорю и о 24 цветных квадратах Макмахона. Здесь же я познакомлю вас с другим набором фигур Макмахона — с 24 цветными треугольниками. Если три стороны равностороннего треугольника покрашены каждая в один из двух цветов и повороты треугольников не считаются отдельными вариантами фигур, то вы получаете четыре разных треугольника. С помощью трёх цветов можно получить 11 треугольников, с помощью четырёх — 24, которые изображены на рис. 108. Для работы с такими картонными фигурками удобно разделить каждую из них на три равные равнобедренные части, как показано на рисунке, а затем закрасить каждую из третей одним из четырёх цветов, в соответствии с приведенной здесь разметкой. Так как вам не потребуется переворачивать треугольники (в набор уже входят «зеркальные» пары), то раскрашивать их нужно только с одной стороны.
^ При наличии п цветов число разных равносторонних треугольников, получающихся таким путем, равно
пъ+2п 3 '
При п = 3 получающийся набор из 11 треугольников не представляет никакого интереса, так как из такого малого числа нельзя сложить никаких интересных фигур. При п = 5 получается 45 треугольников — это многовато для развлекательных целей. А набор из 24 треугольников с четырьмя разными цветами — именно то, что нужно. Более того, именно из такого набора можно сложить не только правильный шестиугольник, но и невероятное множество разнообраз
ных симметричных фигур. Макмахон предлагает большое число комбинаторных задач, основанных на этом наборе. Самая простая — складывать треугольники подобно домино, чтобы стороны одинакового цвета соприкасались, и в результате получались бы правильные многоугольники. Затем он добавляет ещё одно ограничение: весь многоугольник должен быть ограничен линиями одного цвета. (Далее мы будем говорить об этих ограничениях как о двух условиях Макмахона.) В наборе треугольников каждый цвет присутствует на 18 сторонах (четное число), а по условиям Макмахона требуется, чтобы внутри многоугольника каждый цвет появлялся на четном числе сторон одиночных треугольников. Отсюда следует, что периметр любой фигуры, составленной из таких треугольников с выполнением условий, должен состоять из четного числа сторон треугольников.
Уэйд Э. Филпотт, инженер на пенсии из Лимы в штате Огайо, проделал с набором треугольников Макмахона большую работу, чем кто-либо другой из известных мне людей. Все нижеизложенное взято из нашей с ним переписки и публикуется с его любезного разрешения.
Нетрудно доказать, что все многоугольники, составленные из 24 цветных треугольников, отвечающие условиям Макмахона, должны иметь периметр в 12, 14 или 16 сторон треугольников. Как мы уже выяснили, это число обязано быть четным. Минимальный пери-
метр многоугольника, составленного из 24 треугольников с одиночной стороной, равен 12. Периметр в 18 единиц невозможен, так как в наборе содержится всего 18 сторон каждого цвета, а все три стороны одного треугольника не могут входить в периметр многоугольника. Таким образом, максимальный периметр многоугольника, отвечающего всем условиям, равен 16.
Минимальным периметром в 12 единиц обладает единственный из многоугольников, правильный шестиугольник. Его одноцветная сторона может быть составлена шестью различными способами, каждый из которых, в свою очередь, предполагает неизвестное число отдельных решений. Филпотт оценивает полное число решений в несколько тысяч (при этом не включая в них варианты поворотов и отражений фигуры, а также решения, полученные лишь перестановкой цветов). Филпотт установил, что для каждого типа границы шестиугольника существует три варианта расстановки трёх однотонных треугольников (обязательно отличных по цвету от границы шестиугольника), которые симметрично размещаются вокруг центра шестиугольника. Так как каждый однотонный треугольник должен быть окружен треугольными сегментами такого же цвета, в итоге получается шесть однотонных правильных шестиугольников меньшего размера, симметрично помещенных внутри границ большого. На рис. 109 показан принцип получения одноцветной границы шестиугольника шестью различными вариантами расположения
Рис. 110.
Примеры каждого типа параллелограмма 3x.4с границей одного цвета
Рис. 111.
18 симметричных многоугольников с периметром 14 единиц
в центре одного из двух возможных однотонных треугольников. Вы сами можете попробовать составить шестиугольник, применяя любой из шести вариантов.
Из 24 треугольников можно получить параллелограммы со сторонами 2 х 6 и 3 х 4. Легко доказать, что параллелограмм со сторонами 2 х 6 не отвечает двум условиям Макмахона: из 14 треугольников, формирующих периметр параллелограмма, только 13 имеют один и тот же цвет. Параллелограмм 3x4 возможен. И здесь точное число решений неизвестно, хотя Филпотт предполагает, что их меньше, чем для правильного шестиугольника. Так же как и у шестиугольника, здесь возможны шесть способов составления границ фигуры. На рис. 110 приведены предложенные Филпоттом решения для каждого способа, в каждом из которых присутствует 3 однотонных треугольника (обязательно отличающихся по цвету от границ параллелограмма), поставленных в ряд.
Параллелограмм со сторонами 3x4 представляет собой пример симметричной фигуры, периметр которой равен 14 единицам. Филпотт нашел ещё 18 симметричных многоугольников с тем же периметром, отвечающих условиям Макмахона. Они изображены на рис. 111. Для всех этих фигур возможно более чем одно решение. Легко догадаться, что условием существования фигуры с периметром 14 должно быть хотя бы одно «острие» (угол в 60°). Ведь хотя бы один треугольник с двумя одинаковыми по цвету сторонами должен
занимать положение, когда обе эти стороны входят в периметр многоугольника. Обратите внимание на то, что лишь у одной из 18 предложенных фигур «острие» единственное. Эта фигура (под номером 1) также относится к набору 11 симметричных фигур с периметром 14 или 16, составить которые возможно лишь единственным способом. Примечательна также фигура под номером 5.
Согласно Филпотгу, это единственная симметричная фигура, имеющая 11 различных типов одноцветной границы (максимально возможное число). Известны примеры решений всех 11 типов.
Филпотт нашел 42 возможные симметричные фигуры с периметрами 16 (см. рис. 112), так что всего известно 62 симметричных многоугольника, имеющих решения для данных условий. Филпотт пишет, что у каждого из этих многоугольников с периметром 16 должно быть не меньше чем три «острия», но не больше четырёх. Не все симметричные фигуры с тремя остриями имеют решения, однако все с четырьмя остриями решения имеют.
Предложенная Филпоттом «задача на удвоение» заключается в составлении двух одинаковых симметричных фигур по 12 треугольников в каждой, которые отвечали бы условиям Макмахона и имели бы одноцветные границы, отличающиеся по цвету между собой. На рис. 113 показан один из 28 способов решения этой задачи. Филпотт считает, что для каждой из фигур возможны сотни, но не тысяч, вариантов решения.
^ Также придуманная Филпоттом «задача на утроение» заключается в построении трёх одинаковых фигур из восьми треугольников, каждая с границами трёх разных цветов.
Филпотт сообщает, что таких фигур может быть только 10. Они показаны на рис. 114 с решением для одной из них. Филпотт оценивает число решений для каждого варианта не более 100.
Из шести треугольников можно составить двенадцать различных фигур, которые названы гексамондами. Их я представил в своей
книге Sixth Book of Mathematical Games from Scientific American («Шестая книга математических игр от Scientific American*). Все гексамон-ды, за исключением «бабочки», как обнаружил Филпотт, могут быть учетверены.
Джон Харрис из Санта-Барбары, Калифорния, предложил задачу на составление шестиугольников с минимальным или максимальным числом отдельных «кристаллов». («Кристалл» получается из двух элементов, соединенных по сторонам, имеющим одинаковый цвет.) Легко показать, что в любой фигуре должен быть хотя бы один алмаз, но при этом не более 9. Для обоих случаев существует решение, и не одно. Харрис обнаружил, что в параллелограмме 3x4 могут содержаться девять «кристаллов», причем вариантов решения много. При этом параллелограмм можно составить и без «кристаллов», причем также различными способами.
Из какого полного набора треугольников Макмахона можно составить равносторонний треугольник, отвечающий двум цветовым ограничениям? Прежде чем дать ответ, мы должны определить, из каких наборов можно составить равносторонний треугольник, не учитывая ограничений. Пусть число цветов в наборе равно я, а число отдельных структурных единиц — т2. Сложить из набора равносторонний треугольник возможно только для я, удовлетворяющих следующему диофантовому уравнению:
п(п2+2) 2
— - = т .
3
Сколько целочисленных решений имеет это уравнение? Филпотт предложил такую задачку в Journal of Recreational Mathematics, вып. 4, апрель 1971. Некоторые частные решения были опубликованы в вып. 5, январь 1972. Общее число решений конечно, и самые маленькие из них — это п = 1, 2 и 24. При этом все остальные значения п превосходят 5000.
Совершенно очевидно, что единственный треугольник (я = 1) удовлетворяет обоим цветовым условиям. При п = 2 ясно, что полный набор т2 = 4 не удовлетворяет условию о границе. При п = 24 из т2 = 4624 элементарных треугольников получается равносторонний треугольник со стороной в 68 единиц. Отвечает ли эта фигура обоим условиям? Пока это никем не доказано, хотя и вполне возможно.
Житель Манчестера Джордж Литтлвуд доказал, что треугольники, составляющие полный макмахонов набор, складываются в правильный шестиугольник лишь при п = 4. Это следует из того, что уравнение
3
имеет целочисленное решение только для п = 4. Как мы уже видели, сложить такие шестиугольники, отвечающие обоим цветовым ограничениям, возможно. Не учитывая повороты, отражения и перестановки цветов, сколько таких шестиугольников существует? Пока это не выяснено. Филпотт считает, что это число достигает нескольких тысяч.
Набор из 45 «пятицветных» треугольничков (правда, вместо разных цветов их стороны были помечены разным числом точек) был выпущен в Германии в конце шестидесятых. Он носил название «Тримино». В прилагаемом буклете, написанном Хайнцем Ха-бером, предлагались различные симметричные фигуры, которые можно складывать из набора, и варианты игр с их использованием для нескольких человек. Понятно, что частью этого набора был набор из 24 «четырёхцветных» треугольничков. Такой же набор производства Гонконга продавался в США под названием «Трёхмерное домино». Время от времени в продаже появлялись и наборы из 24 деталей. Но первый, существование которого мне удалось задокументировать, был выпущен лондонской фирмой Just Games, Ltd. в 1975 году.
В 1892 году Макмахон получил британский патент под номером 3297 на свой набор из 24 треугольников, но мне неизвестно, продвигал ли он его на рынок. В США патент на набор из четырёхцветных треугольников был выдан в 1985 году Ф.Х. Ричардсу из города Троя в штате Нью-Йорк. Однако Ричарде описывал его использование лишь в качестве набора для игр типа домино. В США в продаже появлялись разнообразные игры такого типа с цветными треугольниками, из которых стоит отметить наиболее известные: «Contack» фирмы Parker Brothers, выпущенный впервые в 1939 году, и «А1-1о-со» производства одной кливлендской фирмы 1964 года.
Можно заменить разноцветные стороны у треугольников кривыми различной формы. Этот вариант превращения треугольников в подобие паззла был предложен самим Макмахоном (см. рис. 115).
Макмахон в своей книге не рассматривает принципиально другой вариант окраски — не сторон, а углов треугольников. Число таких треугольников для п цветов будет таким же, как и у треугольников с разноцветными сторонами. Можно ли составить из таких треугольников с разноцветными углами (24 треугольника, 4 цвета) шестиугольник, который бы удовлетворял единственному условию: чтобы углы одинакового цвета составляли каждую его вершину? К несчастью, это невозможно. Точно так же невозможно и сложить из них равносторонний треугольник с симметрично расположенной треугольной «дыркой». Хотя если пустое место будет расположено в одном из углов или в середине стороны, то такая фигура возможна. Но из такого набора можно сложить параллелограмм 3 х 4 и много других симметричных фигур.
В 1969 году парижанин Марк Одье придумал очередной вариант игры, состоящей из 24 четырёхцветных треугольников, закрашенных по углам. Эта игра выпускалась и продавалась во Франции под названием Trioker, Она имеет британский патент номер 1 219 551. К набору прилагается перечень задач на составление различных фигур и правила для игр.
В наборе была и 25-я фигурка, окрашенная в два цвета, — так называемый джокер, который можно было использовать и для построений, и для игр. Позднее эта игра продавалась и в Испании. В 1976 году во Франции вышла книга Одье и И. Русселя Surprenants Triangles, к которой прилагался этот набор. В США аналогичная игра под названием Tri-ominoes производства компании Pressman была выпущена в свет в 1968 году.
Среди объемных фигур заполнить пространство без промежутков можно только кубами. Именно благодаря этому свойству кубики входили в наборы разнообразных головоломок типа «Мгновенного помешательства». Если вы подберете 27 одинаковых кубиков и покрасите 9 из них в один цвет, 9 — в другой и 9 — в третий (со всех сторон), то можете попробовать решить две необычные пространственные задачки.
Сразу понятно, что невозможно сложить из 27 кубиков большой куб размерами 3x3x3 так, чтобы каждый из 27 ортогональных рядов (параллельных ребрам большого куба) состоял из элементов одного и того же цвета. А можно ли сложить такой большой куб, чтобы в каждом из 27 ортогональных рядов присутствовали все три цвета? Оказывается, можно. Единственное решение этой задачи (повороты, отражения и перестановки цветов не учитываются) было найдено Чарлзом Триггом, математиком на пенсии из Калифорнии. Получится ли у вас «переоткрыть» это решение?
Вторая задача гораздо сложнее. Её не так давно придумал кембриджский математик Джон Хортон Конвей. Он поставил перед собой задачу сложить большой куб таким образом, чтобы ни в одном из тройных рядов (27 ортогональных, 18 диагональных в плоскостях сечения большого куба и 4 пространственных диагонали, соединяющих противоположные углы) не содержалось ни по три кубика одинакового цвета, ни по три разноцветных. Иными словами, в каждом из 49 рядов из трёх кубиков должны были быть два кубика одного цвета и один -другого. Конвею удалось найти два разных, но родственных решения (снова не считая поворотов, отражений и перестановок цветов).
Конечно, вы можете решать обе эти задачи, нарисовав в качестве отображения трёх уровней большого куба три поля для игры в «крестики-нолики» и пронумеровав все клетки в них буквами А, Б, В, соответствующими разным цветам кубиков. Однако и легче, и
интереснее работать с настоящими кубиками, так что я советую вам потратить немного времени на их добывание и окраску.
ОТВЕТЫ
На рис. 116 показан один из способов построения шестиугольника из 24 цветных треугольников для всех шести вариантов одноцветной границы с учетом дополнительного условия, что три однотонных треугольника вокруг центра фигуры располагались бы симметрично в показанном порядке. Сколько всего решений существует для каждого из шести типов, неизвестно.
На рис. 117 приводится единственное решение (не считая поворотов, отражений и перестановки цветов) для построения из 27 единичных кубиков большого куба 3x3x3 (единичные кубики окрашены по 9 в три разных цвета, и в каждом ортогональном ряду присутствует по одному кубику каждого цвета).
^ Это решение было опубликовано Чарлзом Триггом в журнале Mathematics Magazine в январе 1966 года.
На рис. 118 показаны два способа расположения того же набора из 27 кубиков, составляющих большой куб 3 х 3 х 3, в котором ни один из рядов из трёх кубиков (ортогональных и диагональных, в т. ч. четырёх пространственных диагоналей куба) не содержит ни трёх одинаковых по цвету кубиков, ни трёх разных. Это единственные варианты решения данной задачи, найденные Джоном Хортоном Конвеем.
Рис. 117.
Решение первой задачи о кубе
