Что вижу - о том пою (aragont) wrote,
Что вижу - о том пою
aragont

Category:

Может ли миллион обезьян напечатать число Пи?

Математики утверждают, что число Пи состоит из бесконечного числа цифр, последовательность которых нельзя отличить от случайных. Под случайностью подразумевают, что взяв любой достаточно длинный кусок числа Пи, мы найдём в нём будет одинаковое количество нулей, единиц, двоек, ..., девяток. Более того, в нём будет одинаковое количество пар (00, 01,...,10, 11, ...,99), троек и дальше со всеми остановками.

При таком раскладе, внутри бесконечного числа Пи можно найти любое конечное число. Обычному человеку искать числа в числе не очень интересно, но можно закодировать числами какой-нибудь текст. Поскольку Пи обычно записывают десятичными цифрами, то можно использовать следующий код: 00 - пробел, 01 - "а", 02 - "б", 33 - "я", а дальше запятая, тире, кавычки и, если надо, латиница.

Например, если мы возьмём "Войну и мир" Толстого, то она содержит примерно три миллиона букв. В нашей записи это будет число длинной в шесть миллионов цифр, которое (наравне с остальными числами) находится где-то внутри Пи.

Недавно на каком-то форуме мне попалась фраза: Какая польза от "Войны и мира" внутри Пи, если начало этой книги будет выражаться бесконечно большим числом?

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

Шесть миллионов не так и много. Википедия утверждает, что в 2019 году число Пи было посчитано с точностью 31,4 триллионов знаков после запятой. На сайте http://3.141592653589793238462643383279502884197169399375105820974944592.com можно скачать первый миллион цифр, правда там придётся решить не очень сложную (для программиста) загадку.

Теперь вернёмся к "Войне и миру". Нормальный математический вопрос будет звучать так: Сколько цифр числа Пи надо просмотреть, чтобы с вероятностью 50% найти в них "Войну и мир"? (Другая формулировка: Сколько времени потребуется миллиону неграмотных обезьян, чтобы напечатать "Войну и мир"?) Формально это звучит так: какова вероятность найти в строке случайных десятичных цифр длиной n, заранее известную подстроку длиной k?

Точная формула у меня получилась не очень красивой, поэтому я чуть-чуть завышу оценку.

Всего существует 10n чисел длиной n десятичных цифр (короткие дополняются нулями слева). Подстрока длиной k может начинаться в n-k+1 позициях. Каждой начальной позиции искомой подстроки соответствует 10n-k сочетаний остальных цифр.

Соответственно, искомая (завышенная) вероятность выглядит так:

p = (n-k+1)*10n-k/10n = (n-k+1)/10k

Завышенность получается из того, что если подстрока встречается в строке несколько раз, то я считаю каждое вхождение за отдельный случай. Например: какова вероятность того, что в случайной паре цифр встретится тройка? Правильный ответ 19/100, а моя формула даёт 2/10 поскольку я дважды считаю 33 - один раз как 3x, а второй, как x3.

В соответствии с выведенной формулой, чтобы получить 50% вероятности найти "Войну и мир" в числе Пи нам придётся просмотреть более чем n = 0.5*106000000+6000000-1 знаков.

106000000 это довольно заметное число, особенно если вспомнить, что число атомов во вселенной оценивается как 1081. Единственное что утешает, это то, что любую другую книгу соответствующей длины мы так же сможем найти в этих цифрах с вероятностью 50%.

З.Ы.
Формула вероятности также даёт ответ на вопрос: Может ли миллион обезьян напечатать число Пи?
Ответ: Может, но вероятность этого равна нулю, поскольку это предел функции k/10k при k стремящимся к бесконечности.

З.З.Ы.
Длина адреса начала "Войны и мира" в числе Пи сравнима с длиной "Войны и мира".
Tags: математика
Subscribe

  • Кошачий переполох

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

  • Театр теней

    Точечные светодиодные лампы дают отличные тени. Уже наснимал полсотни кадров разной ерунды.

  • Как ловят тигров

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

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 0 comments