Sunday, August 11, 2013

Перельман. Живая математика. Пари.

столовой дома отдыха зашла за обедом речь о том, как вычисляется вероятность событий. Молодой математик, оказавшийся среди обедающих, вынул монету и сказал:

— Кидаю на стол монету, не глядя. Какова вероятность, что она упадёт гербом вверх?

— Объясните сначала, что значит «вероятность»,— раздались голоса.— Не всем ясно.

— О, это очень просто! Монета может лечь на стол двояко (рис. 58): вот так — гербом вверх и вот так — гербом вниз.

Всех случаев здесь возможно только два. Из них для интересующего нас события благоприятен лишь один случай. Теперь находим отношение
числа благоприятных случаев / к числу возможных случаев = 1/2

Дробь $\frac{1}{2}$ и выражает «вероятность» того, что монета упадёт гербом вверх.

Ниже есть продолжение.

— С монетой-то просто,— вмешался кто-то.— А вы рассмотрите случай посложней, с игральной костью, например.

— Давайте, рассмотрим,— согласился математик.— У нас игральная кость, кубик с цифрами на гранях Какова вероятность, что брошенный кубик упадёт определённой цифрой вверх, скажем — вскроется шестёркой? Сколько здесь всех возможных случаев? Кубик может лечь на любую из своих шести граней; значит, возможно всего 6 случаев. Из них благоприятен нам только один: когда вверху шестёрка. Итак, вероятность получится от деления 1 на 6. Короче сказать, она выражается дробью $\frac{1}{6}$
— Неужели можно вычислить вероятность во всех случаях? — спросила одна из отдыхающих.— Возьмите такой пример. Я загадала, что первый прохожий, которого мы увидим из окна столовой, будет мужчина. Какова вероятность, что я отгадала?

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

— А какова вероятность, что первые двое прохожих окажутся оба мужчины? — спросил один из отдыхающих.
— Этот расчёт немногим сложнее. Перечислим, какие здесь вообще возможны случаи. Во-первых, возможно, что оба прохожих будут мужчины. Во-вторых, что сначала покажется мужчина, за ним женщина. В-третьих, наоборот: что раньше появится женщина, потом мужчина. И, наконец, четвёртый случай: оба прохожих — женщины. Итак, число всех возможных случаев — 4. Из них благоприятен, очевидно, только один случай — первый. Получаем для вероятности дробь $\frac{1}{4}$ Вот ваша задача и решена.

— Понятно. Но можно поставить вопрос и о трёх мужчинах: какова вероятность, что первые трое рохожих все окажутся мужчины?

— Что же, вычислим и это. Начнём опять с подсчёта возможных случаев. Для двоих прохожих число всех случаев равно, мы уже знаем, четырём. С присоединением третьего прохожего число возможных случаев увеличивается вдвое, потому что к каждой из 4 перечисленных группировок двух прохожих может присоединиться либо мужчина, либо женщина. Итого, всех случаев возможно здесь 4×2=8. А искомая вероятность, очевидно, равна $\frac{1}{8}$, потому что благоприятен событию только 1 случай. Здесь легко подметить правило подсчёта: в случае двух прохожих мы имели вероятность $\frac{1}{2}*\frac{1}{2}=\frac{1}{4}$, в случае трёх $\frac{1}{2}*\frac{1}{2}*\frac{1}{2}=\frac{1}{8}$ ; в случае четырёх вероятность равна произведению четырёх половинок и т. д. Вероятность всё уменьшается, как видите.

— Чему же она равна, например, для десятка прохожих?

— То есть какова вероятность, что первые десять прохожих все подряд окажутся мужчинами? Вычислим, как велико произведение десяти половинок. Это $\frac{1}{1024}$, менее одной тысячной доли. Значит, если вы бьётесь о заклад, что это случится, и ставите 1 рубль, то я могу ставить 1000 рублей за то, что этого не произойдёт.
— Выгодное пари! — заявил чей-то голос.— Я бы охотно поставил рубль, чтобы получить возможность выиграть целую тысячу.

