Текст книги "Математические головоломки и развлечения"

Автор книги: Мартин Гарднер

сообщить о нарушении

Текущая страница: 5 (всего у книги 30 страниц)

Глава 8. ИГРА В ГЕКС

В наши дни редко кому удается придумать математическую игру, которая была бы одновременно и новой и интересной. Именно такой оригинальной и увлекательной является игра в гекс, впервые появившаяся в пятидесятые годы в Институте теоретической физики Нильса Бора в Копенгагене. Гекс вполне может стать одной из наиболее популярных и наиболее полно исследованных математических игр нашего века.

В гекс играют на доске, имеющей форму ромба, составленного из шестиугольников (рис. 33).

Рис. 33 Игра в гекс на доске со стороной из 11 шестиугольников. Черные выиграли.

Число шестиугольников может быть разным, но обычно предпочитают играть на доске, вдоль стороны которой укладывается одиннадцать шестиугольников. Две противоположные стороны ромба называются «черными», две другие – «белыми». Шестиугольники, находящиеся в углах ромба, относятся к обеим сторонам. Один игрок играет черными фишками, второй – белыми. Играющие по очереди ставят фишку на любой шестиугольник, еще не занятый другой фишкой. Цель «черных» состоит в том, чтобы построить цепь из черных фишек между двумя «черными» сторонами. «Белые» стремятся построить цепь из белых фишек между «белыми» сторонами.

Цепь может как угодно изгибаться, поворачивать. Фишки ставят до тех пор, пока кто-нибудь из игроков не выстроит свою цепь.

На рис. 33, например, видно, как победили «черные».

Игра никогда не кончается вничью, потому что один из участников может запереть другого, только построив свою цепь. Хотя правила гекса очень просты, тем не менее он оказывается удивительно тонкой математической игрой.

Придумал гекс датчанин Пит Хейн. В молодости Хейн провел несколько лет в Институте теоретической физики, а затем, сделав несколько технических изобретений, стал работать в промышленности. Так продолжалось до 1940 года, до вторжения немцев в Данию. Во время оккупации Хейн дважды уходил в подполье – он был председателем антинацистского демократического союза, распущенного с приходом нацистов. Именно во время оккупации он начал писать свои знаменитые эпиграммы под псевдонимом Кумбель.

[Три выпуска этих эпиграмм (Хейн назвал их «груками») изданы на английском языке под истинной фамилией автора: Нет Р. Grouks. I, II, III. – Copenhagen: 1966–1970. Некоторые эпиграммы Хейна были напечатаны на страницах журнала «Наука и жизнь» на русском языке. Вот одна из них, которая могла бы послужить эпиграфом к этой книге:

 
В задачах тех
Ищи удачи,
Где получить
Рискуешь сдачи.]
 

Они печатались в датской газете «Политикен», для которой Хейн одно время писал очерки и стихи, подписываясь своим настоящим именем. В одной только Дании, где население немногим больше четырех миллионов, было продано около четверти миллиона экземпляров сборника его стихов.

Идея игры в гекс пришла Хейну в голову, когда он размышлял над знаменитой топологической проблемой четырех красок. Эта проблема до сих пор не решена. Формулируется она следующим образом. Требуется доказать или опровергнуть утверждение: «Всякую карту можно раскрасить четырьмя красками так, что никакие две области, имеющие один и тот же цвет, не будут иметь общей границы». Хейн рассказал о придуманной им игре во время лекции.

Это было в 1942 году. Вскоре правила игры были опубликованы в газете «Политикен» и гекс стал необычайно популярен в Дании под названием «Многоугольники». Появились в продаже блокноты для игры с заранее напечатанными изображениями досок. «Политикен» из месяца в месяц публиковала задачи и премировала лучшие решения. Игра получила свое нынешнее название гекс лишь в 1952 году, после того как была выпущена фирмой «Паркер».

