О портале "Математика. ру" arrow О числах-великанах arrow 65. Бесплатный обед
Математический портал Математику.ру

Л. де Бройль

Математический язык предоставляет в распоряжение дедукции точный инструмент, в котором она нуждается для совершения, по возможности безошибочного, перехода от посылок к выводам. Исходя в начале рассуждения из абстрактных формул, в которых физические величины представлены символами, ученый, использующий дедуктивное рассуждение, преобразует по правилам логики свои уравнения и приходит к окончательным соотношениям, которые он хочет проверить. Тогда он должен заменить символы цифрами, для того чтобы получить численные результаты, которые можно сравнить с экспериментом; рассуждение уступает место расчету. Такова схема дедуктивного рассуждения в том виде, в каком оно используется во всех науках, достаточно точных, достаточно разработанных для того, чтобы в них можно было применять математический аппарат [31, с. 177].

 

65. Бесплатный обед

Печать E-mail
03.03.2008 г.

65. Бесплатный обед

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

- Молодые друзья мои,  оставьте ваши пререкания.
Сядьте за стол, как кому придется, и выслушайте меня.

Все сели как попало. Официант продолжал:

- Пусть один из вас запишет, в каком порядке вы сейчас сидите.  Завтра вы снова явитесь сюда пообедать и разместитесь уже в ином порядке. Послезавтра сядете опять по-новому и т. д., пока не перепробуете всех воз­можных размещений. Когда же придет черед вновь сесть так, как сидите вы здесь сегодня, тогда - обещаю торжественно - я начну ежедневно угощать вас бесплатно самыми
изысканными обедами.

Предложение   понравилось.   Решено  было  ежедневно собираться в этом ресторане и перепробовать все способы размещения за столом, чтобы скорее начать пользоваться
бесплатными обедами.                                            

Однако, им не пришлось дождаться этого дня. И вовсе не потому, что официант не исполнил обещания, а потому, что   число   всех   возможных   размещений  за столом че­ресчур  велико.   Оно  равняется  ни  мало,   ни  много - 3 628 800.   Такое  число  дней  составляет,   как  нетрудно сосчитать, почти 10 000 лет!

Вам, быть может, кажется невероятным, чтобы 10 че-ловек могли размещаться таким большим числом раз-личных способов. Проверьте расчет сами.

Раньше всего надо научиться определять число пере-становок. Для простоты начнем вычисление с небольшого числа предметов - с трех. Назовем их А, Б и В.

Мы желаем узнать, сколькими способами возможно переставлять их один на место другого. Рассуждаем так

 

Image

 

 

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

Теперь будем присоединять вещь В к каждой из этих пар. Мы можем сделать это трояко: можем

1)  поместить В позади пары,

2)                 »         В впереди пары,

3)                 »         В м е ж д у   обеими вещами.

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

2X3=6.

Способы эти показаны на рис. 56.

Пойдем дальше - сделаем расчет для 4 вещей.

 

Image

 

 

Пусть у нас 4 вещи: А, Б, В и Г. Опять отложим пока в сторону одну вещь, например Г, а с остальными тремя сделаем все возможные перестановки. Мы знаем уже, что число этих перестановок - 6. Сколькими же способами можно присоединить четвертую вещь Г к каждой из 6 троек? Очевидно, четырьмя: можно

1) поместить Г позади тройки;

2)                             »          Г в п е р е д и   тройки;

3)                             »          Г между 1-й и 2-й вещью;

4)                             »           Г между 2-й и 3-й вещью.

Всего получим, следовательно,

6x4=24   перестановки;

а так как 6=2x3, а 2=1x2, то число всех перестановок можно представить в виде произведения:

1X2X3X4=24.

Рассуждая таким же образом и в случае 5 предметов, узнаем, что для них число перестановок равно:

1X2X3X4X5=120.

Для 6 предметов:

1X2X3X4X5X6=720  и т.  д.

Обратимся теперь к случаю с 10 обедающими. Число возможных  здесь перестановок  определится,  если себе труд вычислить произведение

1x2x3x4x5x6x7x8x9x10. Тогда и получится указанное выше число 3 628 800.

Расчет был бы сложнее, если бы среди 10 обедающих было 5 девушек, и они желали бы сидеть за столом не­пременно так, чтобы чередоваться с юношами. Хотя число возможных перемещений здесь гораздо меньше, вычислить его несколько труднее.

Пусть сядет за стол - безразлично как - один из юношей. Остальные четверо могут разместиться, остав­ляя между собою пустые стулья для девушек, 1* 2 * 3* 4= =24 различными способами. Так как всех стульев 10, то первый юноша может сесть 10 способами; значит число всех возможных размещений для молодых людей 10*24=240.

