Условие
n различных ключей случайно лежат в n копилках. Сначала разбивают фиксированные k копилок, затем открывают доступные по ключам. Найдите вероятность получить все ключи и среднюю долю найденных. 0 ≤ k ≤ n.
Решение по шагам
Перестановка раскладывается на циклы. Получив ключ из одной копилки, можно пройти весь её цикл. Поэтому доступны ровно циклы, содержащие хотя бы одну из k заранее отмеченных копилок.
При 1 ≤ k ≤ n число перестановок, у которых каждый цикл отмечен, равно k(n−1)!. Это можно получить вставкой неотмеченных элементов в промежутки после отмеченных в записи циклов: k! порядков отмеченных, (n−k)! порядков остальных и C(n−1,k−1) способов распределения. Их произведение k(n−1)!. Вероятность всех ключей k/n. При k=0 она нулевая.
Для конкретной неотмеченной копилки удалим остальные неотмеченные элементы из циклической записи. Получим равномерную перестановку k+1 выделенных элементов. Её собственный цикл не содержит отметок тогда и только тогда, когда этот элемент — одиночный цикл; вероятность 1/(k+1). Поэтому ожидаемое число недоступных (n−k)/(k+1), найденных k(n+1)/(k+1), а доля равна последнему выражению, делённому на n.
Проверка результата
При k=n вероятность и доля равны 1; при k=0 оба результата нулевые. Для n=3, k=1 перебор шести перестановок даёт вероятность 1/3 и среднее два найденных ключа.
Типичная ошибка
Считать каждый новый ключ независимым новым шансом: замкнутый цикл без отметки недоступен целиком.
Что даёт этот метод
Выделяйте циклы перестановки и применяйте индикаторы доступности.
Дальше по теме
Теория вероятностей: другие задачи.
Следующие разборы
- Как перевод ученика может повысить средний балл обоих классов
- ВШЭ, ПМИ: контрольная «Альфа» 2024, все шесть задач
Условие адаптировано из открытого источника: Борис Демешев и участники, probability_dna, L1717. Решение, объяснение и проверка изложены редакцией damirock.com; это не официальный ключ преподавателя. CC BY 4.0. Вёрстка и обозначения адаптированы; числовые предпосылки указаны в условии.