В 1948 году Джон Нэш, в то время аспирант-математик Принстонского университета, а позже один из самых выдающихся специалистов по теории игр в США, изобрел ту же игру независимо от Хейна. Она быстро увлекла математиков в Принстоне и в Институте высших исследований. Игра обычно называлась «Нэш» или «Ванная». Последнее название в основном было обязано тому, что студенты часто играли на шестиугольных плитках в ванных комнатах.

Читателям, которым захочется поиграть в гекс, следует заранее заготовить листки с начерченными на них досками. Ходы можно отмечать крестиками и кружками. Если вам больше нравится передвигать фишки на «настоящей» доске, можно нарисовать большую доску на листе толстого картона или сложить ее из шестиугольных керамических плиток. Если плитки достаточно большие, то играть можно обычными шашками.

Чтобы понять все тонкости игры в гекс, лучше воспользоваться игровым полем, состоящим из небольшого числа шестиугольников.

На доске 2x2 (четыре шестиугольника) всегда выигрывает тот, кто делает первый ход. На доске 3x3 легко выиграть, если первый ход сделать в центр доски (рис. 34).

Рис. 34

«Черные» могут пойти двумя разными способами, заняв любой из двух шестиугольников, расположенных по обе стороны от центра, и поэтому на третьем ходу обязательно выигрывают.

На доске 4x4 все гораздо сложнее. Начинающий игру выигрывает наверняка лишь в том случае, если он сразу же занимает одну из четырех пронумерованных клеток (рис. 35).

Рис. 35

Сделав первый ход на любую другую клетку, он непременно проиграет. Начав игру с клеток 2 или 3, первый игрок одержит победу на пятом ходу; начав с клеток 1 или 4 – на шестом.

Для доски 5x5 еще можно доказать, что если первый игрок сразу же занимает центральную клетку, то он может выиграть на седьмом ходу. Для досок большего размера анализ становится слишком сложным. Стандартная доска 11 х 11 таит в себе астрономическое число усложнений, и полный анализ игры в гекс на такой доске находится за пределами человеческих возможностей.

Специалисты по теории игр считают гекс особенно интересной игрой по следующей причине. Для игры на стандартной доске не известно, какой тактики необходимо придерживаться, чтобы наверняка обеспечить победу. Однако доказательством от противного можно довольно изящно показать, что для первого игрока всегда существует выигрышная стратегия на доске любого размера! (Доказательство существования обычно позволяет утверждать, что некий объект существует, но не дает никаких указаний, как его найти или построить.) Мы приведем лишь очень краткий набросок доказательства (его можно провести значительно более строго) в том виде, в каком его дал в 1949 году Джон Нэш.

1. Либо первый, либо второй игрок должен выиграть, поэтому либо для первого, либо для второго должна существовать выигрышная стратегия.

2. Предположим, что для второго игрока существует выигрышная стратегия.

3. Тогда первый игрок может обороняться следующим образом.

Сделав произвольный первый ход, он действует затем в соответствии с выигрышной стратегией второго игрока, описанной выше.

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

4. Лишняя фишка не может затруднить выигрыш первого игрока, потому что лишняя фишка – это всегда преимущество, а не помеха. Таким образом, первый игрок может выиграть.

5. Предположение о существовании выигрышной стратегии для второго игрока приводит к противоречию, и потому его нужно отбросить.

6. Следовательно, выигрышная стратегия может существовать лишь для первого игрока.

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

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

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

Они изображены на рис. 36.

Рис. 36 Три задачи из игры в гекс.

Вопрос для всех трех задач один и тот же: найти такой первый ход, который обеспечивает «белым» победу.

* * *

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

Предлагались и другие, неромбические формы доски для гекса.

Например, создатель теории информации. К. Шеннон предложил игровое поле в форме равностороннего треугольника. Выигрывает тот, кто первым построит цепь, соединяющую все три стороны треугольника. Угловые клетки считаются принадлежащими обеим сторонам угла. Нэш доказал, что побеждает первый игрок. Метод доказательства без труда переносится и на случай треугольного игрового поля. (Здесь также выигрывает тот, кто начинает.)

