До Нового года осталось 3 недели, а значит, пришло время «Тайного Санты». Но что, если не все друзья или родственники могут собраться в одной комнате для жеребьёвки? Вы скажете, что можно использовать специальное приложение, куда вбиваются все имена, а потом рандомно рассылаются участникам. Верно, таких приложений действительно много. Но если у человека нет смартфона или электронной почты? Да, в это трудно поверить, но такие люди действительно существуют. Остаётся заморочиться и разослать бумажные письма. Но и тут не всё так просто, ведь розыгрыш может не состояться.

На всякий случай напомним правила «Тайного Санты». Участники пишут свои имена на бумажках, опускают их в шапку, а потом каждый вытягивает себе чьё-то имя. Именно этому человеку нужно купить подарок. Обычно даритель остаётся неизвестным, хотя признаваться не запрещено.

Алгоритм игры, чтобы точно было понятно:

1. Напишите имена друзей / родственников / коллег на бумажках;

2. Сложите имена в шапку;

3. Каждый по очереди вытаскивает имя из шапки;

4. Если вы вытащили бумажку со своим именем, вернитесь к шагу 2;

5. Готовьте подарок и вручайте.

Итак, возможная проблема состоит в том, что человек может получить письмо со своим именем. В этом случае весь розыгрыш придётся перезапускать заново. То есть писать новые письма всем участникам. А если кто-то снова вытянет самого себя…

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

Санта с 99% гарантией

Итак, сколько розыгрышей нужно, чтобы мы были на 99% уверены в получении правильных пар? Эта ситуация является частным случаем биномиального распределения, которое имеет следующую формулу для определения вероятности получения ровно r успехов из n попыток с вероятностью p:

nCr. p^r. ( 1-р )^n - г

Но на самом деле нам нужна вероятность одного или нескольких успехов, что является логически противоположным утверждению о вероятности полного отсутствия успехов. Когда вы подставляете это в биномиальную формулу, она упрощается до:

1- (1-p) ⁿ

Но что такое p?

Один из способов определить p – вручную выписать набор допустимых результатов для разных размеров групп.

Таблица вероятностей успеха в n испытаний

Оказывается, это число варьируется в зависимости от размера группы, но оно приближается к значению чуть выше 1/3. В нашем случае я хочу знать p для группы из 6 человек, поэтому для подбора ответа нужны компьютерные вычисления.

В Python можно написать решение в одну строку, но для ясности я разбил его на 3 строки:

>> import itertools, numpy, math
>> santa = numpy.array([1,2,3,4,5,6])
>> sum([1 for z in itertools.permutations(santa) if math.prod(z-santa) != 0])
265

Это создает итеративный объект Python, который включает все комбинации массива [1, 2, 3, 4, 5, 6]. Если мы используем порядок цифр в массиве для обозначения пары (т.е. первый элемент соответствует первому Санте, второй элемент – второму и так далее), то расклад [1, 2, 3, 4, 5, 6] явно является худшим вариантом розыгрыша, так как каждый Санта вытянет самого себя.

Благодаря модулю itertools мы можем использовать эту абстракцию, чтобы представить все возможные варианты розыгрышей шести Тайных Сант в виде массивов (спойлер, длина этого списка такая же, как 6!, то есть 720).

Но как проверить, состоялся ли розыгрыш? Самый простой способ это узнать – вычесть стартовый индекс каждого Санты из индекса в текущем раскладе. Если в результате розыгрыша кто-то вытаскивает себя, в массиве окажется один или несколько нулей, и тогда мы присваиваем массиву значение нуля, если розыгрыш недействителен, и значение отличное от нуля, если розыгрыш состоялся.

Теперь мы знаем, что существует 265 успешных розыгрышей для группы из шести человек. Это примерно 0,3681.

Так сколько проводить розыгрышей

Итак, теперь мы хотим знать, сколько нужно розыгрышей, чтобы с вероятностью 99% существовал хотя бы один успешный. Мы могли бы просто использовать нашу упрощенную биномиальную формулу, чтобы рассчитать вероятность успеха после n попыток, а затем остановиться, когда мы достигнем 99%, но это слишком скучно.

Чтобы расколоть этот орешек нам потребуется оптимизатор ScipPy. Ему просто нужно изменить наше уравнение так, чтобы искомый ответ давал ноль при вводе в функцию Python.

>> from scipy.optimize import fsolve
>> fsolve(lambda x: 1-(1-265/720.)**x-0.99, 1)
array([10.03406063])

Таким образом, нам нужно около 10 розыгрышей, чтобы ошибка возникала только в одном случае из ста. Но если мы будем рассылать бумажные письма, то даже 10 розыгрышей – это слишком много. Да и нельзя исключать человеческий фактор, можно банально ошибиться при составлении писем с розыгрышами.

Альтернативный подход

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

Теперь мы знаем, как сгенерировать все варианты перестановок и как легко найти успешные розыгрыши, а также, сколько их всего (например, 265). Это число не такое уж большое, поэтому в данном случае проще отправить всем Сантам персонализированный список, состоящий из результатов всех 265 возможных успешных розыгрышей.

В день розыгрыша кто-то просто выбирает случайное число от 1 до 265 и все смотрят, кто им выпал. Конечно, в данном случае организатор будет знать пары, но это не такая уж большая проблема.

Так что теперь, если друзья/семья далеко, без сотовой связи и интернета, это не помешает вам обменяться подарками!

Что ещё интересного есть в блоге Cloud4Y

→ Айтишный пицца-квест. Итоги

→ Как я случайно заблокировал 10 000 телефонов в Южной Америке

→ Клавиатуры, которые постигла неудача

→ Чувствуете запах? Пахнет утечкой ваших данных

→ Изучаем своё железо: сброс паролей BIOS на ноутбуках

Подписывайтесь на наш Telegram-канал, чтобы не пропустить очередную статью. Пишем не чаще двух раз в неделю и только по делу.