Introduzione
Appena uscito dall'università, stai organizzando una grande festa per festeggiare con amici e familiari.
Sono arrivate più di 70 persone, tra cui il tuo zio Ted, un po' eccentrico.
In una delle sue solite trovate, ti scommette £100 che almeno due persone nella stanza festeggiano il compleanno nello stesso giorno.
Sembra assurdo: i compleanni possibili sono molti più degli invitati, quindi accetti con sicurezza.
Con tuo stupore, dopo aver raccolto i compleanni di appena 32 invitati, hai già trovato due persone che festeggiano il compleanno nello stesso giorno.
Accetti la sconfitta e porgi a zio Ted i suoi £100, ma qualcosa non torna.
Il giorno dopo, la curiosità ha la meglio.
Una rapida ricerca sul web ti porta al paradosso del compleanno, che rivela che con appena 23 persone la probabilità che due di loro festeggino il compleanno nello stesso giorno supera il 50%.
Ah. Ecco perché zio Ted era così sicuro.
Deciso a ribaltare la situazione, inizi a cercare altri paradossi; la prossima volta sarai tu a fare le scommesse.
Il paradosso del compleanno è un paradosso veridico: anche se sembra sbagliato, in realtà è vero.
Istruzioni
Il tuo compito è stimare le probabilità del paradosso del compleanno.
Per farlo, devi:
- Generare date di nascita casuali.
- Controllare se una raccolta di date di nascita generate casualmente ne contiene almeno due con lo stesso compleanno.
- Stimare la probabilità che almeno due persone in un gruppo condividano lo stesso compleanno, per diverse dimensioni del gruppo.
Una data di nascita include la data completa (anno, mese e giorno), mentre un compleanno si riferisce solo al mese e al giorno, che si ripetono ogni anno.
Due date di nascita con lo stesso mese e giorno corrispondono allo stesso compleanno.
Il paradosso del compleanno presuppone che:
- Ci siano 365 compleanni possibili (nessun anno bisestile).
- Ogni compleanno abbia la stessa probabilità (distribuzione uniforme).
La tua implementazione deve rispettare queste ipotesi.
Note specifiche per x86-64 Assembly
La funzione random_birthdates() deve produrre date con le seguenti proprietà:
- L'anno deve essere valido.
Un anno valido
y non è bisestile ed è tale che 1600 <= y < 2129.
- L'anno è distribuito in modo uniforme su tutto l'intervallo dei valori validi.
- Il compleanno è distribuito in modo uniforme su tutti i 365 giorni dell'anno, così che ogni giorno di calendario sia ugualmente probabile.
Nota che questo significa che i mesi non hanno tutti la stessa probabilità: un mese di 31 giorni è più probabile di un mese di 30 giorni, ed entrambi sono più probabili di febbraio.
Sia la distribuzione dell'anno che quella del compleanno vengono verificate con un test chi quadrato, al livello di p < 0.0001.
Questo significa che, se le date vengono generate secondo le istruzioni, c'è meno dello 0,01% di probabilità che venga prodotta una distribuzione di valori che non supera il test.