Несколько предложений было внесено с целью уменьшить слишком сильное преимущество первого игрока. Так, первого игрока можно лишить права начинать с короткой диагонали. Решая, кому принадлежит победа, можно учитывать сделанное выигравшим число ходов. Открывая игру, первому игроку разрешается делать лишь один ход, после чего каждый из игроков по очереди делает по два хода за один раз.

Напрашивается предположение, что если на доске размером n х (n + 1) – например 10 х 11 – начинающий игру берет себе более удаленные друг от друга стороны, то относительные преимущества игроков должны уравниваться. К сожалению, обнаружилась очень простая стратегия, с помощью которой второй игрок наверняка одерживает победу. Эта стратегия основана на зеркальной симметрии относительно центральной оси. Если второй игрок – это вы, то представьте себе, что все клетки разбиты на пары так, как показано на рис. 37.

Рис. 37 Как должен расставить свои фишки второй игрок на «укороченной» доске, чтобы выиграть партию в гекс.

Куда бы ни сделал ход противник, вы делаете ход на вторую клетку, обозначенную той же буквой, что и занятая им клетка. Поскольку расстояние между вашими сторонами меньше, ваш проигрыш невозможен!

Несколько слов об общей стратегии игры в гекс. По сообщениям многих читателей, они были разочарованы, обнаружив, что первый игрок очень легко одерживает победу, если занимает центральную клетку и продолжает от нее строить цепь до краев доски. Эти читатели полагают, что запереть первого игрока невозможно, поскольку он всегда может сделать ход, присоединив к своей цепочке одну из двух клеток. Сторонники подобной точки зрения просто не обладают достаточным опытом игры в гекс, иначе бы они обнаружили, что для того, чтобы запереть противника, совсем не обязательно занимать клетки, примыкающие к концам цепи. Игра в гекс намного хитрее, чем кажется с первого взгляда. Блокирование цепи часто происходит внезапно, в результате действий, не имеющих, казалось бы, к этому ни малейшего отношения.

Более изощренная стратегия основана на следующем методе.

Сделайте первый ход в центр, а затем постарайтесь занять отдельные клетки по диагонали или по вертикали так, как это сделано на рис. 38.

Рис. 38

Если ваш противник помешает вам достроить вертикаль, вы придете по диагонали. Если он попытается помешать вам достроить диагональ, вы сделаете ход, заняв клетку на вертикали.

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

Совсем иной принцип положен в основу стратегии машины для игры в гекс, сконструированной К. Шенноном и Э. Ф. Муром. Вот описание этого устройства..[15]15
  Шеннон К. Работы по теории информации и кибернетике. – М.: ИЛ, 1963, стр. 162–180.


[Закрыть]

После исследования игры мы пришли к заключению, что достаточно разумный ход можно было бы находить следующим образом: создать двумерное потенциальное поле, соответствующее игральной доске, белые фишки заменить положительными зарядами, черные фишки – отрицательными. Верх и низ «доски» должны нести отрицательный заряд, а ее правая и левая стороны – положительный. Очередному ходу соответствует некоторая вполне определенная седловая точка поля.

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

Нередко ей случалось озадачивать своих создателей странными на первый взгляд ходами, но при более подробном рассмотрении эти ходы неизменно оказывались вполне разумными. Принято считать, что вычислительные машины прекрасно справляются с длинными вычислениями, но малопригодны для решения более сложных, логических задач. Как ни парадоксально, но построенная нами машина вполне разумно оценивала позицию в игре.

Хуже всего она играла в конце партии, когда игра приобретала комбинационный характер. Любопытно заметить также, что машина для игры в гекс заменила обычную вычислительную процедуру на обратную, решив существенно дискретную проблему с помощью аналогового устройства.

Желая подшутить над специалистами по теории игр, знающими о существенных преимуществах первого игрока, Шеннон построил еще одну машину для игры в гекс, которая, к немалому удивлению знатоков, выигрывала даже в тех случаях, когда делала второй ход.

