Тайный Санта: жеребьёвка онлайн

Как устроена жеребьёвка и что лежит в ссылке

Каждый может вытянуть кого угодно, кроме себя и тех, кого вы от него отделили. «Друг друга» убирает оба направления между двумя людьми, «в одну сторону» — только одно. Прежде чем что-то тянуть, генератор проверяет, существует ли вообще жеребьёвка, которая соблюдает все правила. Для одного имени на человека это задача о паросочетании — можно ли каждому выдать своё, разрешённое ему имя, — и ответ на неё находится точно, а не методом «попробуем и посмотрим». Если ответ «нет», страница называет виновных: группу дарителей, которым на всех разрешено меньше имён, чем их самих. Теорема Холла о свадьбах говорит, что жеребьёвка существует ровно тогда, когда такой группы нет, так что назвать группу — значит назвать причину.

Для одного имени на человека жеребьёвка — это перемешивание. Весь список перемешивается криптографическим генератором случайных чисел браузера, и результат остаётся, только если каждому досталось разрешённое ему имя; иначе список перемешивается снова, до двадцати тысяч раз. Если оставлять только прошедшие проверку перемешивания, у каждой допустимой жеребьёвки ровно одинаковый шанс. Только когда правила оставляют так мало допустимых вариантов, что все двадцать тысяч попыток проваливаются, страница переходит на случайный поиск: он всегда находит вариант, но не обещает каждой жеребьёвке равного шанса.

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

Цифра в тексте под инструментом — простая арифметика. Когда каждый в группе тянет одно имя из шапки, доля жеребьёвок, где никому не досталось своё имя, — это число беспорядков, делённое на число перестановок: 9 из 24 для четырёх человек, 44 из 120 для пяти, 14 833 из 40 320 для восьми. Начиная с четырёх человек она держится между 36 % и 38 % и стремится к единице, делённой на e, — около 36,8 %.

Каждая ссылка несёт жеребьёвку одного человека: название события, его имя, имя или имена тех, кому он дарит, с подсказками, если вы их добавили, бюджет, дату, вашу заметку, четырёхсимвольный код жеребьёвки и минуту, когда она прошла. Ссылка перемешана так, чтобы имя нельзя было прочесть с одного взгляда в превью сообщения. Это не шифрование: любой, кто откроет ссылку, увидит, что в ней, поэтому отправляйте каждому только его ссылку. На распечатанных карточках та же ссылка в виде QR-кода, с уровнем коррекции ошибок M, который по стандарту QR восстанавливает около 15 % повреждённого символа, или L — около 7 % — для ссылки, слишком длинной для M. Предел в сорок человек — наш собственный выбор: дальше кольцо имён и страница карточек перестают читаться. Календарный файл на странице результата содержит одно событие на весь день обмена подарками с напоминанием за неделю; в нём названы день и бюджет, но никогда — человек. Имена, исключения, детали и жеребьёвка сохраняются в этом браузере, чтобы организатор мог заново отправить потерянную ссылку; аккаунт не нужен.

Откуда эти цифры

1. 1. On Representatives of Subsets (Hall's marriage theorem) — P. Hall, Journal of the London Mathematical Society, 1935
2. 2. A000166: Subfactorial or rencontres numbers, or derangements — The On-Line Encyclopedia of Integer Sequences
3. 3. ISO/IEC 18004:2015 — QR Code bar code symbology specification — International Organization for Standardization
4. 4. Crypto: getRandomValues() method — MDN Web Docs, Mozilla

Каждая цифра выше взята из кода, который работает на этой странице. Где число — наша собственная оценка, а не опубликованные данные, в примечании так и сказано, и источник не указан. Метод в последний раз проверен 28 сентября 2026.