My Favorite Puzzles


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.


Puzzles with two children

Straightforward problem: Families with a Boy.

Among the families with two children, which have at least one boy, what is the probability that the family has two boys?

Solution:

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.

Confusing puzzle: The Other Child.

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?

Discussion of the Other Child problem.

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.

Puzzle: Birthday Present.

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?

Puzzle: Navy Recruitment.

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?

Puzzle: Pregnancy.

In a college, all of the students are from families with two 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?

Puzzle: My Family.

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?

Puzzle: John's Brother

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.


Puzzles for programmers

Puzzle: In Three Ways.

Find three ways to make the program below print 20 copies of the dash character '-' by changing or adding one character:

int i, n = 20;
for (i = 0; i < n; i--)
{
    printf("-");
}

Incorrect solutions:

pochmann and SnapDragon from TopCoder suggested entertaining and challenging variations to this problem (using the same restrictions):

Puzzle: Program that prints itself.

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 and you have the output, but you can't interact with your environment in any other way. (Such programs are called quines).


Counting Information

Easy Problem: Guess my Birthday.

My birthday is in January. What is the smallest number of yes/no questions you need to ask to determine the day of my birthday.

Slightly Harder Version: Guess my Birthday

This time, you must mentally list all of your questions before I answer them and then ask them in that order. How many questions do you need?

General solution that helps for all the other problems in this section:

There are two ideas.

This first idea helps to calculate a reasonable minimum number of questions:

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.

This 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 have these two groups as close in size as possible. For example: is your number even? The following questions should follow in a similar manner.

Another easy problem: Fake Coin.

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.

A Harder Fake Coin Problem

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.

More Difficult Problem: 12 Coins.

There are 12 coins. One of them is fake; it is either lighter or heavier than normal coins. Find the fake coin and say whether it is lighter or heavier by using the balance in the minimum number of steps.

Solution to the 12 Coins problem.

A Harder Version of 12 Coins.

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?

Problem: Two Glass Balls.

I am in a 100-story building. I have with me two glass balls. I know that if I throw a ball out of the window, it won't ever 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.

Solution for the Two Glass Balls problem.

Problem: Five Chess Players.

There are five 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 for us to determine the order of their strengths?

Problem: Radioactive Balls.

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 is a radioactive ball inside it. As this tool is very expensive to use, how can you find two radioactive balls using the tool the minimum number of times?


Hat Problems

Problem: 100 Prisoners in a Line

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 cannot speak. To pass, no more than one of them may guess incorrectly. If they can agree on their strategy beforehand, how can they be assured that they will survive?

A colorful variation

Same as above with any number of colors.

An infinite variation

The king has a countable number of wise men. The line starts from the left and is infinite in the right direction. The wise men are all facing to the right and they see the infinite tail of the line. Again, the king places either a black or white hat on each head and they can only say one of two words: black or white. Will they be able to devise a strategy beforehand that ensures that not more than one person makes a mistake?

Problem: Rainbow Hats

Seven 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 two men to have hats of the same color. Without communicating with each other, 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 create a strategy beforehand, how can they be assured of winning?

Problem: Probabilistic Hats

Three men are given a challenge. They will all sit in a room and someone will put either a black or a white hat on each one of them with probability one half. The men cannot communicate with each other, but they can see the colors of the hats of the other two men. At the same time, each man says which color they think the hat on his own head is. Each individual can also pass. They win if at least one of them names the color of his hat correctly, and if none of them gives the incorrect answer. How can they maximize their probability of winning?

Problem: Probabilistic Hats. II

The sultan decides to test his hundred wizards. Tomorrow at noon he will randomly put a red or a blue hat — for both of which he has an inexhaustible supply — on every wizard's head. Each wizard will be able to see every hat but his own. The wizards will not be allowed to exchange any kind of information whatsoever. At the sultan's signal, each wizard needs to write down the color of his own hat. Every wizard who guesses wrong will be executed. The wizards have one day to decide on a strategy to maximize the number of survivors. Suggest a strategy for them.

A variation: The wizards are all very good friends with each other. They decide that executions are very sad events and they do not wish to witness their friends' deaths. They would rather die themselves. They realize that they will only be happy if all of them survive together. Suggest a strategy that maximizes the probability of them being happy, that is, the probability that all of them will survive.


Miscellaneous

Problem: Cigarette Butts

A certain hobo who is skilled at making cigarettes 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?

Problem: Two Fuses

You have two fuses that both last one hour, and you have no other ways of telling time. The fuses may be thicker at some points, so in half an hour, 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?

Problem: Only One Fuse

You have one fuse similar to the ones in the problem above. Is it possible to measure 20 minutes exactly?

Problem: A Poison Duel