Доска, на которой играла эта машина, в одном направлении была короче, чем в другом (размеры доски 7x8 клеток), но Шеннон, установив ее на прямоугольной подставке, замаскировал неравенство сторон. Лишь немногие из игроков, заподозрив неладное, догадывались пересчитать клетки вдоль сторон доски. Машина играла в соответствии с выигрышной стратегией, описанной выше. Ответные ходы она могла бы делать мгновенно, но специально предусмотренные термисторы замедляли ее «реакцию». Перед каждым ходом машина «размышляла» от одной до десяти секунд, создавая у зрителей впечатление, будто она проделывает сложнейший анализ положения на доске.

Ответы

Решения трех задач, возникающих при игре в гекс (см. рис. 36), показаны на рис. 39.

Рис. 39

Полный анализ всех ходов, возможных в этих задачах, оказывается слишком длинным, чтобы его здесь приводить: крестиками отмечены лишь первые правильные ходы «белых».

Глава 9. АМЕРИКАНСКИЙ ИЗОБРЕТАТЕЛЬ ГОЛОВОЛОМОК СЭМ ЛОЙД

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

В действительности было два Лойда – отец и сын. После смерти Лойда-старшего сын отбросил приставку «младший» и продолжил дело отца. Сидя в своей крохотной и темной конторе в Бруклине, Лойд-младший сочинял головоломки для отделов развлечений газет и журналов, издавал книги по занимательной математике, придумывал фокусы. Но сын (Лойд-младший скончался в 1934 году) не обладал отцовской изобретательностью, и его книги мало чем отличались от других наспех составленных компиляций из работ отца. Лойд-старший родился в 1841 году в Филадельфии у «состоятельных, но честных родителей» (собственное выражение Лойда).

В 1844 году его отец, агент по продаже недвижимого имущества, перевез семью в Нью-Йорк, где Сэм до 17 лет посещал общеобразовательную школу. Если бы молодой человек окончил колледж, то из него вполне мог бы выйти выдающийся математик или инженер.

Но Сэм не стал поступать в колледж. Причиной тому в значительной мере явились шахматы.

В течение десяти лет Лойд только и делал, что передвигал по доске шахматные фигуры. В то время шахматы были необыкновенно популярны; многие газеты вели шахматные отделы, где помещались задачи, придуманные читателями. Первая задача Лойда была опубликована одной нью-йоркской газетой, когда автору было всего 14 лет. На протяжении следующих пяти лет он настолько продуктивно сочинял шахматные головоломки, что стал весьма известен в шахматном мире. В 16 лет Лойд стал редактором отдела задач в Chess Monthly («Шахматный ежемесячник»), который тогда издавали Д. У. Фиск и молодой шахматный мастер П. Мерфи.

Позже Лойд редактировал шахматные отделы в одних газетах и под различными псевдонимами регулярно посылал придуманные им задачи в другие.

В 1877–1878 годах Лойд вел еженедельную шахматную страничку в приложении к журналу Scientific American. Каждая его статья начиналась с заглавной буквы, составленной из шахматных фигур задачи. Эти странички вошли в книгу Лойда «Шахматная стратегия», которую он собственноручно набрал и напечатал. Книга Лойда, содержащая 500 его избранных задач, и поныне пользуется огромным спросом.[16]16
  Лойд С. Математическая мозаика. – М.: Мир, 1980.


[Закрыть]

Чаще других перепечатывалась задача Лойда, которую он придумал в 18-летнем возрасте. Эта задача может служить прекрасной иллюстрацией к умению Лойда облекать самые сложные вопросы в форму анекдота.

В 1713 году шведский король Карл XII вместе со своим войском был окружен турками под Бендерами. Не обращая внимания на пули и ядра, король с одним из своих министров часто играл в шахматы. Однажды, когда у них возникла позиция, изображенная на рис. 40, Карл, игравший белыми, объявил противнику мат в три хода. В этот момент шальная пуля сбила с доски белого коня. Карл внимательно изучил новую позицию, улыбнулся и сказал, что коня ему и не нужно, поскольку и без коня он может поставить противнику мат в четыре хода. Едва он успел это сказать, как вторая пуля сбила с доски белую пешку h2. Карл невозмутимо оглядел оставшиеся на доске фигуры и объявил противнику мат в пять ходов.

