Мартин Гарднер - Математические головоломки и развлечения
Рис. 42
В коробочке могут свободно перемещаться 15 перенумерованных квадратных шашек. Два последних квадрата переставлены. Требуется, не вынимая из коробочки, передвинуть квадраты так, чтобы их номера расположились по порядку, а пустой квадрат оказался в правом нижнем углу. В семидесятых годах прошлого века игра в пятнадцать была в большой моде, ей посвящались даже научные статьи в математических журналах.
За правильное решение головоломки Лойд назначил премию в 1000 долларов. Десятки сотен людей клялись, что они решили задачу, но ни один так и не смог вспомнить ходы, чтобы записать их и получить за это премию. Назначая премию, Лойд ничем не рисковал, ибо предложенная им задача неразрешима. Из более чем 20 миллиардов всевозможных расположений квадратов ровно половину комбинаций можно получить, передвигая квадраты из начального расположения, показанного на рис. 42. Остальные расположения квадратов, в том числе и то, которое требуется найти, если воспользоваться терминологией теории перестановок, обладают другой «четностью», а перестановки, обладающие различной четностью, не переходят друг в друга при перемещении квадратов внутри коробочки.
Можно играть и по-другому: беспорядочно сложить квадратики в коробочку и, передвигая, пытаться расположить их по порядку номеров. Вероятность успеха, очевидно, равна 1/2. Существует простой способ, позволяющий узнать, можно ли получить данную перестановку В из любой другой перестановки А: для этого нужно лишь подсчитать число «транспозиций» (каждая транспозиция означает перестановку двух квадратов: их нужно вынуть из коробочки и поменять местами), которые необходимо совершить, чтобы превратить А в В. Если это число четно, то А и В имеют одинаковую четность и тогда, передвигая квадраты, А можно переводить в В и наоборот.
То обстоятельство, что транспозиция двух квадратиков автоматически меняет четность перестановки их номеров, положено в основу одной довольно злой задачи-шутки (разновидности игры в пятнадцать), выпущенной в продажу несколько десятков лет назад. На квадратиках, как показано на рис. 43, написаны не цифры, а буквы. На квадратах одного цвета (у нас они заштрихованы) написаны слова RATE и YOUR, на квадратах другого цвета слова MIND и PAL.[17] Вы показываете квадраты с получившейся на них надписью своей жертве и затем перемешиваете их как угодно. При этом вы незаметно загоняете второе R в левый верхний угол. Ваша несчастная жертва, конечно, оставит букву R в левом верхнем углу и будет пытаться расположить по порядку остальные буквы.
Эта задача безнадежна, потому что, поменяв местами буквы R, вы изменили четность перестановки. В лучшем случае бедняга сможет получить «RATE YOUR MIND PAL».[18]
Из всех головоломок Лойда наибольшей известностью, несомненно, пользовалась его загадочная картинка «Таинственное исчезновение», запатентованная им в 1896 году. Картонный круг в центре прикрепляется к картонному квадрату. По окружности нарисованы 13 воинов, частично — на круге, частично — на квадрате.
Если круг немного повернуть, части воинов соединятся уже другому, а один воин совсем исчезнет! Эту головоломку неоднократно публиковали, поэтому на рис. 44 показана менее популярная, но в каком-то смысле более занимательная загадочная картинка, которая называется «Тэдди и львы». В одном положении круга вы видите семь львов и семь охотников, а в другом — восемь львов и шесть охотников. Откуда берется восьмой лев? Кто из охотников исчезает и куда он девается?
Рис. 44 Загадочная картинка Лойда «Тедди и львы». На картинке вверху — семь львов и семь охотников, на картинке внизу — восемь львов и шесть охотников.
В 1914 году, через три года после смерти отца, Лойд-младший издал гигантскую «Энциклопедию головоломок», в которой была собрана, несомненно, самая обширная коллекция задач, когда-либо появлявшаяся в одном сборнике. Из этой сказочной, давно уже ставшей библиографической редкостью книги заимствована следующая задача. На ее примере видно, как искусно умел старый мастер переделывать любую, пусть даже самую простую задачу, для решения которой не нужно владеть ничем, кроме умения логически мыслить и обращаться с дробями, превращая ее в захватывающе увлекательную головоломку.
В Сиаме очень ценятся два вида бойцовых рыб: большой белый окунь, называемый королевской рыбой, и маленький черный карп, известный под названием дьявольской рыбки. Эти виды рыб настолько враждуют между собой, что, едва завидев друг друга, бросаются в бой и бьются насмерть.
Королевская рыба легко может справиться за несколько секунд с одной или двумя маленькими рыбками. Но дьявольские рыбки настолько проворны и действуют так слаженно, что втроем не уступят одной большой рыбе, однако не смогут и одолеть ее. Атакуют они так умело и изобретательно, что вчетвером приканчивают большую рыбу за какие-нибудь три минуты. Собираясь в еще большую стайку, они расправляются со своим врагом еще быстрее, причем между продолжительностью схватки и числом рыбок существует прямо пропорциональная зависимость (то есть пять рыбок расправятся с одной королевской рыбой за 2 мин 24 сек, шесть рыбок — за 2 мин ровно и т. д.).
Предположим, что 4 королевские рыбы сражаются с 13 дьявольскими рыбками. Кто выиграет бой и сколько времени он продлится? Предполагается, что дьявольские рыбки действуют наиболее эффективным способом.
Во избежание неоднозначности в условии сформулированной Лойдом задачи следует пояснить, что дьявольские рыбки всегда атакуют группами из трех и более рыб и, напав на королевскую рыбу, дерутся до тех пор, пока не прикончат ее. Мы не можем, например, предположить, что, пока двенадцать дьявольских рыбок осаждают четырех больших рыб, тринадцатая дьявольская рыбка носится туда и обратно, нападая на всех четырех больших рыб одновременно. Если принять предположение о том, что на большую рыбу может нападать не только целая дьявольская рыбка, но и любая ее доля, то рассуждать можно так. Если четыре дьявольские рыбки приканчивают одну королевскую рыбу за три минуты, то тринадцать дьявольских рыбок прикончат ее за 12/13 мин, а четырех королевских рыб — за 48/13 мин (то есть за 3 мин 41 7/13 сек). Но рассуждая точно таким же образом, можно показать, что двенадцать дьявольских рыбок прикончат одну королевскую рыбу за одну минуту, а четырех рыб — за четыре минуты, даже без помощи тринадцатой рыбки. Это заключение, очевидно, противоречит условию Лойда о том, что три дьявольские рыбки не могут совместными усилиями одолеть врага.
Профессор Артур У. Беркс сообщил мне об интересной связи, существующей между лойдовскои игрой в пятнадцать и компьютером. Оба они обладают конечным числом состояний, последовательно сменяющих друг друга. Работа компьютера и решение головоломки начинаются с вполне определенного состояния. Все остальные состояния можно разделить на две группы: «допустимые», реализующиеся при указанных начальных данных, и «недопустимые», которые реализоваться не могут. Эту связь Беркс рассмотрел более подробно в свой книге.[19]
Ответы
В шахматной задаче «белые» объявляют мат в три хода, взяв пешку ладьей. Если черный слон возьмет ладью, то белые переведут своего коня на 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 (мат).
