birthday paradox fastest search

Question

The birthday problem or birthday paradox predicts the likelihood of one or more matching birthdays in a group of N people. Several sites explain how it works, and the mathematics behind it:

1. https://en.wikipedia.org/wiki/Birthday_problem
2. https://math.stackexchange.com/questions/25876/probability-of-3-people-in-a-room-of-30-having-the-same-birthday
3. http://www.wolframalpha.com/input/?i=birthday+problem+calculator&a=FSelect_**BirthdayProblem-.dflt-&f2=35&f=BirthdayProblem.n_35&f3=365&f=BirthdayProblem.pbds_365

These sites are all great for explaining the concept, but all require that the data has already been collected. None show how to efficiently survey a large group of people.

I’m planning to demonstrate the birthday paradox in a short presentation. Basically, I need the fastest way to determine which, if any, people share or nearly share birthdays in an audience of about 50 people.

the best algorithm I can think of:

1. ask all people to think of their birthday, just the month and day (or a fictional birthday if they're uncomfortable sharing their true birthday)
2. ask all people to listen carefully
3. ask individual people to start announcing their birthday to the group and listen for their match

In the worst case scenario, all people would announce their birthdays in sequence without anyone matching. It feels like I’ve overlooked some shortcut to finding the answer more quickly, beyond a brute-force approach.

alternatives I considered:

• split audience into 2 groups? no, this would prevent people from hearing responses from other group

• plant a person in the audience to “share” their birthday with someone if nobody matches halfway? no, this is cheating

• pass around a year calendar and marker? no, this would probably take longer than speaking

• online survey? no, people might not have phone or WIFI

The solution needs to be low-tech, done without prior preparation and of course, honest.

Please let me know your suggestions for quickly searching for matched birthdays.

Thanks!

Answer 1

• Start with everyone seated.
• Go by the day (1-31) of their birthday, ask all people born on the 1st of a month to stand up.
• If anyone does, ask them to raise their hand as you call their month ... January ... if anyone raises their hand, tell them to sit down. If two people raise their hand, you are done.
• Continue on with ... February, March, etc. asking standing people to raise their hand when they hear their month, and to sit down when you recognize them
• When done, continue to the 2nd of the month, third, etc.

By having people stand up on their day, and raise their hand on their month, you can quickly identify 2 matching birthdays. You can also quickly skip days when there are no matching birthdays.

Answer 2

Go month by month. Have people with birthdays in that month raise their hands and call on them. You can use short-term memory to identify repeated numbers in the short list from each month, whereas most people can't do this with repeated dates among a list of 30 dates. Even if you don't do that perfectly, members of the audience will help.

If you don't want to take the time and risk failure or an uncooperative audience, try using a prepared list of people with known birthdays of about the right length, say US presidents. (Polk and Harding were born November 2nd.)