Рис. 40

У этой истории есть продолжение. Через несколько лет после появления задачи Лойда один немецкий шахматист заметил, что если бы первая пуля сбила вместо коня белую ладью, то Карл все равно мог бы объявить мат в шесть ходов. Читатели, увлекающиеся шахматами, наверное, с удовольствием поразмыслят над этой замечательной «четырехсерийной» задачей.

Первая головоломка, принесшая коммерческий успех, была придумана Лойдом, когда ему еще не исполнилось и двадцати лет. Она изображена на рис. 41 точно в таком виде, как ее нарисовал Лойд.

Рис. 41

Разрезав картинку вдоль пунктирных линий и переставив ее части (не сгибая их при этом), мы увидим наездников, сидящих верхом на ослах. П. Т. Барнум приобрел у Лойда право издания нескольких таких картинок и выпустил их в продажу миллионными тиражами под названием «П. Т. Барнум и его волшебные ослики». Говорят, что за несколько недель эта головоломка принесла Лойду 10000 долларов. Не утратила она своей популярности и в наши дни.

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

Рис. 42

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

За правильное решение головоломки Лойд назначил премию в 1000 долларов. Десятки сотен людей клялись, что они решили задачу, но ни один так и не смог вспомнить ходы, чтобы записать их и получить за это премию. Назначая премию, Лойд ничем не рисковал, ибо предложенная им задача неразрешима. Из более чем 20 миллиардов всевозможных расположений квадратов ровно половину комбинаций можно получить, передвигая квадраты из начального расположения, показанного на рис. 42. Остальные расположения квадратов, в том числе и то, которое требуется найти, если воспользоваться терминологией теории перестановок, обладают другой «четностью», а перестановки, обладающие различной четностью, не переходят друг в друга при перемещении квадратов внутри коробочки.

Можно играть и по-другому: беспорядочно сложить квадратики в коробочку и, передвигая, пытаться расположить их по порядку номеров. Вероятность успеха, очевидно, равна 1/2. Существует простой способ, позволяющий узнать, можно ли получить данную перестановку В из любой другой перестановки А: для этого нужно лишь подсчитать число «транспозиций» (каждая транспозиция означает перестановку двух квадратов: их нужно вынуть из коробочки и поменять местами), которые необходимо совершить, чтобы превратить А в В. Если это число четно, то А и В имеют одинаковую четность и тогда, передвигая квадраты, А можно переводить в В и наоборот.

То обстоятельство, что транспозиция двух квадратиков автоматически меняет четность перестановки их номеров, положено в основу одной довольно злой задачи-шутки (разновидности игры в пятнадцать), выпущенной в продажу несколько десятков лет назад. На квадратиках, как показано на рис. 43, написаны не цифры, а буквы. На квадратах одного цвета (у нас они заштрихованы) написаны слова RATE и YOUR, на квадратах другого цвета слова MIND и PAL.[17]17
  Rate your mind pal – пошевели-ка мозгами, приятель (англ.).


[Закрыть] Вы показываете квадраты с получившейся на них надписью своей жертве и затем перемешиваете их как угодно. При этом вы незаметно загоняете второе R в левый верхний угол. Ваша несчастная жертва, конечно, оставит букву R в левом верхнем углу и будет пытаться расположить по порядку остальные буквы.

Эта задача безнадежна, потому что, поменяв местами буквы R, вы изменили четность перестановки. В лучшем случае бедняга сможет получить «RATE YOUR MIND PAL».[18]18
  Те, кто не знают английского языка, могут воспользоваться вольным «переводом» головоломки – русской фразой (без знаков препинания): «Слон спит стоя, а вы?» (рис. 43). Перемешивая шашки, нужно незаметно совершить подлог: заменить букву «с», стоящую в левом верхнем углу, начальной буквой слова «спит».


[Закрыть]

