240 х 120 = 28 800.
Число это во много раз меньше предыдущего и потребовало бы всего 79 лет (без малого). Доживи молодые посетители ресторана до столетнего возраста, они могли бы дождаться бесплатного обеда если не от самого официанта, то от его наследников.
Умея подсчитывать перестановки, мы можем определить теперь, сколько различных расположений шашек[16] возможно в коробке игры в «15». Другими словами, можем подсчитать число всех задач, какие способна предложить нам эта игра. Легко понять, что подсчет сводится к определению числа перестановок из 15 предметов. Мы знаем уже, что для этого нужно перемножить
1 х 2 х 3 х 4 х… и т. д… х 14 х 15.
Вычисление дает итог:
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.
- Вот ты и постиг эту старинную игру. Одно только практическое правило надо тебе еще знать: если в стопке число монет нечетное, то первую монету перекладывают на третье блюдце, если четное - то на среднее блюдце.
- Ты сказал: старинная игра. Разве не сам ты ее придумал?
- Нет, я только применил ее к монетам. Игра очень древнего происхождения и зародилась, говорят, в Индии. Существует интересная легенда, связанная с этой игрой. В городе Бенаресе будто бы имеется храм, в котором индусский бог Брама при сотворении мира установил три алмазных палочки и надел на одну из них 64 золотых кружка: самый большой внизу, а каждый следующий меньше предыдущего. Жрецы храма обязаны без устали, днем и ночью, перекладывать эти кружочки с одной палочки на другую, пользуясь третьей, как вспомогательной, и, соблюдая правила нашей игры, переносить за раз только один кружок и не класть большего на меньший. Легенда говорит, что когда будут перенесены все 64 кружка, наступит конец мира.
- О, значит, мир давно уже должен был погибнуть, если верить этому преданию!
- Ты, по-видимому, думаешь, что перенесение 64 кружков не должно отнять много времени?
- Конечно. Делая каждую секунду один ход, можно ведь в час успеть проделать 3600 перенесений.
- Ну и что же?
- А в сутки - около ста тысяч. В десять дней - миллион ходов. Миллионом же ходов можно, я уверен, перенести хоть тысячу кружков.
- Ошибаешься. Чтобы перенести всего 64 кружка, нужно уже круглым счетом 500 миллиардов лет.
- «Только» 18 триллионов с лишком, если называть триллионом миллион миллионов.
- Погоди, я сейчас перемножу и проверю.
- Прекрасно. А пока будешь умножать, я успею сходить по своим делам.
И брат ушел, оставив меня погруженным в выкладки. Я нашел сначала произведение 16 двоек, затем умножил этот результат - 65 536 - сам на себя, а то, что получилось, - снова на себя. Потом не забыл отнять единицу.
У меня получилось такое число[19]:
18 446 744 073 709 551 615. Брат, значит, был прав.
Вам, вероятно, интересно было бы знать, какими числами в действительности определяется возраст мира. Ученые располагают на этот счет некоторыми, конечно, лишь приблизительными данными:
Солнце существует…10 000 000 000 000 лет
Земной шар…2 000 000 000»
Жизнь на Земле… 300 000 000»
Человек…300 000»
62. Пари
В столовой дома отдыха за обедом зашла речь о том, как вычисляется вероятность событий. Молодой математик, оказавшийся среди обедающих, вынул монету и сказал:
- Кидаю на стол монету не глядя. Какова вероятность, что она упадет гербом вверх?
- Объясните сначала, что значит «вероятность», - раздались голоса. - Не всем ясно.
Рис. 87. Монета может лечь на стол двояко
- О, это очень просто! Монета может лечь на стол двояко: вот так - гербом вверх и вот так - гербом вниз. Всех случаев здесь возможно только два. Из них для интересующего нас события благоприятен лишь один случай. Теперь находим отношение
Дробь 1/2 и выражает «вероятность» того, что монета упадет гербом вверх.
- С монетой-то просто, - вмешался кто-то. - А вы рассмотрите случай посложней, с игральной костью например.
- Давайте рассмотрим, - согласился математик. - У нас игральная кость, кубик с цифрами на гранях. Какова вероятность, что брошенный кубик упадет определенной цифрой вверх, скажем, вскроется шестеркой? Сколько здесь всех возможных случаев? Кубик может лечь на любую из своих шести граней; значит, возможно всего 6 случаев. Из них благоприятен нам только один: когда вверху шестерка. Итак, вероятность получится от деления 1 на 6. Короче говоря, она выражается дробью 1/6.