— Но имеется тысяча шансов против вашего одного, учтите и это.

— Ничего не значит. Я бы рискнул рублём против тысячи даже и за то, что сотня прохожих окажутся все подряд мужчинами.

— А вы представляете себе, как мала вероятность такого события? — спросил математик.

— Одна миллионная или что-нибудь в этом роде?

— Неизмеримо меньше! Миллионная доля получится уже для 20 прохожих. Для сотни прохожих будем иметь… Дайте-ка, я прикину на бумажке. Биллионная… Триллионная… Квадрильонная… Ого! Единица с тридцатью нулями!

— Только всего?

— Вам мало 30 нулей? В океане нет и тысячной доли такого числа мельчайших капелек.

— Внушительное число, что и говорить! Сколько же вы поставите против моего рубля?

— Ха-ха!… Все! Все, что у меня есть.

— Все — это слишком много. Ставьте на кон ваш велосипед. Ведь не поставите?

— Почему же нет? Пожалуйста! Пусть велосипед, если желаете. Я нисколько не рискую.

— И я не рискую. Не велика сумма рубль. Зато могу выиграть велосипед, а вы почти ничего.

— Да поймите же, что вы наверняка проиграете! Велосипед никогда вам не достанется, а рубль ваш можно сказать уже в моём кармане.

— Что вы делаете!— удерживал математика приятель.— Из-за рубля рискуете велосипедом. Безумие!

— Напротив,— ответил математик,— безумие ставить хотя бы один рубль при таких условиях. Верный ведь проигрыш! Уже лучше прямо выбросить рубль.

— Но один-то шанс все же имеется?

— Одна капля в целом океане. В десяти океанах! Вот ваш шанс. А за меня десять океанов против одной капельки. Мой выигрыш так же верен, как дважды два — четыре.

— Увлекаетесь, молодой человек,— раздался спокойный голос старика, все время молча слушавшего спор.— Увлекаетесь…

— Как? И вы, профессор, рассуждаете по-обывательски?

— Подумали ли вы о том, что не все случаи здесь равновозможны? Расчёт вероятности правилен лишь для каких событий? Для равновозможных, не так ли? А в рассматриваемом примере… Впрочем,— сказал старик, прислушиваясь,— сама действительность, кажется, сейчас разъяснит вам вашу ошибку. Слышна военная музыка, не правда ли?

— Причём тут музыка?..— начал было молодой математик и осекся. На лице его выразился испуг. Он сорвался с места, бросился к окну и высунул голову.

— Так и есть! — донёсся его унылый возглас.— Проиграно пари! Прощай мой велосипед…

Через минуту всем стало ясно, в чем дело. Мимо окон проходил батальон солдат.
http://ru.wikisource.org/wiki/Живая_математика_(Перельман)/Глава_7

Перельман. Живая математика. Перекладывание монет.

или Ханойская башня.

В детстве старший брат показал мне, помню. занимательную игру с монетами. Поставив рядом три блюдца, он положил в крайнее блюдце стопку из 5 монет: вниз рублёвую, на неё — 50-копеечную монету, выше — 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 = 2×2-1
7 = 2×2×2-1
15 = 2×2×2×2-1
31 = 2×2×2×2×2-1.

— Понимаю: сколько монет перекладывается, столько раз берётся двойка множителем, а затем отнимается единица. Я мог бы теперь вычислить число ходов для любой стопки монет. Например, для 7 монет:
2 × 2 × 2 × 2 × 2 × 2 × 2 — 1 = 128 — 1 = 127.

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

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

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

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

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

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

— Ну и что же?

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

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

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

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

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

У меня получилось такое число:
18 446 744 073 709 551 615 [Читателю уже знакомо это число: оно определяет награду, затребованную изобретателем шахматной игры.]

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

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