Из всех головоломок Лойда наибольшей известностью, несомненно, пользовалась его загадочная картинка «Таинственное исчезновение», запатентованная им в 1896 году. Картонный круг в центре прикрепляется к картонному квадрату. По окружности нарисованы 13 воинов, частично – на круге, частично – на квадрате.

Если круг немного повернуть, части воинов соединятся уже другому, а один воин совсем исчезнет! Эту головоломку неоднократно публиковали, поэтому на рис. 44 показана менее популярная, но в каком-то смысле более занимательная загадочная картинка, которая называется «Тэдди и львы». В одном положении круга вы видите семь львов и семь охотников, а в другом – восемь львов и шесть охотников. Откуда берется восьмой лев? Кто из охотников исчезает и куда он девается?

Рис. 44 Загадочная картинка Лойда «Тедди и львы». На картинке вверху – семь львов и семь охотников, на картинке внизу – восемь львов и шесть охотников.

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

В Сиаме очень ценятся два вида бойцовых рыб: большой белый окунь, называемый королевской рыбой, и маленький черный карп, известный под названием дьявольской рыбки. Эти виды рыб настолько враждуют между собой, что, едва завидев друг друга, бросаются в бой и бьются насмерть.

Королевская рыба легко может справиться за несколько секунд с одной или двумя маленькими рыбками. Но дьявольские рыбки настолько проворны и действуют так слаженно, что втроем не уступят одной большой рыбе, однако не смогут и одолеть ее. Атакуют они так умело и изобретательно, что вчетвером приканчивают большую рыбу за какие-нибудь три минуты. Собираясь в еще большую стайку, они расправляются со своим врагом еще быстрее, причем между продолжительностью схватки и числом рыбок существует прямо пропорциональная зависимость (то есть пять рыбок расправятся с одной королевской рыбой за 2 мин 24 сек, шесть рыбок – за 2 мин ровно и т. д.).

Предположим, что 4 королевские рыбы сражаются с 13 дьявольскими рыбками. Кто выиграет бой и сколько времени он продлится? Предполагается, что дьявольские рыбки действуют наиболее эффективным способом.

Во избежание неоднозначности в условии сформулированной Лойдом задачи следует пояснить, что дьявольские рыбки всегда атакуют группами из трех и более рыб и, напав на королевскую рыбу, дерутся до тех пор, пока не прикончат ее. Мы не можем, например, предположить, что, пока двенадцать дьявольских рыбок осаждают четырех больших рыб, тринадцатая дьявольская рыбка носится туда и обратно, нападая на всех четырех больших рыб одновременно. Если принять предположение о том, что на большую рыбу может нападать не только целая дьявольская рыбка, но и любая ее доля, то рассуждать можно так. Если четыре дьявольские рыбки приканчивают одну королевскую рыбу за три минуты, то тринадцать дьявольских рыбок прикончат ее за 12/13 мин, а четырех королевских рыб – за 48/13 мин (то есть за 3 мин 41 7/13 сек). Но рассуждая точно таким же образом, можно показать, что двенадцать дьявольских рыбок прикончат одну королевскую рыбу за одну минуту, а четырех рыб – за четыре минуты, даже без помощи тринадцатой рыбки. Это заключение, очевидно, противоречит условию Лойда о том, что три дьявольские рыбки не могут совместными усилиями одолеть врага.

Профессор Артур У. Беркс сообщил мне об интересной связи, существующей между лойдовскои игрой в пятнадцать и компьютером. Оба они обладают конечным числом состояний, последовательно сменяющих друг друга. Работа компьютера и решение головоломки начинаются с вполне определенного состояния. Все остальные состояния можно разделить на две группы: «допустимые», реализующиеся при указанных начальных данных, и «недопустимые», которые реализоваться не могут. Эту связь Беркс рассмотрел более подробно в свой книге.[19]19
  Burks A. W. The Logic of Fixed and Growing Automata: Engineering Research Institute of the University of Michigan. – 1957.


[Закрыть]

Ответы

