В одной большой ИТ-компании работает сто программистов. В закрытой комнате в ста пронумерованных коробках случайным образом размещены карточки с номерами от 1 до 100. Программисты могут зайти в комнату по одному и открыть 50 коробок в поисках своего номера. После того как номер найден или открыта 50-я коробка, программист должен покинуть комнату.
Если свои номера найдут все сто программистов, их всех повысят. Но если хотя бы один из них не сможет найти свой номер, будут уволены все сто программистов.
Посетив комнату, программисты не могут общаться с теми, кто в ней ещё не был. Но они могут обсуждать общую стратегию до того, как попадут в комнату. Какая стратегия поисков будет наилучшей, чтобы всех программистов повысили, а не уволили?
Если программисты будут искать свой номер бессистемно, вероятность успеха каждого из них составит 50%. Тогда вероятность, что все найдут свои номера, будет слишком мала:
В = (1/2)100 = 1/1267650600228229401496703205376 = 0,0000000000000000000000000000008
Но что, если все программисты договорятся открывать коробки, начиная со своего номера и до тех пор, пока не найдут карточку, которая будет вести на исходную коробку? Представим, что в комнату вошёл программист с номером 50 и ищет свой номер таким образом:
- Открывает первой коробку №50, в ней номер 99.
- Открывает коробку №99, в ней номер 69.
- Открывает коробку №69, в ней номер 97.
- Открывает коробку №97, в ней номер 22.
- Открывает коробку №22, в ней номер 2.
- Открывает коробку №2, в ней номер 39.
- Открывает коробку №39, в ней номер 3.
- Открывает коробку №3, в ней номер 15.
- Открывает коробку №15, в ней номер 57.
- Открывает коробку №57, в ней номер 50 — номер самого программиста.
В таком случае вероятность, что все программисты найдут свои номера, вырастет до 0,31. Но почему? Сейчас объясним.
Дело в том, что номера всех программистов в пронумерованных коробках образуют какую-то зацикленную последовательность (или несколько последовательностей, но об этом позже). Простейший такой цикл может быть номером 1 в коробке №1:
Цикл чуть сложнее может состоять из двух объектов, например если в коробке №1 лежит номер 7, а в коробке №7 лежит номер 1:
Цикл может содержать три коробки, четыре и так далее. Такие зацикленные последовательности могут состоять из скольких угодно элементов. В случае с сотней коробок самая длинная последовательность может содержать их все:
Но гораздо вероятнее, что номера в сотне коробок образуют несколько зацикленных последовательностей: какие-то короче, а какие-то — длиннее:
Если открывать коробки в последовательности, при которой первая коробка будет иметь тот же номер, что и сам программист, а следующая — номер из предыдущей, есть вероятность рано или поздно найти коробку со своим номером внутри:
Но у нас есть ограничение: каждый программист может открыть только 50 коробок. Если номер программиста находится в 53-й коробке в зацикленной последовательности, программист просто не доберётся до этой коробки за отведённое число открываний.
Из этого следует, что вероятность того, что все программисты найдут свои номера по выбранной стратегии, зависит от того, есть ли в нашем множестве коробок такие последовательности, в которых 51 коробка или более. Эта вероятность равняется ⅓, но давайте в этом убедимся.
Мы можем представить зацикленную последовательность из ста коробок так:
№1 → №2 → №3 → №4 → … → №100 → №1
Но вероятнее, что последовательность будет примерно такой:
№5 → №99 → №51 → №17 → … → №63 → №5
Подойдём к процессу открывания коробок с другой стороны:
- При первом открывании мы выбираем из 100 коробок.
- При втором — из 99.
- При третьем — из 98.
… - При сотом открывании — из 1.
Получается, что общее количество вариантов перестановок номеров в коробках будет таким:
100 × 99 × 98 × … × 1 = 100!
Значит, для ста коробок у нас есть 100! вариантов образования зацикленной последовательности. При этом многие варианты фактически включают друг друга, потому что наши зацикленные последовательности имеет вид не прямых, а кругов. Например, вот эти две последовательности — одна и та же последовательность:
№5 → №99 → №51 → №17 → … → №63 → №5
№99 → №51 → №17 → … → №63 → №5 → №99
Получается, что количество уникальных зацикленных последовательностей будет равно 100!/100. Тогда вероятность того, что зацикленная последовательность будет содержать 100 коробок, можно вычислить так:
В(ЗП=100) = количество уникальных ЗП / количество перестановок = (100!/100)/100! = 1/100
Для 99 коробок вероятность будет 1/99, для 98 — 1/98 и так далее. Чтобы вычислить вероятность того, что номера в ста коробках составляют зацикленные последовательности из 50 элементов, сложим вероятности того, что эти последовательности больше: 1/51 + 1/52 + 1/53 + 1/54 … + 1/100. Получится вероятность 0,69%.
Тогда получается, что вероятность того, что номера в ста коробках образуют зацикленные последовательности из 50 и менее элементов — 0,31%:
1 — 0,69 = 0,31
И хотя 0,31 — это не так много, всё же это намного больше, чем 0,0000000000000000000000000000008.
