Вступ
Щойно закінчивши коледж, ми влаштовуємо велику вечірку, щоб відсвяткувати разом із друзями та родиною.
Прийшло понад 70 людей, серед них і наш трохи ексцентричний дядько Тед.
У одній зі своїх звичних витівок він закладається з нами на £100, що принаймні двоє людей у кімнаті мають однаковий день народження.
Це звучить безглуздо: можливих днів народження значно більше, ніж гостей, тож ми впевнено погоджуємося.
На наш подив, зібравши дні народження лише 32 гостей, ми вже знайшли двох гостей з однаковим днем народження.
Приймаючи свою поразку, ми віддаємо дядькові Теду його £100, але щось тут не сходиться.
Наступного дня цікавість бере гору.
Швидкий пошук в інтернеті виводить нас на парадокс дня народження, з якого видно, що вже за 23 людей імовірність збігу днів народження перевищує 50%.
Ага. Ось чому дядько Тед був таким упевненим.
Сповнені рішучості змінити розклад, ми починаємо шукати інші парадокси; наступного разу ми будемо тими, хто укладає парі.
Парадокс дня народження належить до веридичних парадоксів: попри те, що він здається неправильним, насправді він істинний.
Вказівки
Наше завдання - оцінити ймовірності парадоксу днів народження.
Щоб це зробити, нам потрібно:
- Згенерувати випадкові дати народження.
- Перевірити, чи містить набір випадково згенерованих дат народження щонайменше дві з однаковим днем народження.
- Оцінити ймовірність того, що щонайменше двоє людей у групі мають однаковий день народження, для різних розмірів групи.
Дата народження охоплює повну дату народження (рік, місяць і день), тоді як день народження охоплює лише місяць і день, які повторюються щороку.
Дві дати народження з однаковими місяцем і днем відповідають одному дню народження.
Парадокс днів народження припускає, що:
- Існує 365 можливих днів народження (без високосних років).
- Кожен день народження є рівноймовірним (рівномірний розподіл).
Реалізація має дотримуватися цих припущень.
Особливості x86-64 Assembly
Функція random_birthdates() повинна генерувати дати з такими властивостями:
- Рік повинен бути коректним.
Коректний рік
y не є високосним і задовольняє умову 1600 <= y < 2129.
- Рік рівномірно розподілений по всьому діапазону коректних значень.
- День народження рівномірно розподілений по всіх 365 днях року, тож кожен календарний день однаково ймовірний.
Зауважмо, що це означає, що місяці не однаково ймовірні: 31-денний місяць імовірніший за 30-денний, і обидва ймовірніші за лютий.
І розподіл року, і розподіл дня народження перевіряють за допомогою критерію хі-квадрат на рівні p < 0,0001.
Це означає, що якщо дати генеруються згідно з інструкціями, імовірність отримати розподіл значень, який не проходить цей критерій, менша за 0,01%.