В шахматной задаче «белые» объявляют мат в три хода, взяв пешку ладьей. Если черный слон возьмет ладью, то белые переведут своего коня на f3, тем самым вынуждая черных переставить слона. Тогда белые объявляют мат, делая ход пешкой на g4. Если бы черные взяли вместо ладьи коня, белые объявили бы шах ладьей Лh3+, черные в этом случае прикрываются слоном (Ch4), а белые, как и раньше, объявляют пешкой мат на g4.

После того как пуля сбила белого коня, белые, взяв черную пешку пешкой, объявят мат в четыре хода. Если черные сделают ход слоном СеЗ, то белые ответят ладьей Лg4. Далее следует ход черного слона Cg5 и ответный ход белой ладьей Лh4+ (шах). Черный слон берет ладью, а белые объявляют мат пешкой на g4.

После того как пуля сбила с доски белую пешку h2, белые объявляют мат в пять ходов, делая первый ход ладьей Лb7. Если последует ход черных СеЗ, то 2. Лb1 Cg5; 3. Лh + Ch4; 4. Лh2!! gh; 5. g4x (мат).

Если же черные делают первый ответный ход слоном Cg1, то следует: 2. Лb1 Ch2; 3. Ле1 Kph4; 4. Kpg6. На любой ход черных белые отвечают 5. Ле4х (мат).

Если бы первой пулей была сбита белая ладья, а не конь, белые объявили бы мат в шесть ходов, начиная игру конем (Kf3). Тогда лучшим ходом черных был бы ход слоном Ce1, который привел бы к такому продолжению: 2. K: el Kph4; 3. h3 Kph5; 4. Kd3 Kph4; 5. Kf4 h5; 6. Kg6x (мат).

* * *

Наездников можно посадить на ослов (которые при этом словно по волшебству сразу поскачут галопом) таким образом, как это пoказано на рис. 45.

Рис. 45 Решение головоломки с ослами и седоками.

На рис. 46 воспроизведен предполагаемый источник головоломки Лойда: персидский рисунок начала семнадцатого века.

Рис. 46 Персидский рисунок XVII века, послуживший, как предполагают, источником головоломки Лойда.

* * *

Что касается загадочной картинки «Тедди и львы», то бессмысленно спрашивать, который из львов исчез или который из охотников вдруг появился. Когда части смещаются, исчезают все львы и охотники, а вместо них появляются восемь новых львов, каждый на 1/8 меньше первоначального, и шесть новых охотников, каждый на 1/6 больше прежнего.

* * *

Известно много решений задачи о дерущихся рыбах. Вот решение, которое дал сам Лойд.

Четыре маленькие рыбки расправляются за 3 мин с одной большой рыбой, в то время как остальные дьявольские рыбки, разбившись на тройки, нападают на каждую из трех остальных больших рыб. После этого пять рыбок, объединившись, разделываются с еще одной большой рыбой за 2 мин 24 сек. Остальные маленькие рыбки в это время продолжают драться с большими.

Если бы этим рыбкам (они разделились на две группы, так как дерутся с двумя королевскими рыбами) помогала еще одна дьявольская рыбка, то все три группы рыбок кончили бы бой одновременно. Поэтому сил у каждой из оставшихся в живых королевских рыб осталось ровно столько, сколько необходимо, чтобы сражаться с одной дьявольской рыбкой в течение 2 мин 24 сек. Если же на любую из королевских рыб нападает сразу не одна, а семь рыбок, то они приканчивают ее за у этого времени, то есть 20 4/7 сек.

У единственной оставшейся в живых королевской рыбы сил к концу этих 20 4/7 сек хватит только на то, чтобы продержаться еще 20 4/7 сек против одной дьявольской рыбки (напомним, что на нее нападало шесть маленьких рыбок). Все же 13 дьявольских рыбок, объединив свои силы, расправляются с ней за 1/13 этого времени, то есть за 1 53/91 сек.

Сложив продолжительность всех схваток – 3 мин, 2 мин 24 сек, 20 4/7 сек и 1 53/91 сек, мы найдем, что весь бой длился 5 мин 46 2/13 сек.