Живая математика

Вычисление дает итог:

1 307 674 365 000,

т. е. больше триллиона.

Из этого огромного числа задач половина неразрешима. Существует, значит, свыше 600 миллиардов неразрешимых положений в этой игре. Отсюда понятна отчасти та эпидемия увлечения игрой в «15», которая охватила людей, не подозревавших о существовании такого огромного числа неразрешимых случаев.

IV

Заканчивая нашу беседу о числе перестановок, решим такую задачу из школьной жизни.

В классе 25 учеников. Сколькими способами можно рассадить их по партам?

Путь решения этой задачи - для тех, кто усвоил себе все сказанное раньше - весьма несложен: нужно перемножить 25 таких чисел:

1 х 2 х З х 4 х 5 х 6… х 23 х 24 х 25.

Результат получается огромный, из 26 цифр - число, величину которого наше воображение не в силах себе представить. Вот оно:[17]

15 511 210 043 330 985 984 000 000.

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

61. Перекладывание монет

В детстве старший брат показал мне, помню, занимательную игру с монетами. Поставив рядом три блюдца, он положил в крайнее блюдце стопку из 5 монет: вниз - рублевую, на нее - полтинник, выше - двугривенный, далее - пятиалтынный и на самый верх - гривенник[18].

Рис. 85. Брат показал мне занимательную игру

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

Так выглядели монеты, о которых идет речь

Я принялся перекладывать. Положил гривенник на третье блюдце, пятиалтынный на среднее и запнулся. Куда положить двугривенный? Ведь он крупнее и гривенника, и пятиалтынного.

- Ну, что же? - выручил меня брат. - Клади гривенник на среднее блюдце, поверх пятиалтынного. Тогда для двугривенного освободится третье блюдце.

Я так и сделал. Но дальше - новое затруднение. Куда положить полтинник? Впрочем, я скоро догадался: перенес сначала гривенник на первое блюдце, пятиалтынный на третье и затем гривенник тоже на третье. Теперь полтинник можно положить на свободное среднее блюдце. Дальше, после длинного ряда перекладываний, мне удалось перенести также рублевую монету с первого блюдца и, наконец, собрать всю кучку монет на третьем блюдце.

- Сколько же ты проделал всех перекладываний? - спросил брат, одобрив мою работу.

- Не считал.

- Давай сосчитаем. Интересно же знать, каким наименьшим числом ходов можно достигнуть цели. Если бы стопка состояла не из 5, а только из 2 монет - пятиалтынного и гривенника, - то сколько понадобилось бы ходов?

- Три: гривенник на среднее блюдце, пятиалтынный - на третье и затем гривенник на третье блюдце.

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

3 + 1 + 3 = 7.

- Для четырех монет число ходов позволь мне сосчитать самому. Сначала переношу 3 меньшие монеты на среднее блюдце - 7 ходов; потом полтинник на третье блюдце - 1 ход и затем снова три меньшие монеты на третье блюдце - еще 7 ходов. Итого:

7 + 1 + 7 = 15.

- Отлично. А для пяти монет?

- 15 + 1 + 15 = 31, - сразу сообразил я.

- Ну, вот ты и уловил способ вычисления. Но я покажу тебе, как можно его еще упростить. Заметь, что полученные нами числа 3, 7, 15, 31 - все представляют собой двойку, умноженную на себя один или несколько раз, но без единицы. Смотри.

Рис. 86. Жрецы обязаны перекладывать кружки…

И брат написал табличку:

3 = 2 х 2-1

7 = 2 х 2 x 2-1

15 = 2 х 2 х 2 х 2-1

31=2 x 2 x 2 x 2 x 2-1.

- Понимаю: сколько монет перекладывается, столько раз берется двойка множителем, а затем отнимается единица. Я мог бы теперь вычислить число ходов для любой стопки монет. Например, для 7 монет:

2 х 2 х 2 х 2 х 2 х 2 х 2-1 = 128 -1 = 127.

- Вот ты и постиг эту старинную игру. Одно только практическое правило надо тебе еще знать: если в стопке число монет нечетное, то первую монету перекладывают на третье блюдце, если четное - то на среднее блюдце.

- Ты сказал: старинная игра. Разве не сам ты ее придумал?