Once upon a time there was a land where the only antidote to a poison was a stronger poison, which needed to be the next drink after the first poison. In this land, a malevolent dragon challenges the country's wise king to a duel. The king has no choice but to accept.

By bribing the judges, the dragon succeeds in establishing the following rules of the duel: Each dueler brings a full cup. First they must drink half of their opponent's cup and then they must drink half of their own cup.

The dragon wanted these rules because he is able to fly to a volcano, where the strongest poison in the country is located. The king doesn't have the dragon's abilities, so there is no way he can get the strongest poison. The dragon is confident of winning because he will bring the stronger poison.

The only advantage the king has is that the dragon is dumb and straightforward. The king correctly predicts what the dragon will do. How can the king kill the dragon and survive?

Problem: Pebbles

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?

Problem: Equation

Do there exist natural numbers x, y, and z satisfying the equation: 28x + 30y + 31z = 365?


Subtraction Trick Puzzles

Problem: Davidsons

The Davidsons have five sons. Each son has one sister. How many children are there in the family?

Problem: A Stick

A stick has two ends. If you cut off one end, how many ends will the stick have left?

Problem: A Square

A square has four corners. If we cut one corner off, how many corners will the remaining figure have?

Problem: Two Sons

Anna had two sons. One son grew up and moved away. How many sons does Anna have now?

Problem: Crows (submitted by Jonathan)

Ten crows were sitting on a fence. A farmer shot one. How many were left?

Problem: Candles (submitted by Yulia Yelkhimova)

John had four candles and lit them all up. Then he changed his mind and blew out one of the candles. How many candles has he left?

Problem: Apples

At a farmer's market you stop by an apple stand, where you see 20 beautiful apples. You buy 5. How many apples do you have?

Problem: Full House

Mrs. Fullhouse has 2 sons, 3 daughters, 2 cats and 1 dog. How many children does she have?

Problem: A Chandelier

My dining room chandelier has 5 light bulbs in it. During a storm two of them burned out. How many light bulbs are in the chandelier now?

Problem: Fudge

My dog Fudge likes books. In the morning he brought two books to his corner and three more books in the evening. How many books will he read tonight?

Problem: Candy

There were five bowls full of candy on the table. Mike ate one bowl of candy and Sarah ate two. How many bowls are there on the table now?

Problem: Cows

Peter had ten cows. All but nine died. How many cows are left?

Problem: Shots

A patient needs to get three shots. There is a break of 30 minutes between shots. Assuming the shots themselves are instantaneous, how much time will the procedure take?

Problem: Race I (submitted by Victor Gutenmacher)

You are running a race and you pass the person who was running second. What place are you now?

Problem: Race II (submitted by Victor Gutenmacher)

You are running a race and you pass the person who was running last. What place are you now?


Trick Puzzles with Multiplication and Division

Problem: A Stick variation

How many ends do five stick have? What about five and a half stick?

Problem: Chess

Two friends played chess for four hours. How many hours each of them played chess for?

Problem: A Log

It takes 12 minutes to saw a log into 3 parts. How much time will it take to saw it into 4 parts?

Problem: A Caterpillar

A caterpillar wants to see the world and decides to climb a 12-meter pole. It starts every morning and climbs 4 meters in half a day. Then it falls asleep for the second half of the day, during which time it slips 3 meters down. How much time will it take the caterpillar to reach the top?

Problem: Fingers

Humans have 10 fingers on their hands. How many fingers are there on 10 hands?

Problem: Horses (submitted by Yulia Yelkhimova)

Three horses are galloping at 27 miles per hour. What is the speed of one horse?

Problem: Museums

Ten kids from Belmont High School went on a tour of Italy. During the tour they visited 20 museums. How many museums did each kid go to?

Problem: Twins

How many people are there in two pairs of twins, twice?

Problem: Eggs (submitted by Jonathan)

It takes 3 minutes to boil 3 eggs. How long will it take to boil 5 eggs?

Problem: A Rabbit (submitted by Gabe)

On average, rabbits start breeding when they are 3 months old and produce 4 offspring every month. If I put a day old rabbit in a cage for a year, how many offspring will it produce?

Problem: Eggs (submitted by Xi_Heather)

A chicken and a half can lay an egg and a half in a day and a half. How long will it take three chickens to lay three eggs?

Problem: Cucumbers (submitted by Misha)

100 pounds of cucumbers, that were 99% water, got a bit dehydrated, and became 98% water. What is their weight now?

Problem: Friends

Two friends went for a walk and found $20. How much money would they have found if they were joined by two more friends?

Problem: Goldfish (submitted Rua Javari)

One hundred percent of the fish in a pond are goldfish. I take 10% of the goldfish out of the pond. What percentage of goldfish does the pond now contain?


Last revised December 2009