Расположите два вида монет так, как показано ниже на рисунке 1, чередуя разные монеты. Если у вас монеты только одного вида, расположите их поочередно вверх орлом и решкой. Ваша задача – изменить положение восьми монет так, чтобы четыре монеты одного вида находились рядом друг с другом, как показано на рисунке 2.
Каждый шаг сводится к одновременному перемещению двух соседних монет. Вы можете передвигать их на любое место на той же линии, что и другие монеты, но при этом их нельзя менять местами: при перемещении левая монета должна оставаться слева, а правая – справа.
Удастся ли вам решить эту задачу за четыре шага?
Возможно, вы впадете в уныние, если не сможете решить эту головоломку сразу. Но, прошу, проявите упорство, поскольку вы способны найти решение. Для того чтобы вам помочь, предлагаю более простой вариант этой задачи – с шестью монетами. Обратите внимание: в итоге все монеты смещаются влево на два промежутка.
Пока мы не закрыли эту тему, хочу сказать несколько слов о последней задаче в стиле головоломки Тэйта. В ней используются пять монет, но вводится дополнительное условие, согласно которому перемещать можно только две разные монеты за один шаг. На рисунке ниже изображены два ряда монет. Можете ли вы за четыре шага расположить монеты из верхнего ряда так, как показано в нижнем ряду?
Французский математик Эдуард Люка, с которым мы встречались в предыдущей главе (помните его задачу об океанских лайнерах?), включил две следующие классические головоломки в свою книгу Récréations Mathématiques («Занимательная математика»). Обе относятся к категории чрезвычайно запутанных, но невероятно простых задач.
Восемь монет расположены в один ряд, как показано на рисунке ниже. Каждый раз вы можете передвигать монету либо направо, либо налево так, чтобы она, перешагнув через две монеты, попала на третью. Перешагивать можно через две монеты по одной или через стопку из двух монет.
Можете ли вы переместить четыре монеты так, чтобы в конечном счете у вас получилось четыре стопки по две монеты?
Люка называл следующую головоломку jeu des grenouilles – «Игра лягушек». Он предлагал использовать в ней черные и белые пешки, но при отсутствии шахмат подойдут и монеты.
Расположите три монеты одного номинала и три монеты другого номинала в ряд, как показано на рисунке ниже, оставив посредине свободное место. (Или выложите три монеты вверх орлом, а три – решкой.) Представьте себе, что слева – три лягушки, а справа – три жабы. Лягушки могут передвигаться только слева направо, а жабы только справа налево. Лягушка или жаба может либо переместиться на один шаг вперед на свободное место, либо перепрыгнуть через одну монету на свободное место, при условии, что она передвигается в правильном направлении.
Можете ли вы переместить всех лягушек на позиции жаб, а жаб на позиции лягушек?
Солитер (или колышковый солитер), пожалуй, самая известная игра для одного игрока, в которой одни предметы «перепрыгивают» через другие. «Мне доставляет огромное удовольствие игра под названием “Солитер”», – писал в 1716 году в одном из своих писем немецкий энциклопедист Готфрид Лейбниц. Вклад Лейбница в математику и философию включает открытие исчисления бесконечно малых величин (независимо от Исаака Ньютона), изобретение арифмометра, а также описание двоичной системы счисления, в которой нули и единицы соответствовали отверстиям и колышкам в его любимой игре. Однако Лейбниц предпочитал играть в нее наоборот: вместо того чтобы перепрыгивать через колышек на свободное место, убирая колышек с поля, он перешагивал пустое место и ставил на нем колышек. «Но зачем все это, спросите вы, – писал он. – Отвечу: чтобы совершенствовать искусство изобретать новое».
Далее мы с вами сыграем в солитер с монетами. В игре действуют обычные правила: любая монета может перешагнуть через соседнюю и занять место с другой стороны, после чего монета, через которую перешагнули, удаляется с поля. Как и в шашках, при желании можно ходить через несколько монет за один шаг, если монета занимает позицию, в которой возможен следующий шаг.
Расположите десять монет треугольником, как показано на рисунке. Одну монету уберите. Теперь, перешагивая через другие монеты, уменьшите треугольник до одной монеты.
Как и предыдущие головоломки с монетами, эта тоже всецело поглотит ваше внимание, пока вы ее не решите. Но прежде чем вы начнете, рекомендую разложить монеты на листе бумаги, на котором отмечены 10 точек, чтобы монеты не смещались со своих мест.
Поиграв немного, вы можете обнаружить следующее решение за шесть ходов после удаления монеты с позиции 2:
1. Монета на позиции 7 перемещается на позицию 2 (монета на позиции 4 удаляется).
2. Монета 9 перемещается на 7 (8 удаляется).
3. 1 перемещается на 4 (2 удаляется).
4. 7 перемещается на 2 (4 удаляется).
5. 6 перемещается на 4, затем на 1, а затем на 6 (5, 2 и 3 удаляются).
6. 10 перемещается на 3 (6 удаляется).
Но мы можем решить эту головоломку и за пять ходов. Попробуйте найти такое решение.
В эту главу я включил полдюжины задач с монетами (почти полглавы), поскольку монеты – самый универсальный предмет из всех используемых в головоломках. Существует много способов применения монет: их можно передвигать, не отрывая от поверхности, укладывать стопками, использовать в качестве геометрических точек или колышков для «Солитера». Кроме того, у монет две различающиеся стороны, что положено в основу следующей головоломки (или фокуса).
Представьте, что вы фокусник и у вас завязаны глаза. Вы предлагаете одному из зрителей положить десять монет на стоящий перед вами стол и сообщить вам, сколько монет перевернуты орлом вверх.
Вы не видите монеты, а значит, не можете определить, какой стороной они расположены вверх.
Как вам разделить монеты на две группы таким образом, чтобы в обеих группах было одинаковое количество орлов?
Когда я впервые увидел этот фокус, я был впечатлен, но его решение поразило меня гораздо больше.
Попытайтесь сначала решить задачу с открытыми глазами. Возьмите десять монет и разложите их на столе так, чтобы было видно, скажем, три орла. Попробуйте разделить монеты на две группы, чтобы в обеих оказалось одинаковое количество орлов. Поскольку три орла не делятся на два без остатка, вам придется перевернуть несколько монет. Ключ к решению головоломки – понять, сколько монет нужно перевернуть, а затем придумать, как проделать то же самое с завязанными глазами.
Головоломка с монетами в темноте похожа на фокус, так как в ходе ее решения неожиданно наступает приятное озарение. Вообще-то многие головоломки напоминают трюки фокусника, и не только потому, что их решение – это своего рода откровение, но и потому, что зачастую они основаны на неявном введении в заблуждение.
Я включил следующую задачу в эту главу, потому что в ней тоже используются монеты, а решение поразительно. Конечно, я не рассчитываю на то, что вы и правда станете раскладывать на столе сотню монет, но, если вам не удастся найти ответ, все же настоятельно рекомендую прочитать его, хотя бы из любопытства. Впервые эта задача была задана в 1996 году на Международной олимпиаде по информатике – конкурсе для школьников, который изначально был ориентирован на очень умных подростков – компьютерных гиков. Это замечательная задача.
На столе выложены в ряд сто монет. Пенни и Боб играют в игру, их задача – собрать максимальную сумму денег, поочередно забирая монеты со стола. Игроки могут брать только монеты, находящиеся в конце ряда. Монеты имеют разное достоинство: 1 пенни, 2 пенни, 1 фунт и т. д.
Первой ходит Пенни. Она берет монету с одного конца и кладет ее в карман. Боб забирает монету с другого конца ряда и тоже кладет себе в карман. Так они по очереди берут монеты до тех пор, пока на столе ничего не остается. За каждый ход игроки могут брать монету с любого конца.
Удастся ли вам доказать, что Пенни при любых обстоятельствах может собрать не меньшую сумму денег, чем Боб?
Подсказка: пронумеруйте монеты от 1 до 100.
Ладно, хватит уже игр с монетами! Давайте перейдем к головоломкам со спичками – этот предмет издавна занимает второе место по популярности в головоломках. Однако сначала предлагаю разобрать головоломку, в которой фигурируют и монета, и спички. Считайте ее эквивалентом редкого дуэта двух старых эстрадных певцов в области занимательной математики.
Два перевернутых стакана стоят так, как показано на рисунке. Между ними находится спичка; под левым стаканом лежит монета. Можете ли вы достать монету из-под стакана так, чтобы спичка не упала?
Спички были изобретены в XIX веке, и на протяжении сотни лет задачи со спичками были, пожалуй, самыми распространенными головоломками, которые решали представители разных поколений. Сейчас спички используются не так широко, как раньше, поскольку меньше людей курят, а у курящих, как правило, есть зажигалки. Приемлемой заменой спичкам могут стать зубочистки, карандаши или ватные палочки.