Таємний Санта онлайн: жеребкування

Як працює жеребкування і що є в посиланні

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

Для одного імені на людину жеребкування — це перемішування. Увесь список перемішують криптографічним генератором випадкових чисел браузера, і перемішування залишають, лише якщо кожна людина потрапила на того, кого їй дозволено тягнути; інакше перемішують знову, до двадцяти тисяч разів. Якщо залишати лише ті перемішування, що проходять, кожне правильне жеребкування має точно однаковий шанс. Лише коли правила лишають так мало правильних варіантів, що всі двадцять тисяч перемішувань провалюються, сторінка переходить на випадковий пошук, який завжди щось знаходить, але не обіцяє кожному варіанту рівного шансу.

Для двох імен на людину перевірка існування — це задача про потік: кожна людина дарує двом, кожна отримує від двох, ніхто не тягне ту саму людину двічі. Саме жеребкування — два раунди перемішування для одного імені, причому другому заборонено повторювати перший. Це дає майже рівний шанс кожному правильному жеребкуванню на два імені, але не зовсім рівний, і ми кажемо про це прямо, а не округлюємо.

Цифра в тексті під інструментом — проста арифметика. Коли кожна людина в групі тягне одне ім’я з шапки, частка жеребкувань, у яких ніхто не отримує власного імені, — це кількість безладних перестановок, поділена на кількість усіх перестановок: 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.