Учёные располагают на этот счёт некоторыми,— конечно, лишь приблизительными — данными:
Солнце существует 5 000 000 000 000 лет.
Земной шар 3000000 000 лет.
Жизнь на Земле 1 000 000 000 лет.
Человек не менее 500 000 лет.
http://ru.wikisource.org/wiki/Живая_математика_(Перельман)/Глава_7

Перельман. Живая математика. Легенда о шахматной доске

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

Одну из подобных легенд я и хочу рассказать. Чтобы понять её, не нужно вовсе уметь играть в шахматы: достаточно знать, что игра происходит на доске, разграфлённой на 64 клетки (попеременно чёрные и белые).

Ниже есть продолжение.

1.

Шахматная игра была придумана в Индии, и когда индусский царь Шерам познакомился с нею, он был восхищён её остроумием и разнообразием возможных в ней положений.

Узнав, что она изобретена одним из его подданных, царь приказал его позвать, чтобы лично наградить за удачную выдумку.

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

— Я желаю достойно вознаградить тебя, Сета, за прекрасную игру, которую ты придумал,— сказал царь.

Мудрец поклонился.

— Я достаточно богат, чтобы исполнить самое смелое твоё пожелание,— продолжал царь.— Назови награду, которая тебя удовлетворит, и ты получишь её.
Рис. 53. «За вторую клетку прикажи выдать два зерна».

Сета молчал.

— Не робей,— ободрил его царь— Выскажи своё желание. Я не пожалею ничего, чтобы исполнить его.

— Велика доброта твоя, повелитель. Но дай срок обдумать ответ. Завтра, по зрелом размышления, я сообщу тебе мою просьбу.

Когда на другой день Сета снова явился к ступеням трона, он удивил царя беспримерной скромностью своей просьбы.

— Повелитель,— сказал Сета,— прикажи выдать мне за первую клетку шахматной доски одно пшеничное зерно.

— Простое пшеничное зерно? — изумился царь.

— Да, повелитель. За вторую клетку прикажи выдать 2 зерна, за третью 4, за четвёртую — 8, за пятую — 16, за шестую — 32...

— Довольно,— с раздражением прервал его царь.— Ты получишь свои зерна за все 64 клетки доски, согласно твоему желанию: за каждую вдвое больше против предыдущей. Но знай, что просьба твоя недостойна моей щедрости. Прося такую ничтожную награду, ты непочтительно пренебрегаешь моею милостью. Поистине, как учитель, ты мог бы показать лучший пример уважения к доброте своего государя. Ступай. Слуги мои вынесут тебе твой мешок с пшеницей.

Сета улыбнулся, покинул залу и стал дожидаться у ворот дворца.

2.

За обедом царь вспомнил об изобретателе шахмат и послал узнать, унёс ли уже безрассудный Сета свою жалкую награду.

— Повелитель,— был ответ,— приказание твоё исполняется. Придворные математики исчисляют число следуемых зёрен.

Царь нахмурился. Он не привык, чтобы повеления его исполнялись так медлительно.

Вечером, отходя ко сну, царь ещё раз осведомился, давно ли Сета со своим мешком пшеницы покинул ограду дворца.

— Повелитель,— ответили ему,— математики твои трудятся без устали и надеются ещё до рассвета закончить подсчёт.

— Почему медлят с этим делом? — гневно воскликнул царь.— Завтра, прежде чем я проснусь, всё до последнего зерна должно быть выдано Сете. Я дважды не приказываю.

Утром царю доложили, что старшина придворных математиков просит выслушать важное донесение.

Царь приказал ввести его.

— Прежде чем скажешь о твоём деле,— объявил Шерам,— я желаю услышать, выдана ли, наконец, Сете та ничтожная награда, которую он себе назначил.

— Ради этого я и осмелился явиться перед тобой в столь ранний час,— ответил старик.— Мы добросовестно исчислили всё количество зёрен, которое желает получить Сета. Число это так велико…

