Over on Ones and Zeros, Michael links to an entry on another blog, and also talks about the Monty Haul problem, and how a non intuitive answer can be the best strategy.
The "Birthday Paradox" is in a similar vein, too. How many people do you have to know, on average, before two of them wil have the same birthday? With 365 days in a year, you'd think it would have to be a lot...but thanks to the laws of permutations, you're at better-than-even odds at only 23 people.
It doesn't make much sense (23 people in 365 days of the year)? but look at it this way...given the first person, the odds of the second person not having the same birthday is (365-1)/365 (since it could be any other day of the year but the original person).
If you continue in this vein, person #3's chance of NOT sharing a birthday with either of them, and them with each other is 364/365 * 363/365. The multiplication of the factors represents the fact that you are not just comparing the next person to the first, but to everyone else as well.
This sort of thing adds up hellaciously. At 23 people, you are at even odds none of them share a birthday. By 40 people, because of all of the possible combinations, there is just a 12% chance of no one sharing a birthday.
So, if you are in a bar with 50 people, make a bet with a friend that two of the people share a birthday. If the people in the bar are honest about their birthdates...you will clean up.
Oh, and as a postscript, I do know two people with the same birthday within my circle (and I am not even counting my father, who shares mine). So it really does work.