Omicron Persei 8

Logic Level 3

A thousand light years away from Earth, there is a planet that orbits its sun every 100 days. That planet is called Omicron Persei 8, it is inhabitated by living creatures known as Omicronians and they too have the ritual to celebrate the anniversary of their birthday.

What is the maximum number of randomly selected Omnicrons needed such that the probability of all of their birthdays are different exceeds 50%?

Assume that there is a uniform distribution of birthdays across all days of the 100 day year.

Image Credit: Omicron Persei 8 .

No copyright infringement intended.

12 14 13 11 15

4 solutions

Sharky Kesa
Jun 14, 2015

Let's call $p(n)$ the probability that all the birthdays are different in a group of $n$ people. It is easy to see that

$\begin{aligned} p(n) &= 1 \times \left ( 1 - \dfrac {1}{100} \right ) \times \left ( 1 - \dfrac {2}{100} \right ) \times \ldots \times \left ( 1 - \dfrac {n - 1}{100} \right )\\ &= \dfrac {100 \times 99 \times \ldots \times (99 - n + 1)}{100^n}\\ &= \dfrac {100!}{100^n (100-n)!}\\ &= \dfrac{^{100}P_n}{100^n} \end{aligned}$

We have to find the maximum value of $n$ such that $\dfrac{^{100}P_n}{100^n} > \dfrac {1}{2}$ . Bashing it out with a calculator, we get that 12 is the answer.

Brock Brown
Jun 16, 2015

Python 3.4:

from random import randint
from time import time
def different_birthdays(omicronians):
    birthdays = set()
    for omicronian in range(omicronians):
        new_birthday = randint(1,100)
        if new_birthday in birthdays:
            return False
        birthdays.add(new_birthday)
    return True
p = 0
omicronians = 100
while p < 0.5:
    omicronians -= 1
    count = 0
    trials = 0
    end = time() + 1
    while time() < end:
        if different_birthdays(omicronians):
            count += 1
        trials += 1
    p = count/trials
print("Answer:", omicronians)

Anthony Winder
Mar 25, 2016

"""
Omicron Persei 8
Python 3

Increments no_of_Omicronians (starting from 0) until 
prob_different_birthdays is no longer greater than 0.5. 
The answer is one less than the final no_of_Omicronians.

Rationale: 

The probability that all Omicronians have different 
birthdays is trivially 1.0 if there are zero Omicronians. 

For each additional randomly selected Omicronian the 
probability can be derived recursively from the previous 
probability by multiplying it by the factor 
no. of days still available for non-overlapping birthdays / no. of days in year,
(where the no. of days still available is 
no. of days in year - previous no. of Omicronians).

If, for example, there are currently seven Omicronians 
with different birthdays, the probability of a randomly 
introduced eighth having a birthday on a different day from 
any of the others is the probability (already known) of the 
first seven having different birthdays multiplied by 93/100
(since 93 potential birthdays remain 'unclaimed').
"""

days_in_year = 100.0
no_of_Omicronians = 0
prob_different_birthdays = 1.0

while True:
    if prob_different_birthdays <= 0.5:
        print("The answer is", no_of_Omicronians - 1)
        break
    else:
        prob_different_birthdays *= (days_in_year - no_of_Omicronians) / days_in_year
        no_of_Omicronians += 1

# end of program

Great! Upvoted!!

Pi Han Goh - 5 years, 2 months ago

Manvendra Singh
Oct 28, 2015

Did the same way sharky

Omicron Persei 8

Image Credit: Omicron Persei 8 .

No copyright infringement intended.

4 solutions

0 pending reports