— Как бы велико оно ни было,— надменно перебил царь, житницы мои не оскудеют. Награда обещана и должна быть выдана…

— Не в твоей власти, повелитель, исполнять подобные желания. Во всех амбарах твоих нет такого числа зёрен, какое потребовал Сета. Нет его и в житницах целого царства. Не найдётся такого числа зёрен и на всём пространстве Земли. И если желаешь непременно выдать обещанную награду, то прикажи превратить земные царства в пахотные поля, прикажи осушить моря и океаны, прикажи растопить льды и снега, покрывающие далёкие северные пустыни. Пусть всё пространство их сплошь будет засеяно пшеницей. И все то, что родится на этих полях, прикажи отдать Сете. Тогда он получит свою награду.

С изумлением внимал царь словам старца.

— Назови же мне это чудовищное число,— сказал он в раздумьи.

— Восемнадцать квинтильонов четыреста сорок шесть квадрильонов семьсот сорок четыре триллиона семьдесят три биллиона семьсот девять миллионов пятьсот пятьдесят одна тысяча шестьсот пятнадцать, о повелитель!

3.

Такова легенда. Действительно ли было то, что здесь рассказано, неизвестно,— но что награда, о которой говорит предание, должна была выразиться именно таким числом, в этом вы сами можете убедиться терпеливым подсчётом.

Начав с единицы, нужно сложить числа: 1, 2, 4, 8 и т. д. Результат 63-го удвоения покажет, сколько причиталось изобретателю за 64-ю клетку доски.
[
1=20
2=21
4=22
8=23
...
1+2+4+8+...+2(64-1)=
=20+21+22+...24... +263=
=264-1
]

...Мы без труда найдём всю сумму следуемых зёрен, если удвоим последнее число и отнимем одну единицу. Значит, подсчёт сводится лишь к перемножению 64 двоек:
2 × 2 × 2 × 2 × 2 × 2 × и т. д. (64 раза).

Для облегчения выкладок разделим эти 64 множителя на 6 групп по 10 двоек в каждой и одну последнюю группу из 4 двоек. Произведение 10 двоек, как легко убедиться, равно 1024, а 4 двоек — 16. Значит, искомый результат равен
1024 × 1024 × 1024 × 1024 × 1024 × 1024 × 16.

Перемножив 1024×1024, получим 1 048 576.

Теперь остаётся найти:
1 048 576 × 1 048 576 × 1 048 576 × 16,

отнять от результата одну единицу — и нам станет известно искомое число зёрен:
18 446 744 073 709 551 615.

Если желаете представить себе всю огромность этого числового великана, прикиньте, какой величины амбар потребовался бы для вмещения подобного количества зёрен. Известно, что кубический метр пшеницы вмещает около 15 миллионов зёрен. Значит, награда шахматного изобретателя должна была бы занять объем примерно в 12 000 000 000 000 куб. м, или 12 000 куб. км. При высоте амбара 4 м и ширине 10 м длина его должна была бы простираться на 300 000 000 км,— т. е. вдвое дальше, чем от Земли до Солнца!..

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

В самом деле: если бы Сета, принявшись за счёт, вёл его непрерывно день и ночь, отсчитывая по зерну в секунду, он в первые сутки отсчитал бы всего 86 400 зёрен. Чтобы отсчитать миллион зёрен, понадобилось бы не менее 10 суток неустанного счета. Один кубический метр пшеницы он отсчитал бы примерно в полгода: это дало бы ему всего 5 четвертей. Считая непрерывно в течение 10 лет, он отсчитал бы себе не более 100 четвертей. Вы видите, что, посвятив счету даже весь остаток своей жизни, Сета получил бы лишь ничтожную часть потребованной им награды.
http://ru.wikisource.org/wiki/Живая_математика_(Перельман)/Глава_7