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

Условие
Два древних шамана сошлись в ритуальном состязании! Перед ними лежит священный сосуд с 16 магическими камнями четырёх стихий:
- 4 камня духа земли
- 4 камня духа огня
- 4 камня духа воды
- 4 камня духа ветра

Правила испытания:
1) Шаманы по очереди берут по одному камню случайной стихии (старший шаман начинает).
2) Когда у одного из шаманов окажется 3 камня одной стихии — его дух пробуждается, и он объявляется победителем!
3) Камни после вытягивания не возвращаются в священный сосуд.

Вопрос мудрецам:
Какова вероятность, что ритуал завершится пробуждением духа?

Решение
Давайте построим вероятностную модель:
множество всех исходов — это случайная перестановка всех 16 камней, то есть упорядоченный список вида (камень 1, камень 2, …, камень 16).

Перед началом ритуала порядок неизвестен и равновероятен, то есть любая из 16! перестановок возможна

1) Как раздаются камни
По ходу игры шаманы "открывают" этот список поочередно:
старший берёт 1-й, 3-й, 5-й, ..., 15-й камни (всего 8)
младший берёт 2-й, 4-й, 6-й, ..., 16-й (всего 8)
следовательно, множество камней старшего — это равновероятное 8 элементное подмножество из 16

таких подмножеств C из 16 по 8 = 12 870

2) Посчитаем вероятность ничьей
Ритуал завершится пробуждением духа, когда у одного из шаманов соберётся 3 камня одной стихии. Значит ничья будет в том случае, когда у обоих шаманов будет не больше двух камней каждой стихии.
Камней каждой стихии по 4 штуки и шаманы берут камни пока они не закончатся. Значит ничья возможна только при таком раскладе:

у младшего: 2 земли, 2 огня, 2 воды, 2 ветра
у старшего: 2 земли, 2 огня, 2 воды, 2 ветра

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

3) Посчитаем количество способов получить 2 земли, 2 огня, 2 воды, 2 ветра

У нас все камни внутри одной стихии разные. Мы выбираем 2 из 4 камней огня, 2 из 4 камней земли, 2 из 4 камней воды, 2 из 4 камней ветра

(C из 4 по 2)^4 = 6^4 = 1 296

4) Итог
Вероятность ничьей: P = 1 296/12 870= 72/715
Вероятность пробуждения духа: 1 - P = 643/715 = 0.9

@ProdAnalysis