Here is a collection of my favorite math puzzles. I like puzzles which can be solved with a beautiful trick, or which are counter-intuitive, or which confuse people. I do not want to spoil them for you by posting all the solutions, but I would like to post some discussion and divide the puzzles into groups.
Among the families with two children, which have at least one boy, what is the probability that the family has two boys?
Assume that the probability of a child being a boy is 1/2. It is easy to see that for families with two children each of the following cases occurs with the probability 1/4:
Therefore, among families with one boy only one third of the families have two boys. Hence, the answer is 1/3.
A man says, "I have two children; at least one of them is a boy." What is the probability that the other one is a boy?
I recommend that you look at the discussion only after you have solved the problem. After you understand the solution to the problem of the other child, you can easily solve the three puzzles below. Note that not all of them have the same answer.
I meet my friend at the store. She tells me that she is buying a present for her son. I know that she has two children, but I don't know the gender of her children. Based on the information I have, what is the probability that the other child is a boy?
In a small town every family has two children. Every family that has at least one boy received an advertisement from the Navy. What is the probability that the second child in a family that received the advertisement is a boy?
In a college, all of the students are from families with 2 children, and both of the children are in this college. For summer vacation, all of the students go to an island with no other people. During the vacation, one of the girls becomes pregnant. Assume that she has no taste whatsoever and selects her partner at random. What is the probability that the father of the unborn child has a brother?
I have two children. At least one of them is a boy. What is the probability that the other one is a boy as well?
A man has two children. One of them is a boy named John. What is the probability that John has a younger brother?
Here is a hint for those who are stuck.
Find three ways to make the program below print 20 copies of the dash character '-' by changing/adding one character:
int i, n = 20;for (i = 0; i < n; i--){printf("-");}
pochmann and SnapDragon from TopCoder suggested very fun and challenging variations to this problem (using the same restrictions):
In your favorite programming language write a program that, when run, will print out its own source code. Bonus puzzle: write this program without using external resources - you have the interpreter for your language, you have the output and you can't interact with your environment in any other way. (Such programs are called quines).
My birthday is in January. What is the smallest number of yes/no questions you need to ask to guess the day of my birthday.
This time, you must think of all of your questions before I answer them and then ask them in that order. How many questions do you need?
There are two ideas.
The first idea helps to calculate a reasonable minimum number of questions. Idea: If you ask K questions you can have 2K different sequences of yes/no answers. If you can guess the number in K questions, that means that the number is uniquely defined by the yes/no sequence. Hence, the number of different sequences should be equal to or greater than N. That is 2K ≥ N.
The second idea describes the strategy. The first question divides all of the numbers into two groups corresponding to "yes" or to "no" answers. The best question would be the one which has these two groups as equal in size as possible. For example: is your number even? The following questions should be made in a similar manner.
I have N coins, one of them is fake and is lighter than the others. I also have a balance with two cups. I can put some number of coins into each cup, and the balance shows me which set of coins is lighter. Using the balance the fewest number of times, find the fake coin.
This is the same problem as above except this time, you have to say what all of your weighings will be before you actually do them.
There are 12 coins. One of them is fake; it is either lighter or heavier than normal coins. Find the fake coin and tell whether it is lighter or heavier by using the balance in the minimum number of steps.
Once again you have 12 coins and a balance. This time, you must decide the exact weighings you will do before you do them. How many weighings will it take you this time?
I am in a 100-story building. I have with me two glass balls. I know that if I throw the ball out of the window, it will never break if the floor number is less than X, and it will always break if the floor number is equal to or greater than X. Assuming that I can reuse the balls which don't break, find X in the minimum number of throws.
There are 5 chess players of different strengths. If two of them play, the stronger one always wins. What is the minimum number of games they need to play, so that we can determine the order of their strengths?
There are 11 balls; two of them are radioactive. We have a tool in the form of a box. If we put several balls inside the tool, it can tell us whether or not there exists a radioactive ball inside it. As this tool is very expensive, how can you find two radioactive balls using the tool the minimum number of times?
A king decides to give 100 of his prisoners a test. If they pass, they can go free. Otherwise, the king will execute all of them. The test goes as follows: the prisoners stand in a line, all facing forward. The king puts either a black or a white hat on each prisoner. The prisoners can only see the colors of the hats in front of them. Then, in any order they want, each one guesses the color of the hat on their head. Other than that, the prisoners can not speak. To pass, no more than 1 of them may guess incorrectly. If they can make their strategy before hand, how can they be assured that they will survive?
7 men are sitting in a room. Someone puts a hat on the head of each man. Each hat has an equal probability of being one of the seven colors of the rainbow. It is okay for 2 men to have hats of the same color. Without communication, each man guesses the color of the hat on their head. If at least one of them guesses right, they win this little game of theirs. If they are allowed to make a strategy beforehand, how can they be assured of winning.
3 men are given a challenge. They will all sit in a room, and on each one, someone will put on either a black or a white hat, each with probability one half. The men can not communicate, but they can see the colors of the hats of the other 2 men. At the same time, they each say what they think is the color of the hat on his own head. Each one can also pass. They win if at least one of them says the color of his hat correctly, and none of them give the incorrect answer. How can they maximize their probability of winning?
There exists a hobo that is skilled at making cigarettes. He can turn any 4 cigarette butts into a single cigarette. Today, this hobo has found 24 cigarette butts on the street. Assuming he smokes every cigarette he can, how many cigarettes will he smoke today?
You have two fuses that both last 1 hour, and you have no other ways of telling time. The fuses may be thicker at some points, so in half an hour (or any other amount of time), the amount of fuse that has burned may or may not be half the length of the whole fuse. How do you measure 45 minutes worth of time?
You have one fuse similar to the ones in the problem above. Is it possible to measure exactly 20 minutes?
There exists a land where the only antidote to a poison is a stronger poison. In this land, a dragon challenges a king to a duel, and the king accepts. The rules of the duel are as follows: Each duelist has a cup of poison. First, they exchange poisons. Then, each duelist drinks half of the poison in front of them. After that, they exchange again and drink their own poisons. The survivor wins. The king knows that the dragon has a stronger poison than any the king will ever make, and it is the poison that the dragon will use. How can the king win the duel?
You have 45 pebbles arranged in several piles. Each turn you take one pebble from each pile and put them into a new pile. What is an asymptotic behavior for this process?
Last revised April 2006