Задача: сто программистов и повышение или увольнение для всех
easy

Задача: сто программистов и повышение или увольнение для всех

Все либо выиграют, либо проиграют

В одной большой ИТ-компании работает сто программистов. В закрытой комнате в ста пронумерованных коробках случайным образом размещены карточки с номерами от 1 до 100. Программисты могут зайти в комнату по одному и открыть 50 коробок в поисках своего номера. После того как номер найден или открыта 50-я коробка, программист должен покинуть комнату.

Если свои номера найдут все сто программистов, их всех повысят. Но если хотя бы один из них не сможет найти свой номер, будут уволены все сто программистов.

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

Если программисты будут искать свой номер бессистемно, вероятность успеха каждого из них составит 50%. Тогда вероятность, что все найдут свои номера, будет слишком мала:

В = (1/2)100 = 1/1267650600228229401496703205376 = 0,0000000000000000000000000000008

Но что, если все программисты договорятся открывать коробки, начиная со своего номера и до тех пор, пока не найдут карточку, которая будет вести на исходную коробку? Представим, что в комнату вошёл программист с номером 50 и ищет свой номер таким образом:

  1. Открывает первой коробку №50, в ней номер 99.
  2. Открывает коробку №99, в ней номер 69.
  3. Открывает коробку №69, в ней номер 97.
  4. Открывает коробку №97, в ней номер 22.
  5. Открывает коробку №22, в ней номер 2.
  6. Открывает коробку №2, в ней номер 39.
  7. Открывает коробку №39, в ней номер 3.
  8. Открывает коробку №3, в ней номер 15.
  9. Открывает коробку №15, в ней номер 57.
  10. Открывает коробку №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

Подойдём к процессу открывания коробок с другой стороны:

  1. При первом открывании мы выбираем из 100 коробок.
  2. При втором — из 99.
  3. При третьем — из 98.
  4. При сотом открывании — из 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.

Обложка:

Алексей Сухов

Корректор:

Ирина Михеева

Вёрстка:

Маша Климентьева

Соцсети:

Юлия Зубарева

Любите такие задачи? Подойдите поближе
Внизу кнопка, при нажатии на нее вы попадете на витрину курсов «Практикума» с нуля. Выбираете там то, что вам близко, и погружаетесь в профессию. Через год-полтора вы работаете в какой-нибудь ИТ-компании. И там вы решаете подобные задачи, но уже за деньги. Старт бесплатно.
Начать бесплатно
Любите такие задачи? Подойдите поближе Любите такие задачи? Подойдите поближе Любите такие задачи? Подойдите поближе Любите такие задачи? Подойдите поближе
Получите ИТ-профессию
В «Яндекс Практикуме» можно стать разработчиком, тестировщиком, аналитиком и менеджером цифровых продуктов. Первая часть обучения всегда бесплатная, чтобы попробовать и найти то, что вам по душе. Дальше — программы трудоустройства.
Начать карьеру в ИТ
Получите ИТ-профессию Получите ИТ-профессию Получите ИТ-профессию Получите ИТ-профессию
Еще по теме
easy