Introdução
Você acabou de se formar na faculdade e está dando uma festa enorme para celebrar com amigos e familiares.
Mais de 70 pessoas apareceram, incluindo seu tio Ted, que é um tanto excêntrico.
Em uma de suas travessuras de sempre, ele aposta £100 com você que pelo menos duas pessoas na sala fazem aniversário no mesmo dia.
Isso parece ridículo: existem muito mais datas de aniversário possíveis do que convidados, então você aceita sem hesitar.
Para seu espanto, depois de coletar o aniversário de apenas 32 convidados, você já encontrou dois convidados que fazem aniversário no mesmo dia.
Aceitando a derrota, você entrega os £100 ao tio Ted, mas algo não parece certo.
No dia seguinte, a curiosidade fala mais alto.
Uma rápida busca na internet te leva ao paradoxo do aniversário, que revela que, com apenas 23 pessoas, a probabilidade de duas delas fazerem aniversário no mesmo dia passa de 50%.
Ah. Então era por isso que o tio Ted estava tão confiante.
Para virar o jogo, você começa a pesquisar outros paradoxos; da próxima vez, você é quem vai fazer as apostas.
O paradoxo do aniversário é um paradoxo verídico: mesmo parecendo errado, ele é de fato verdadeiro.
Instruções
Sua tarefa é estimar as probabilidades do paradoxo do aniversário.
Para isso, você precisa:
- Gerar datas de nascimento aleatórias.
- Verificar se uma coleção de datas de nascimento geradas aleatoriamente contém pelo menos duas com o mesmo aniversário.
- Estimar a probabilidade de que pelo menos duas pessoas em um grupo façam aniversário no mesmo dia, para diferentes tamanhos de grupo.
Uma data de nascimento inclui a data completa do nascimento (ano, mês e dia), enquanto um aniversário se refere apenas ao mês e ao dia, que se repetem a cada ano.
Duas datas de nascimento com o mesmo mês e o mesmo dia correspondem ao mesmo aniversário.
O paradoxo do aniversário parte das seguintes premissas:
- Existem 365 aniversários possíveis (nenhum ano bissexto).
- Cada aniversário tem a mesma probabilidade (distribuição uniforme).
Sua implementação deve seguir essas premissas.
Notas específicas do Assembly x86-64
A função random_birthdates() deve produzir datas com as seguintes propriedades:
- O ano deve ser válido.
Um ano válido
y não é bissexto e é tal que 1600 <= y < 2129.
- O ano é distribuído uniformemente por todo o intervalo de valores válidos.
- O aniversário é distribuído uniformemente pelos 365 dias do ano, de modo que cada dia do calendário tenha a mesma probabilidade.
Observe que isso significa que os meses não são igualmente prováveis: um mês de 31 dias é mais provável que um de 30 dias, e ambos são mais prováveis que fevereiro.
Tanto a distribuição do ano quanto a do aniversário são verificadas por um teste de qui-quadrado, com nível de p < 0,0001.
Isso significa que, se as datas estiverem sendo geradas de acordo com as instruções, há menos de 0,01% de chance de produzirem uma distribuição de valores que falhe no teste.
