The Puzzled Podcast Abhijith Kesavan

Puzzle

There are four houses on a street: red, blue, green, and yellow. Each house is occupied by a person of a different nationality: American, British, French, and German. Each person also has a different pet: cat, dog, bird, and fish.

Using the following clues, can you determine who owns the fish?


The American lives in the red house.
The British live in a house next to the blue house.
The French owns a cat.
The German lives in the green house.
The bird is owned by the person in the yellow house.
The person who owns the fish lives next to the person who owns the cat.

Who owns the fish?

Welcome to The Puzzled Podcast, a show that explores the fascinating world of puzzles, riddles, and brain teasers. In each episode, we'll dive into a different puzzle, challenge, or mystery and explore the creative thinking and problem-solving skills required to solve it. Today's puzzle is named 'The 100 Prisoners Hat Puzzle'.

There are 100 prisoners in jail, all of whom have been sentenced to death. The jailer, who is feeling somewhat merciful, gives them a chance to go free if they can solve a puzzle. He explains the puzzle to the prisoners as follows:

"You will be placed in a room one by one, and each of you will be given a hat, either red or blue, chosen at random. You can see the hats of the prisoners who come before you, but not your own. Once you are in the room, you may not communicate with any other prisoner or leave the room. Then, you must guess the color of your own hat. If at least half of you guess correctly, you will all be set free. If not, you will all be executed."

The prisoners have one night to come up with a strategy. What strategy can they use to ensure that at least 50 of them go free?

Note: The hats are chosen independently for each prisoner, and there is no collusion between the prisoners beforehand. Also, the prisoners cannot communicate with each other in any way once they are in the room.

You are a prisoner in a strange land, and the king has decided to play a game with you. The game works as follows:


The king will place 100 gold coins on a table in a room that is otherwise empty.
You will then be taken to another room, where you can't see or touch the coins. In this room, there are two levers, labeled "A" and "B".
You must pull one of the levers, which will either flip all the coins or leave them as they are. You don't know which lever does which.
You will then be taken back to the room with the coins, where you can see the result of your lever pull.
You must repeat this process as many times as you like, pulling either lever A or lever B each time.
Your goal is to ensure that there is an even number of heads (i.e. gold side up) on the table when you are finished. If there is an odd number of heads, the king will execute you.

The catch is that you can't keep track of which coins are heads or tails, and you can't communicate with anyone else while you're in the room with the coins. You also can't take any of the coins out of the room with you.

How can you ensure that you always leave an even number of heads on the table, no matter how many times you pull the levers?

Solution.

The key to solving this puzzle is to use binary numbers. Each digit in a binary number represents a power of 2, so for example, the binary number 1011 represents the number 11.



Now, back to the puzzle. If you start with all the coins showing tails (i.e. gold side down), then there are an even number of heads on the table. Each time you pull a lever, you flip some of the coins, so the number of heads on the table changes. Let's say that you pull lever 'A' k times and lever 'B' m times, for a total of k+m pulls. Then the number of heads on the table will be:



N = 100 + k - 2km



Here's how we get this formula. Each pull of lever A flips all 100 coins, so it changes the number of heads from x to 100-x. Similarly, each pull of lever B changes the number of heads from x to x+1 or x-1 (depending on whether there are an even or odd number of heads to start with). We can combine these two cases into one formula:



N = (100-k) + k*(1-2m)



Simplifying this formula gives us the one above.



Now, we need to ensure that N is even no matter what values of k and m we choose. One way to do this is to choose k to be any odd number (such as 1 or 3) and m to be any even number (such as 2 or 4). This ensures that the term k - 2km is always odd, so we get an even number of heads (100 + odd number = even number).



So, for example, if we choose k=3 and m=2, then we pull lever A three times and lever B two times. The number of heads on the table after each pull is:



Pull 1: 0 heads (all tails)

Pull 2: 100 heads (all heads)

Pull 3: 98 heads (two tails flipped by lever A)

Pull 4: 97 heads (one more tail flipped by lever B)

Pull 5: 94 heads (two more tails flipped by lever A)

Since 94 is even, we have succeeded in our task and avoided being executed by the king!

You have been given the task to measure exactly 4 liters of water using only a 3-liter jug and a 5-liter jug. The jugs do not have any markings on them, and you have no other measuring tools. How can you accomplish this task?

You and your friend are caught by the police for a crime, and you are both placed in separate cells. The prosecutor makes the following offer to each of you:

If you both remain silent, you will each get 1 year in prison.

If you betray your friend and they remain silent, you will go free and your friend will get 3 years in prison.

If you both betray each other, you will both get 2 years in prison.

What do you choose?

Three friends decide to split the cost of a hotel room equally. They pay $10 each, totaling $30. Later, the hotel owner realizes that the room rate was only $25, so he gives $5 back to the bellboy to return to the friends. The bellboy, being dishonest, pockets $2 and gives back only $3 to the friends. Now, each friend has paid $9, totaling $27, and the bellboy has $2. But $27 + $2 = $29, so where is the missing $1?