Сто коробок и общий шанс на победу — разбор задачи

Условие

В комнате $100$ коробок с номерами от $1$ до $100$ В них случайно, с равными шансами для всех перестановок, разложены карточки с теми же номерами, по одной в коробку. Сто участников по очереди заходят в комнату. Участник с номером $i$ может открыть не более $50$ коробок и должен найти карточку $i$ Затем всё возвращают в исходное состояние; оставлять знаки и передавать сведения нельзя. Команда выигрывает, только если каждый нашёл свой номер. До начала можно договориться о стратегии. Придумайте стратегию с вероятностью общего успеха больше $30\,\%$ и объясните эту оценку.

О задаче · Подростки и взрослые

Тема: Перестановки и вероятность
Для кого: Подростки и взрослые
Уровень библиотеки: Продвинутый · ориентир

Записать идею

Личный черновик для заметок и расчётов. Он никуда не отправляется и не проверяется.

Подсказка 1

Пусть найденный на карточке номер указывает, какую коробку открыть следующей. С какой коробки начать?

Подсказка 2

Любая перестановка распадается на замкнутые цепочки. Команда проиграет, если хотя бы одна такая цепочка слишком длинная.

Разобрать решение по шагам

Следуйте указателям

Участник $i$ начинает с коробки $i$ Если там карточка $j$ следующей открывает коробку $j$ и так далее. Поскольку каждый номер встречается ровно один раз, такой маршрут возвращается к началу и не попадает в чужую цепочку. Карточка $i$ лежит в последней коробке этой цепочки. Поэтому участник найдёт её за число открываний, равное длине своей цепочки.

Опишите единственную причину проигрыша

Все участники выигрывают тогда и только тогда, когда каждая цепочка имеет длину не больше $50$ Двух цепочек длиннее $50$ быть не может: им потребовалось бы больше $100$ номеров. Значит, события «есть цепочка длины $51$ », «длины $52$ » и так далее до $100$ несовместны.

Посчитайте шанс одной длинной цепочки

Для фиксированного $k>50$ выберем $k$ номеров цепочки: это $\binom{100}{k}$ способов, то есть число подмножеств из $k$ элементов. Их можно расположить в цикле $(k-1)!$ способами: повороты записи обозначают тот же цикл. Остальные номера образуют любую перестановку, $(100-k)!$ вариантов. Делим произведение на число всех перестановок:

\frac{\binom{100}{k}(k-1)!(100-k)!}{100!}=\frac1k.

Двойного счёта нет, потому что такая длинная цепочка может быть только одна.

Сложите несовместные неудачи

Вероятность проигрыша равна сумме вероятностей несовместных событий — длин циклов от $51$ до $100$ Поэтому вероятность общего успеха

1-\sum_{k=51}^{100}\frac1k\approx0{,}31183=31{,}183\,\%.

Это не гарантия для конкретной раскладки. Стратегия делает успехи участников зависимыми: короткая цепочка сразу помогает всем, чьи номера в неё входят.

Пример одного цикла: четыре участника выигрывают вместе

Коробка 7 содержит карточку 23, коробка 23 — карточку 41 и так далее. Каждый начинает со своего номера и обходит весь цикл.

Каждый идёт по своей замкнутой цепочке

01iоткрыть коробку со своим номером

02i → j → k → iкарточка указывает следующую коробку

03Не длиннее 50условие успеха всей команды

Ответ

Открывать ящики по циклу перестановки, начиная со своего номера. Вероятность общего успеха:

1-\sum_{k=51}^{100}\frac1k\approx31{,}18\,\%.

Главная идея

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

Как заметить эту идею в другой задаче

В пронумерованных ящиках лежит перестановка тех же номеров. Переход «номер карточки → следующий ящик» разбивает её на циклы; ограничение числа открываний становится ограничением длины цикла.

Возможная ошибка

Перемножить сто вероятностей $\frac{1}{2}$ При обходе цепочек успехи участников не независимы.

Источник и примечания

Источник и редакция

Классическая задача. Формулировка и разбор — Popov Academy.

Проверь себя

Теперь участников $4$ коробок $4$ каждому разрешены $2$ открытия. Какова вероятность общего успеха той же стратегии?

Ответ к дополнительной задаче

$\frac{5}{12}$ примерно $41{,}67\,\%$ Неудачу дают цикл длины $3$ или $4$ эти события несовместны и имеют вероятности $\frac{1}{3}$ и $\frac{1}{4}$ Успех: $1-\frac{1}{3}-\frac{1}{4}=\frac{5}{12}$ . Среди $24$ перестановок подходят $10$

Тема, знания и приёмы

Вероятность · Уровень уточняется

Вероятность равновозможных исходов
Факториалы и сочетания для строгого подсчёта
Сложение вероятностей несовместных событий

Приёмы решения: Переход от шага к следующему

Задать вопрос по задаче →

Условие

Следуйте указателям

Опишите единственную причину проигрыша

Посчитайте шанс одной длинной цепочки

Сложите несовместные неудачи

Источник и редакция

Продолжить чтение

Условие

Дополнительная задача