2
$\begingroup$

It's well-known that with 23 or more people in a group, the probability is > 1/2 that two people will share a birthday. (The non-uniformity of birthdays only helps increase this probability.)

I often want to demonstrate this in class, but I don't know a good algorithm for finding the collisions. Obviously sorting the students by birthday would suffice, but it seems like overkill. The last time I did this, I went month-by-month: "Raise your hand if you were born in January." Then we'd brute-force January to search for collisions. Etc.

I realize this question isn't well-constrained, but I would appreciate an efficient algorithm that respects common sense (ie, uses steps that are practical for a human to execute on human subjects). If you'd prefer a more traditional algorithm question: given an array of size $n$, find two entries that match or state that none exists. Make your algorithm use as few comparisons as possible in absolute terms (ie, no using asymptotic notation).

  • 2
    make them line up according to their date of birth. That way you don't need to do any asking.. (they do it)2012-05-22
  • 0
    How about telling the students to go into one of the 4 corners of the room (I assume the room has 4 corners) depending on month (January/February/March for the first corner, etc.) and then having the students in each group state their birthdays to the other members of the group in turn?2012-05-22
  • 0
    You should check *in advance* (if you have student records) what the birthdays are of the students in the class, since if there really is no birthday pair then it will be a disappointing use of class time to seek a common birthday. Use instead a backup list of over 23 random people. For example, at http://en.wikipedia.org/wiki/List_of_Presidents_of_the_United_States_by_date_of_birth is a list of US presidents by birth and there is one coincidence (scroll down to "Born on same date") involving the 11th and 29th president (but it's 28 people by then due to Cleveland being president twice).2012-05-22
  • 0
    I don't see what is so inefficient with asking those born in January to raise hands and point to them one by one and ask for their birthdays, and so on. Once I attended a talk on the use of the birthday paradox in cryptography, and there were over 30 people in the room. I didn't know for sure that there would be a birthday pair, but in any event I asked everyone born in January to raise their hand. I pointed to one of them, asked for the birthday, and then asked if anyone else shared that birthday. Someone did. My job was done and I sat down. A pretty effective demonstration!2012-05-22
  • 0
    The page http://en.wikipedia.org/wiki/List_of_United_States_Presidents_by_date_of_death shows you the days when US presidents died. There are three dates on which more than one US president died, including the famous example of the 2nd and 3rd US president both dying on July 4th (in the same year).2012-05-22
  • 0
    @picakhu This is a sorting algorithm, which (as I said in my question) seems like overkill. But perhaps it's best?! I was hoping to avoid having students get out of their chairs, but perhaps it's fine.2012-05-23
  • 0
    @Fixee, I was just giving one method. This would work better with middle school kids.2012-05-23

1 Answers 1