Задача про джуниоров и стартап
hard

Задача про джуниоров и стартап

В один перспективный стартап одновременно взяли шесть джуниоров. Каждый месяц каждый из джуниоров может стать мидлом с вероятностью 1/2. Если повышение состоялось, оно уже не имеет обратной силы. Через сколько месяцев в среднем можно ожидать, что все шесть джуниоров станут мидлами?

Это задача про вероятности, поэтому вспомним основное:

Вероятность наступления какого-то события равна отношению количества нужных нам событий к общему количеству событий.

Например, вероятность выкинуть кубик с чётным числом очков считается так:

  1. Всего чётных граней на кубике — 3.
  2. Всего граней на кубике, которые могут выпасть при броске — 6.
  3. Вероятность выкинуть кубик с чётной гранью наверху будет равна 3 / 6 = ½
  4. Это значит, что с вероятностью 50% мы выкинем нужный нам результат при одном броске.

Теперь вернёмся к задаче.

Обозначим за Ах количество месяцев, которые должны пройти до того, как все джуны станут мидлами, где х — количество мидлов. В нашем случае у нас должно стать 6 мидлов, поэтому х = 6. Нам надо найти А0 — стартовую точку, которая покажет нам, сколько месяцев должно пройти, прежде чем все 6 станут мидлами.

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

Когда все джуны стали мидлами, это ситуация А6 — у нас 6 мидлов, а значит, 0 джунов. Получается, что А6 = 0, потому что все уже стали мидлами и не нужно ждать очередного месяца.

Теперь шагнём назад и посмотрим на ситуацию А5, когда у нас 5 мидлов и 1 джун. Вероятность того, что у нас через месяц джун станет мидлом — ½, либо станет, либо нет (и мы останемся в состоянии А5). Это значит, что количество месяцев, которое пройдёт, прежде чем этот джун станет мидлом равна:

А5 = 1 + ½ × А6 + ½ × А5, а единица здесь отвечает за месяц, который должен пройти, прежде чем любой джун станет мидлом.

 

Решим это уравнение. Мы выяснили, что А6 = 0, поэтому:

А5 = 1 + 0 + ½ × А5

А5 = 1 + ½ × А5 → А5 = 2

Откатимся ещё назад и посчитаем ожидаемое количество месяцев, до финала, когда у нас 4 мидла и 2 джуна — это А4. Сейчас распишем подробно решение, чтобы была понятна логика на следующих этапах.

У нас 2 джуна, каждый из которых может стать мидлом (а может и не стать). Получается, у нас 4 исхода месяца:

  1. Оба стали мидлами.
  2. Первый стал, а второй нет.
  3. Первый не стал, а второй стал.
  4. Оба не стали джунами (всё осталось как и было).

Зная это, получим формулу:

А4 = 1 (прошёл месяц) + ¼ × А6 (оба стали мидлами) + 2/4 × А5 (один стал, а другой нет) + ¼ × А4 (оба не стали)

А4 = 1 + ¼ × А6 + 2/4 × А5 + ¼ × А4 ← подставим сюда уже известные значения А6 и А5

А4 = 1 + 0 + ½ × 2 + ¼ × А4

А4 = 8/3

Откатимся снова и получим ситуацию, когда у нас 3 мидла и 3 джуна — это ситуация А3. Всего у нас может быть 8 исходов, когда кто-то становится мидлом, а кто-то нет (2³ = 8) и 4 возможных исхода:

  1. Все стали сразу мидлами — вероятность ⅛, и переходим в ситуацию А6.
  2. Двое из трёх стали мидлами — вероятность ⅜, и переходим в ситуацию А5.
  3. Один из трёх стал мидлом — вероятность ⅜, и переходим в ситуацию А4.
  4. Никто не стал мидлом — вероятность ⅛, и остаёмся в ситуации А3.

Запишем это в виде уже привычной формулы:

А3 = 1 + ⅛ × А6 + ⅜ × А5 + ⅜ × А4 + ⅛ × А3

Подставим уже известные значения А6, А5 и А4 и получим значение А3:

А3 = 22/7

Снова откатываемся назад и смотрим на ситуацию А2, когда у нас 2 мидла и 4 джуна. Теперь у нас 2⁴ = 16 возможных ситуаций и 5 разных исходов:

  1. Все стали мидлами — вероятность 1/16, и переходим в ситуацию А6
  2. Трое стали мидлами — вероятность 4/16, и переходим в ситуацию А5.
  3. Двое стали мидлами — вероятность 6/16, и переходим в ситуацию А4.
  4. Один стал мидлом — вероятность 4/16, и переходим в ситуацию А3.
  5. Никто не стал мидлом — вероятность 1/16, и остаёмся в ситуации А2.

Составим формулу для А2 и потом подставим уже известные значения А6 — А3:

А2 = 1 + 1/16 × А6 + 4/16 × А5 + 6/16 × А4 + 4/16 × А3 + 1/16 × А2

А2 = 368/105

Откатимся ещё на шаг назад и посмотрим на ситуацию А1, когда у нас 1 мидл и 5 джунов. Здесь 2⁵ = 32 возможных ситуаций и 6 возможных ситуаций:

  1. Все стали мидлами — вероятность 1/32 → А6.
  2. Четверо стали мидлами — вероятность 5/32 → А5.
  3. Трое стали мидлами — вероятность 10/32 → А4.
  4. Двое стали мидлами — вероятность 10/32 → А3.
  5. Один стал мидлом — вероятность 5/32 → А2.
  6. Никто не стал мидлом — вероятность 1/32, и остаёмся в ситуации А1.

Составим формулу для А1 и потом подставим уже известные значения А6—А2:

А1 = 1 + 1/32 × А6 + 5/32 × А5 + 10/32 × А4 + 10/32 × А3 + 5/32 × А2 + 1/32 × А1

А1 = 2470/651

И наконец, откатимся до стартового условия, когда у нас 0 мидлов и 6 джунов — то, что нам и нужно найти. Здесь 2⁶ = 64 возможных ситуации и 7 возможных исходов:

  1. Все стали мидлами → вероятность 1/64 → А6.
  2. Пятеро стали мидлами → вероятность 6/64 → А5.
  3. Четверо стали мидлами → вероятность 15/64 → А4.
  4. Трое стали мидлами → вероятность 20/64 → А3.
  5. Двое стали мидлами → вероятность151/64 → А2.
  6. Один стал мидлом → вероятность 6/64 → А1.
  7. Никто не стал мидлом → вероятность 1/64 → остаёмся в ситуации А0.

Составим формулу для А0 и потом подставим уже известные значения А6—А1:

А0 = 1 + 1/64 × А6 + 6/64 × А5 + 15/64 × А4 + 20/64 × А3 + 15/64 × А2 + 6/64 × А1 + 1/64 × А0

А0 = 7880/1953 ≈ 4,03

Получается, что ожидаемое время, когда все 6 джунов станут мидлами — 4,03 месяца. Но так как повышение происходит каждый месяц, нужно округлить до 5. Но это не значит, что через 5 месяцев все ТОЧНО станут мидлами — это лишь среднее значение вероятности, что скорее всего это произойдёт через это время.

Уф. Решили. Вы — крутые, если дочитали досюда.

Обложка:

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

Корректор:

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

Вёрстка:

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

Соцсети:

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

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