Bruce is an inmate at a large prison, and like most of the other prisoners, he smokes cigarettes. During his time in the prison, Bruce finds that if he has 3 cigarette butts, he can cram them together and turn them into 1 full cigarette. Whenever he smokes a cigarette, it turns into a cigarette butt.
One day, Bruce is in his cell talking to one of his cellmates, Steve.
"I really want to smoke 5 cigarettes today, but all I have are these 10 cigarette butts," Bruce tells Steve. "I'm not sure that will be enough."
"Why don't you borrow some of Tom's cigarette butts?" asks Steve, pointing over to a small pile of cigarette butts on the bed of their third cellmate, Tom, who is out for the day on a community service project.
"I can't," Bruce says. "Tom always counts exactly how many cigarette butts are in his pile, and he'd probably kill me if he noticed that I had taken any."
However, after thinking for a while, Bruce figures out a way that he can smoke 5 cigarettes without angering Tom. What is his plan?
Bruce takes 9 of his 10 cigarette butts and turns them into 3 cigarettes total (remember, 3 cigarette butts can be turned into 1 cigarette). He smokes all three of these, and now he has 4 cigarette butts.
He then turns 3 of the 4 cigarette butts into another cigarette and smokes it. He has now smoked 4 cigarettes and has 2 cigarette butts.
For the final step, he goes and borrows one of Tom's cigarette butts. With this cigarette butt plus the 2 he already has, he is able to make his 5th cigarette to smoke. After smoking it, he is left with 1 cigarette butt, which he puts back in Tom's pile so that Tom won't find anything missing.
What is the least number of people that need to be in a room such that there is greater than a 50% chance that at least two of the people have the same birthday?
Only 23 people need to be in the room.
Our first observation in solving this problem is the following:
(the probability that at least 2 people have the same birthday + the probability that nobody has the same birthday) = 1.0
What this means is that there is a 100% chance that EITHER everybody in the room has a different birthday, OR at least two people in the room have the same birthday (and these probabilities don't add up to more than 1.0 because they cover mutually exclusive situations).
With some simple re-arranging of the formula, we get:
the probability that at least 2 people have the same birthday = (1.0 - the probability that nobody has the same birthday)
So now if we can find the probability that nobody in the room has the same birthday, we just subtract this value from 1.0 and we'll have our answer.
The probability that nobody in the room has the same birthday is fairly straightforward to calculate. We can think of this as a "selection without replacement" problem, where each person "selects" a birthday at random, and we then have to figure out the probability that no two people select the same birthday. The first selection has a 365/365 chance of being different than the other birthdays (since none have been selected yet). The next selection has a 364/365 chance of being different than the 1 birthday that has been selected so far. The next selection has a 363/365 chance of being different than the 2 birthdays that have been selected so far.
These probabilities are multiplied together since each is conditional on the previous. So for example, the probability that nobody in a room of 3 people have the same birthday is (365/365 * 364/365 * 363/365) =~ 0.9918
More generally, if there are n people in a room, then the probability that nobody has the same birthday is (365/365 * 364/365 * ... * (365-n+2)/365 * (365-n+1)/365)
We can plug in values for n. For n=22, we get that the probability that nobody has the same birthday is 0.524, and thus the probabilty that at least two people have the same birthday is (1.0 - 0.524) = 0.476 = 47.6%.
Then for n=23, we get that the probability that nobody has the same birthday is 0.493, and thus the probabilty that at least two people have the same birthday is 1.0 - 0.493) = 0.507 = 50.7%. Thus, once we get to 23 people we have reached the 50% threshold.
A boy was at a carnival and went to a booth where a man said to the boy, "If I write your exact weight on this piece of paper then you have to give me $50, but if I cannot, I will pay you $50."
The boy looked around and saw no scale so he agrees, thinking no matter what the carny writes he'll just say he weighs more or less. In the end the boy ended up paying the man $50. How did the man win the bet?
The man did exactly as he said he would and wrote "your exact weight" on the paper.
A guard is stationed at the entrance to a bridge. He is tasked to shoot anyone who tries to cross to the other side of the bridge, and to turn away anyone who comes in from the opposite side of the bridge. You are on his side of the bridge and want to escape to the other side.
Because the bridge is old and rickety, anyone who tries to cross it does so at a constant speed, and it always takes exactly 10 minutes to cross.
The guard comes out of his post every 6 minutes and looks down the bridge for any people trying to leave, and at all other times he sits in his post and snoozes. You know you can sneak past him when he's sleeping, but the problem is that you won't be able to make it all the way to the other side of the bridge before he sees you (since he comes out every 6 minutes, but it takes 10 minutes to cross).
One day a brilliant idea comes to you, and soon you've successfully crossed to the other side of the bridge without being shot. How did you do it?
Right after the guard goes back to his post after checking the bridge, you sneak by and make your way down the bridge. After a little bit less than 6 minutes, you turn around and start walking back toward the guard. He will come out and see you, and assume that you are a visitor coming from the other side of the bridge, since you're only about 4 minutes from the end of the other side of the bridge. He will go back into his post since he doesn't plan to turn you away until you reach him, and then you turn back around and make your way the rest of the way to the other side of the bridge.
