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

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

Документы

Содержание Ещё одна увлекательная задача - определение кратчайшей игры, которая может быть сыграна на доске 13 х 13 или меньшей. (При О своем великолепном результате Кларнер рассказывает в пись­ме, датированном 1974 годом I ООО развивающих головоломок... Scientific American На доске 5x5 первый игрок имеет очевидный шанс выиграть, положив l-пентамино в центр доски, как показано на рис. 82Ь. Можно ли сложить из Y-пентамино прямоугольник Спрямляемых гептамино, кроме этого, известно лишь четыре. Их стандартное кратчайшее решение продемонстрировано на рис. 84.

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

• Психологическое сопровождение замещающих семей, 219.46kb.
• Психологическая коррекция агрессивного поведения детей, 219.57kb.
• С. В. Левина Н. А. Задворочнова публичный доклад, 193.66kb.
• Проектный метод в деятельности доу, 187.91kb.
• Проектный метод в деятельности доу, 214.46kb.
• Альтергот Оксана Петровна. Детский сад является юридическим лицом, имеет полный пакет, 211.9kb.

ГЛАВА 13


Полиомино и спрямление


Всеобщий интерес к полиомино был порожден книгой Соломона В. Голомба Polyominoes («Полиомино»). Полиомино — это многогран­ник, образованный соединенными по граням единичными квадра­тами. В свою очередь, популярность полиомино подтолкнула Го­ломба, преподававшего электроинженерию и математику в универ­ситете Южной Калифорнии, уделить больше свободного времени изучению некоторых темных углов данной области. В своих пись­мах он постоянно ставил занимательнейшие задачи, имевшие отно­шение к игре в пентамино, которую изобрел много лет назад.

На рис. 74 показаны 12 возможных пентамино (полиомино, со­стоящих из пяти квадратов) с названиями, данными им Голомбом. Чтобы сыграть в стандартную игру в пентамино, вам понадобятся эти 12 фигур, вырезанных из картона, и стандартная доска для ша­шек 8x8 клеток, которые должны быть такого же размера, что и квадраты, из которых состоят ваши пентамино. Если вы ещё никог­да не играли в такую игру, вам лучше приготовить набор пентами­но и заранее потренироваться с ним. Эта игра — одна из самых не­обычных математических настольных игр, появившихся в послед­ние годы.

Играют в неё вдвоем. Игроки садятся за доску и кладут рядом на­бор пентамино. Первый игрок берет любую фигуру и кладет её на любые пять клеток доски. Второй кладет на доску вторую фигуру, и так далее, пока кто-то из игроков окажется не способен сделать ход — либо потому, что ни один из оставшихся пентамино не подходит к оставшимся свободным клеткам, либо потому, что больше не оста-

_{*ЧТ f F V I}

NT F Р VI

_{У *Luwl}

Y X L U W Z


Рис. 74.

12 пентамино


лось не выложенных на доску фигур. Этот игрок считается проиг­равшим. Конечно, запрещается пользоваться какими-либо наброс­ками. Партии в эту игру обычно скоротечны. Для успешной игры необходимо мастерство и воображение. Математики пока абсолют­но не имеют понятия, кто из игроков должен выигрывать при усло­вии безошибочной игры. «Полный анализ этой игры, — пишет Го­ломб, — представляет собой задачу, приближающуюся по своей сложности к пределам возможностей быстродействующего ком­пьютера при условии наличия существенного запаса времени и крайне сложной программы». Голомб объясняет, что наиболее ус­пешная стратегия для этой игры — постараться разделить доску на отдельные равные участки. В этом случае весьма вероятно, что на каждый ход вашего противника, сделанный на одном участке дос­ки, вы сможете ответить ходом на другом участке. Если игра будет продолжаться в таком же духе, последний ход останется за вами.

Голомб разработал типичный пример, в котором оба игрока ста­раются придерживаться этой стратегии. Он показана на рис. 75. Иг­рок А кладет фигуру рядом с центром доски, чтобы не дать своему противнику разделить её. Игрок Б в ответ кладет фигуру Uвплотную к А^ход 2). Голомб замечает, что это хороший ход, так как он «не уп­рощает ситуацию для противника и не позволяет ему разделить до­ску». Игрок А теперь также старается перехитрить противника. Он кладет фигуру L (ход 3) так, чтобы препятствовать разделению дос­ки. Четвертый ход, который делает игрок Б, неудачен, так как он позволяет игроку А положить фигуру W (ход 5) таким образом, что



