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

  • 0
    @Fixee, I was just giving one method. This would work better with middle school kids.2012-05-23

1 Answers 1

3

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.