Сколькими же способами могут сесть на пустые стулья между юношами 5 девушек? Очевидно, 1x2x3x4x5=120 способами. Сочетая каждое из 240 положений юношей о каждым из 120 положений девушек, получаем число всея возможных размещений:

240x120=28 800.

Число это во много раз меньше предыдущего и потре­бовало бы всего 79 лет (без малого). Доживи молодые посетители ресторана до столетнего возраста, они могли бы дождаться бесплатного обеда, если не от самого офи­цианта,  то от его наследников.

Умея подсчитывать перестановки, мы можем опреде­лить теперь, сколько различных расположений шашек возможно в коробке игры «в 15» *). Другими словами, мы можем подсчитать число всех задач, какие способна предложить нам эта игра. Легко понять, что подсчет сво­дится к определению числа перестановок из 15 предметов. Мы знаем уже, что для этого нужно перемножить

1Х2ХЗХ4Х...Х14Х15. Вычисление дает итог:

1 307 674 365 000,

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

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

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

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

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

 

*) Впрочем, приближенно это вычисление может быть выполнено сравнительно несложно. В математике часто встречается необходимость вычислить произведенмие всех целых чисел от 1 до некоторого числа п. Это произведение обозначают символом п\ и называют «n-факториал». Например, выписанное выше произведе­ние коротко обозначается как 25!. В XVIII веке английский мате­матик С т и р л и н г  установил формулу, позволяющую прибли­женно вычислять факториалы. Эта формула имеет вид

 

Image

 

где

Image

- пекоторые числа, играющие важную

роль в разных вопросах математики. Пользуясь таблицами логариф­мов, по формуле Стирлинга легко получить:

 

Image

 

монету,   выше - 20-копеечную,   далее   15-копеечную   и на самый верх - 10-копеечную.

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

Я принялся перекладывать. Положил 10-копеечную монету на третье блюдце, 15-копеечную на среднее и зап­нулся. Куда положить 20-копеечную? Ведь она крупнее и 10-копеечной и 15-копеечной.

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

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

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

-   Не  считал.

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

-   Три:  10-копеечную на среднее блюдце,  15-копееч­ную - на третье и затем 10-копеечную на третье блюдце.

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

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

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

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

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

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

3=2x2-1

7=2x2x2-1 15=2x2x2x2-1 31 = 2x2x2x2x2-1.

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

2x2x2x2x2x2x2-1 = 128-1 = 127.

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

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

-   Нет, я только применил ее к монетам. Игра очень древнего происхождения и зародилась, говорят, в Индии. Существует интересная легенда, связанная с этой игрой. В  городе  Бенаресе  будто  бы имеется храм,  в  котором индусский  бог  Брама  при  сотворении  мира   установил три алмазные палочки и надел на одну из них 64 золотых кружка:   самый  большой  внизу,   а   каждый  следующий
меньше предыдущего. Жрецы храма обязаны без устали, днем и ночью, перекладывать эти кружки с одной палочки на другую,  пользуясь третьей,  как вспомогательной, и соблюдая правила нашей игры; переносить за один раз только один кружок и не класть большего на меньший. Легенда говорит, что когда будут перенесены все 64 круж­ка, наступит конец мира.

Image

 

 

 

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

 

-            О, значит, мир давно уже должен был погибнуть, если верить этому преданию!

-            Ты думаешь, кажется, что перенесение 64 кружков не должно отнять много времени?

-            Конечно. Делая каждую секунду один ход, можно ведь в час успеть проделать 3600 перенесений.

-            Ну и что же?

-            А  в  сутки - около  ста  тысяч.   В  десять дней - миллион ходов. Миллионом же ходов можно, я уверен, перенести хоть тысячу кружков.

-            Ошибаешься.   Чтобы  перенести всего 64 кружка, нужно уже круглым счетом 500 миллиардов лет!

-            Но  почему это?   Ведь число  ходов   равно  только произведению 64 двоек без единицы, а это составляет... Погоди, я сейчас перемножу!

-            Прекрасно.   А   пока   будешь   умножать,   я   успею
сходить   по   своим   делам.

И брат ушел, оставив меня погруженным в выкладки. Я нашел сначала произведение 16 двоек, затем умножил этот результат - 65 536 - сам на себя, а то, что получи­лось,- снова на себя. Потом не забыл отнять единицу.

У меня получилось такое число:

18 446 744 073 709 551 615 *).

Брат,   значит,   был   прав...

Вам, вероятно, интересно было бы знать, какими чис­лами в действительности определяется возраст мира. Ученые располагают на этот счет некоторыми,- конечно, лишь приблизительными - данными:

Солнце существует     5 000 000 000 000 лет.

Земной шар...............          3000000000    » .

Жизнь на Земле........          1 000 000 000    » .

Человек..............                не менее 500 000    »  .

 
« Пред.   След. »
Яндекс.Метрика