Рис. 75.


она делит доску на два равных участка по 16 клеток в каждом. В дан­ном случае эти участки равны не только по размеру, но и по форме.

Теперь игрок Б кладет фигуру / (ход 6), надеясь, что противник не найдет фигуры, соответствующей другому свободному участку. Однако А оказывается способен положить фигуру Р так, что в ре­зультате выигрывает. Все три оставшиеся свободными участка до­статочно велики для того, чтобы вместить фигуру. Однако те, что могли бы подойти — I, ссылка скрыта, — уже были использованы.

Наиболее интересный вариант стандартной игры, продолжает Голомб, это игра с предварительным выбором пентамино. В этом случае игроки выбирают фигуры не перед каждым ходом, а зара­нее, перед началом игры, по очереди. Тот, кто последним берет фи­гуру, ходит первым. Игра продолжается как обычно, за исключе­нием того, что игрок может выкладывать на доску только свои фи­гуры. В этом случае стратегия игры совершенно иная. Вместо того чтобы пытаться разделить доску, добившись того, чтобы осталось четное число ходов, игрок старается обеспечить как можно больше возможностей для размещения своих фигур и одновременно ли­шить противника места на доске, подходящего для его фигур. Это осуществляется созданием «убежищ», как назвал их Голомб, — участков доски, которым соответствуют только собственные фигу­ры игрока.

Партия этого типа изображена на рис. 76. Голомб комментирует её следующим образом. Игрок А избавляется от фигуры X, самой не­удобной из имеющихся у него, делая первый ход, как показано на рисунке. (Фигуры, выбранные каждым из игроков, перечислены сбоку от доски; после использования они вычеркиваются.) Игрок Б в свою очередь выкладывает свой «неудобный» вариант — фигуру W

(ход 2). Теперь А ходит фигурой F (ход 3), чтобы создать убежище для своего Y. Игрок Б при помощи фигуры L отгораживает убежище для U (ход 4). Ход 5 — игрок А кладет фигуру N. Б кладет фигуру / (ход 6) так, чтобы получившийся треугольник 2x3 соответствовал бы только двум из оставшихся фигур — Р и U. Затем игрок А кладет фигуру К (ход 7), но сдается, так как понимает, что дальше игра пой­дет именно так, как показано на рисунке (ход 8). Игроки по очере­ди заполняли бы свои убежища, и в итоге А остался с фигурой Г, ко­торая никуда не подходит.

Если мастерство игроков не одинаково, Голомб предлагает дать более слабому игроку фору, позволив ему первым выбирать фигуру и ходить последним. Можно пойти и ещё дальше, дав более слабому игроку возможность выбрать первым 2 или даже 3 фигуры и также ходить последним.

Существуют и другие занятные варианты этой игры. В игре «со сдачей» названия или очертания фигур изображаются на карточках, которые перемешиваются и сдаются игрокам, как при игре в карты. Каждый игрок забирает себе те фигуры, которым соответствуют оказавшиеся у него карточки, и далее игра идет так же, как описано выше. Можно играть парами, вчетвером, тогда игроки, сидящие друг напротив друга, играют «командой». Проигрывает та команда, один из игроков которой оказывается не способен сделать ход. Так можно играть в любой из описанных вариантов — обычный, с пред­варительным выбором или со сдачей карт. Можно также играть втроем или большим числом человек, но так, чтобы каждый был за себя. В этом случае выигрывает тот игрок, кто сумеет сделать ход последним. Он получает за игру 10 очков. Тот, кто первым оказался не способен ходить, не получает ничего, а остальные игроки — по 5.

Взяв за основу стандартную игру в пентамино, Голомб предло­жил и ряд новых задач на квадратной доске необычного размера. Чтобы возможно было сделать ход, доска должна иметь размеры не менее чем 3x3 клетки. Но на такой доске тот, кто первым сделает ход, сразу же выиграет, так как положить на неё вторую фигуру бу­дет уже невозможно. На доске размером 4x4 всегда выигрывает тот, кто ходит вторым. Голомб рассмотрел все возможные варианты первого хода на такой доске — не считая размещения фигур в зер­кальном отображении и перевернутом виде — и соответствующие ответные ходы, приносящие победу (рис. 77). Во всех случаях, кро­ме одного, у второго игрока имеется выбор варианта хода. Насколь­ко быстро вам удастся найти вариант развития партии, при кото­

