Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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).

share|improve this question
2  
make them line up according to their date of birth. That way you don't need to do any asking.. (they do it) –  picakhu May 22 '12 at 21:07
    
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? –  Qiaochu Yuan May 22 '12 at 21:20
    
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 en.wikipedia.org/wiki/… 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). –  KCd May 22 '12 at 23:19
    
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! –  KCd May 22 '12 at 23:24
    
The page en.wikipedia.org/wiki/… 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). –  KCd May 22 '12 at 23:27

1 Answer 1

A simple method would be to take advantage of the available parallelism and cheap broadcast operation: simply have each student state their birthday in turn, and all the other students say something if they also have that birthday.

There are surely faster divide-and-conquer approaches, but that would make the algorithm more complex, and thus error prone.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.