Энциклопедический словарь юного математика

Задачи-головоломки известны с давних времен, они встречаются уже в египетских папирусах. С I в. н.э. известна задача, получившая название задачи Иосифа Флавия, римского историка. Легенда рассказывает, что однажды отряд воинов, среди которых находились Флавий и его друг, был окружен. Из всех уставших, выбившихся из сил воинов, отчаявшихся спастись, нужно было выбрать двоих, которые предприняли бы попытку найти выход из окружения. Флавий предложил выбрать этих двоих путем пересчета так, чтобы каждый третий выбывал из построенных в круг воинов. Счет продолжался до тех пор, пока не осталось только два человека. Это были мудрый Флавий и его друг. На какие места в круге они встали, если в отряде был 41 воин? Древняя рукопись сообщает: на 16-е и 31-е.

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

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

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

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

Двое называют по очереди любое число от 1 до 10 и складывают названные числа. Выигрывает тот, кто первым доведет до 100 сумму чисел, названных обоими игроками. Оптимальная стратегия в этой игре состоит в том, чтобы после хода противника называть числа, дающие, в сумме с предыдущими, члены следующего ряда: 12, 23, 34, 45, 56, 67, 78, 89, 100.

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

Задача основана на психологической особенности человеческого восприятия – запоминать главные факты из условия задачи. В данном случае – то, что монета в кармане не пятак. И начинаются безуспешные попытки решения. А правильный ответ: 10 коп. и 5 коп., так как в условии задачи сказано, что только одна монета не пятак.

В старинной задаче «Волк, козел и капуста» крестьянину нужно перевезти через реку волка, козла и капусту. Лодка так мала, что в ней кроме крестьянина может поместиться или только волк, или только козел, или только капуста. Но если оставить волка с козлом, то волк его съест, а если оставить козла с капустой, то будет съедена капуста. Как быть крестьянину?

Головоломки типа этой задачи называются комбинаторными (см. Комбинаторика). В таких головоломках требуется путем взаимной перестановки элементов расположить их в соответствии с условием задачи в определенном порядке.

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

К комбинаторным головоломкам относится и знаменитый венгерский кубик Рубика, и полимино, и игры типа «Игра 15», а также задачи «на маневрирование», головоломки с перестановкой шашек, «Ханойская башня» и др.

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

Количество перемещений дисков, которые должны сделать жрецы, вычисляется по формуле 2ⁿ - 1, где n – число дисков. Предположим, что жрецы работают так быстро, что за одну секунду переносят один диск. Тогда на всю работу им понадобится 2⁶⁴-1, или около 580 млрд. лет. За это время храм, действительно, может рассыпаться в пыль.

Рис. 1 Головоломка «Ханойская башня». Перенесите кольцо с левой оси на правую по правилам, изложенным в индийской легенде, не более чем за 31 ход.