в














n= 11 8 ходов

п= 12 10 ходов

^ I ООО развивающих головоломок...

ДОПОЛНЕНИЕ

Впервые я рассказал о голомбовской игре в пентамино на страни­цах ^ Scientific American в ноябре 1957 г. С тех пор в продаже появи­лись две «пиратские» версии игры. Первая, выпущенная фирмой Philips Publishers в 1960 году, носила название Pan-Kai и состояла из доски размером 10 х 10 клеток и двух наборов по 12 пентамино (для двух игроков). В 1967 году появилась игра фирмы Parker Brothers Universe («Вселенная»). Игровое поле имело форму широкого крес­та, а к нему прилагалось четыре набора пентамино, чтобы можно было играть не только вдвоем, но и втроем, и вчетвером. Точно так же, как и в правилах Pan-Kai, в инструкции ко «Вселенной» огова­ривалось, что игрок не имеет права класть свою фигуру так, чтобы образовывался замкнутый участок поля величиной менее чем в пять клеток. На коробке с игрой была изображена сцена из фильма «2001: Космическая одиссея», где астронавты играют на борту сво­его корабля в аналогичную компьютерную игру. Однако при выхо­де фильма на экраны эту сцену заменили на игру в компьютерные шахматы.

Первая авторская версия этой игры с буклетом, написанным са­мим Голомбом, появилась в 1973 году. Её выпустила компания Hallmark Cards. Случилось же это ровно через двадцать лет после то­го, как Голомб впервые представил полиомино ученым-математи­кам на незабываемой встрече Гарвардского математического клуба.


ОТВЕТЫ

В первой задаче требовалось найти единственный среди 33 вариан­тов игр-двухходовок с пентамино на доске 4x4 вариант, где у вто­рого игрока имеется лишь одна возможность выиграть. Это вариант игры под номером 26, который ещё раз показан на рис. 82а. Первый игрок оставляет справа пространство, которое можно заполнить только L-пентамино. Однако, если поместить на это место эту фи­гуру, первый игрок сможет выиграть, заполнив левую часть доски. С другой стороны, если второй игрок положит слева любую фигуру, кроме L, то первый игрок сможет выиграть, положив L-пентамино справа. Значит, чтобы выиграть, второй игрок должен положить L-пентамино в левую часть доски, как показано на рисунке.

^ На доске 5x5 первый игрок имеет очевидный шанс выиграть, положив l-пентамино в центр доски, как показано на рис. 82Ь.


182



ABC



D Е F


После этого противник должен будет пойти своей фигурой с од­ной из сторон, и тогда первый игрок выигрывает, занимая другую сторону доски. Самая короткая возможная партия на такой доске — в два хода (рис. 82с), а самая длинная — в пять ходов (рис. 82d). Ва­риант самой короткой игры — единственный, в то время как длин­ную можно играть по-разному.

На доске 5x6 первый игрок может выиграть, если сделает такой первый ход, какой показан на рис. 82е. Доказательство этого до­вольно сложно, и недостаток места не позволяет мне продемонст­рировать ответные ходы, следующие за всеми возможными вариан­тами хода второго игрока. Существует по меньшей мере ещё три возможности сделать выигрышный первый ход.

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

^ Можно ли сложить из Y-пентамино прямоугольник с нечетной площадью? Оказывается, можно, и самый маленький из таких пря­моугольников будет представлять собой квадрат со стороной в 15 клеток. Решение найдено Дженифер Хэзельгров, кибернетиком из университета Глазго. Это исключительно сложная задача, ответ на которую я здесь приводить не стану.

Вариант спрямления гептамино, изображенного на рис. 80 внизу, приведен на рис. 83. Этот вариант предложен Джеймсом Э. Стюар­том. Однако это не единственное решение, так как четыре централь­ных гептамино можно сложить по-разному, а каждая из закрашенных пар может быть отображена зеркально. Обратите внимание на заме­чательную четырёхстороннюю симметрию этой составной фигуры.

^ Спрямляемых гептамино, кроме этого, известно лишь четыре. Их стандартное кратчайшее решение продемонстрировано на рис. 84.