Hat Color Puzzles

Four Fishermen in the Sand

I buried four fishermen up to their necks in the sand on the beach at low tide for keeping their fishing spot a secret from me. I positioned them on either side of a wall, and placed either white or black hats on their heads, as shown in the accompanying photograph I took of them. Knowing only that there are two white hats and two black hats, they must correctly deduce the color of their own hat as quickly as possible. Which one will first be able to do this with 100% confidence? Assume they are sufficiently motivated to deduce, but not make random guesses.

100 Wizards and a Witch

An evil witch / kindergarten teacher / Republican has sentenced 100 wizards / kindergarten students / homosexual atheists to the following fate: After a short amount of time in which they may develop a guessing strategy, the wizards will line up in random order, all facing the same direction, and have white or black hats placed on their heads. Starting at the back of the line (the wizard who can see the other 99 and their hats), the witch will give each wizard one chance to correctly guess their own hat color. This single guess ("white!" or "black!") is also the only way that they are able to communicate with one another (no whispering or coded vocal inflections, etc.). Wizards are not even aware of whether previous guesses were correct or not. Furthermore, the witch can listen as the wizards discuss their strategy before she decides how she will distribute an unknown combination of white and black hats. What strategy should the wizards employ?

Four Fisherman in the Sand
SOLUTION

Fishermen A and B see nothing but wall and are totally out of the loop; they wait patiently, futilely, for any information that might help them. Fisherman C sees a white hat, and cannot immediately deduce anything; he waits for further information. Fisherman D sees a white and black hat, and also cannot make any solid conclusions.

But consider, from Fisherman C's perspective: if Fisherman D saw two white hats (or two black hats), he would be able to deduce his own hat color. Fisherman D's uncertainty and silence is very telling to Fisherman C. After Fisherman C is sure that Fisherman D has nothing to say, he can safely deduce that his own hat is black, says so, and is free.

This information does not help the other fishermen, and they remain silent until their lungs fill with sea water.

100 Wizards and a Witch
SOLUTION

The most obvious strategy is that Wizards #100, #98, #96, etc. name the hat color in front of them, allowing Wizards #99, #97, etc. to guess with 100% accuracy, thereby saving at least half the wizards for sure and, depending on the breaks, about 75 of them on average.

(And no matter what strategy these wizards come up with, the one at the back of the line is doomed to a 50% chance of survival, since no one but the witch ever knows what color his hat is.)

However, there is a surefire strategy that saves the lives of at least 99 wizards. The strategy uses a set of rules (detailed below), whereby each wizard can compare whether the number of black hats he sees agrees with the number of black hats the previous wizard saw. This is all the information needed in order to deduce whether ones own hat is black. Here's the strategy:

• Guessing Scheme A: even # of black hats → guess "black!"; odd number of black hats → guess "white!"
• Guessing Scheme B: even # of black hats → guess "white!"; odd number of black hats → guess "black!"
• The first wizard uses Guessing Scheme A.
• Wizards switch guessing schemes every time they hear "black!"

For simplicity, let's reduce it to a 10-wizard case, pictured here:
Wizard #10 is at the rear, and is the first to guess his hat color. As mentioned before, his own hat color is irrelevant to the overall strategy. He sees 5 black hats in front of him and (incorrectly, poor bastard) says "white!" according to Scheme A.

Wizard #9 now knows two things: 1) He sees an odd number of black hats and 2) Wizard #10 also saw an odd number of black hats. Wizard #9 can safely deduce his own hat is white, as prescribed by Scheme A.

Wizard #8 knows his two buddies saw an odd number of black hats, but he sees an even number of them, so he knows his own must be black, and says so (according, again, to Scheme A).

After hearing Wizard #8 say "black!", Wizard #7 switches to Scheme B, and takes the even number of black hats in front of him to mean his own is white.

And so on.

Monty Hall Problem Revisited

After attempting to answer someone's supposed counterargument in the comments section to my earlier post, I realized that there's a better explanation of the Monty Hall Problem that will hopefully satisfy/silence the doubters. First, I'll restate the problem:

Monty Hall Problem

Of three doors, one is good. First, you select a door. Second, Monty Hall eliminates one of the doors for you - the door he eliminates is not the door you selected, and not the good door. Third, you have the option of keeping your original door, or changing to the only remaining door. What should you do?

SOLUTION

For the sake of this explanation, imagine that you play the game many times, and you always pick Door A, which means Monty will always have to eliminate either Door B or Door C. Every other aspect of the game is still fair and random, meaning that at the beginning of each game, Door A, Door B and Door C have an equal probability of being good.
Now let's consider the moment after you've selected Door A (because you always select Door A in this example) and Monty must eliminate Door B or Door C for you.

1. If Door B is good, he will eliminate Door C (1/3 of all occurences)
2. If Door C is good, he will eliminate Door B (1/3 of all occurences)
3. If Door A is good, Monty must choose whether to eliminate Door B or Door C. He does so with equal probability, so:

• If Door A is good, sometimes Monty eliminates Door C (1/6 of all occurences)
• If Door A is good, sometimes Monty eliminates Door B (1/6 of all occurences)

In 1/2 of all the games you play, Monty eliminates Door C (1/2 = 1/3 + 1/6) and you must then choose between Door A and Door B:
That means that for every 6 times you play the game, you'll have to choose between Door A and Door B 3 times. Of those 3 times, 2 of them will occur because Door B was the good door, and 1 of them will occur because Door A was the good door and Monty randomly eliminated Door C.

And the other 1/2 of the time (3 of every 6 games) you find yourself left with a choice between Door A and Door C, and it's twice as likely that Door C is the good door:
In either event, your chances are better if you change your original selection.

Algebra Puzzles!

As if the word "algebra" wasn't off-putting enough, my first two problems are normally formed using trains, evoking the stereotypical headache-inducing algebra problem ("One train leaves Tulsa going northeast at 60mph, the other..."). I've replaced the trains in an attempt to make the problems more attractive to the few readers I haven't already alienated with this series of posts.

Man in a Tunnel

A man has traveled 1/4 of the way through a tunnel when he notices a giant killer bunny hopping at a constant rate behind him, some distance outside of the tunnel. Whether he continues forward as fast as he can, or turns around and runs as fast as he can, he will exit the tunnel and miss being devoured by the bunny with zero time to spare at either end. How much faster is the mutant bunny than the man?

Supersonic Bee

Two giant killer bunnies, initially separated by a distance of 25 miles, are both hopping at a rate of 100mph, directly towards one another. A supersonic bee begins on one bunny's nose, and flies back and forth between that bunny's nose and the other's at a rate of 800 miles an hour until the bunnies ultimately collide with each other and the bee. At the point of impact, how far will the bee have traveled?

Heaven and Hell

A giant killer bunny dies and finds itself given three unmarked doors to choose from. One leads directly to heaven, one results in a 1-day stay in hell, and one results in a 2-day stay in hell. If the bunny chooses either of the "hell" doors, it will carry out its hell sentence and return to the same three doors, which at that point will have been randomly shuffled, and the bunny gets to choose again. What is the average time it takes a giant killer bunny to get into heaven?

Man in a Tunnel
SOLUTION

I find this problem interesting because it feels as though you're not given enough information to solve it. How fast can he run? How far away is the bunny?

More data would only be helpful insofar as it would make the problem easier to visualize than by using algebraic variables. So let's say it takes the man 1 minute to reach the end of the tunnel through which he entered. At this rate, it would take him 3 minutes to reach the far end of the tunnel, since it's three times as far. Adding the times for these segments together means it would take a total of 4 minutes for this man to run from one end to the other. How long would it take the bunny to cover the same distance? It would take the bunny 1 minute to reach the near end and 3 minutes to reach the far end, so 2 minutes to cover the entire distance of the tunnel. The bunny is twice as fast as the man.

Supersonic Bee
SOLUTION

Solving this problem hinges on realizing how simple it really is. If it actually required adding together all the successively decreasing distances between the bunnies, solving it would not be fun or interesting, and even most nerdy math types wouldn't bother.

All you need to know is speed = distance / time (or distance = speed x time). The bee's speed is 800mph. How long will he be flying? Traveling toward each other at 100mph, the bunnies can each cover 12.5 miles in 1/8 of an hour. So the bee travels at 800mph for 1/8 of an hour: 100 miles.

Heaven and Hell
SOLUTION

Solving this by algebra is more or less straightforward, but it's still very easy to get lost.

Call the answer - the average time it takes a bunny to get into heaven - X. X is the average of three values: the expected times for each door. Door #1 has an expected time of 0. But how can we calculate the others?

If the bunny walks through door #2, it spends 1 day in hell and starts over again. After that 1 day, it can then expect to wait the average time, X. So the total expected time for door #2 is 1 + X. The same reasoning gets you 2 + X for door #3.

Since X is the average of the three values, you need to add those values and divide by 3. Putting all this together you get the equation:

X = ( [0] + [1+X] + [ 2+X] ) /3

Some simple equation manipulation gets you 3X = 3 + 2X and finally X=3. The average time it takes a giant killer bunny to get into heaven is 3 days.

More Puzzles

Back by popular demand no demand whatsoever:

The Monty Hall Problem

Three Doors. One of them is good (it leads to underwear models, funnel cake, etc.) and two are bad (alligators, doctoral theses). You pick one, but before we show you whether the door you picked is good or bad, we generously eliminate one of the bad doors from the other two. Now it's time to make your final decision: Switch to the only remaining door, or stay with your original pick. Should you switch or stay? Does it matter?

Coin Flip Game

You and I flip a coin at the same time, and continue flipping at the same pace until the game is over. You win as soon as you get two heads on consecutive flips. I win as soon as I get a head and a tail, in that order, on consecutive flips. (We tie if both things happen on the same flip.) Who, if anyone, has better odds?


Unlike last week, intuition initially suggests simple and uninteresting answers to both puzzles - "it doesn't matter which door" and "no one has better odds", respectively. Of course, those intuitive answers are not correct.

The Monty Hall Problem

SOLUTION

The intuitive (but wrong) answer, "it doesn't matter", appears to make sense because (1) there are now just as many good doors as bad doors, and (2) you still don't know if your original pick was good or bad. (1) and (2) are both correct assumptions, but the actual answer is that if you switch doors, you'll pick the good door twice as often.

Think of it this way: When you originally picked your door, you had a 1/3 chance of being right. Nothing has changed that fact. When I eliminated a bad door, I was able to do so independent of whether your original pick was good or not. So now there's still a 1/3 chance that your original door is good, and a 2/3 chance that the good door is somewhere else. But "somewhere else" now consists of one option instead of two.

Coin Flip Game
SOLUTION

The intuitive answer is that the game is fair, because in any two consecutive flips, we both have a 25% chance of success, right? In reality, my odds of winning on a given flip eventually tend toward 50%, and your odds of winning on a given flip tend toward just over 19%. The mathematics turns out to be surprisingly complicated, involving patterns related to the Fibonacci sequence and the golden ratio. Figure that out on your own if you're so inclined. If you're not, here's a partial explanation of why the game isn't fair.

What are the chances of success on a given round? If your last flip was heads (good news for you), it's 50%. If your last flip was tails (bad news for you), it's 0%. Same for me. This logic holds as far as the second round. But if it's a later round and we're still playing, that means that nobody won on the previous round, and we can deduce a little more:

You didn't win on the previous round, and you needed HH, so your previous two flips could have been HT, TH, or TT. That's: one scenario in which you might win on your next flip, and two in which you can't.

I didn't win on the previous round, and I needed TH, so my previous two flips could have been HH, TH, or TT. That's two scenarios in which I might win on my next flip, and one in which I can't.

When you consider more and more previous flips, it gets increasingly complicated and the odds skew more and more in my (HT) favor. Here is a partial table of the odds of getting the second of two desired flips on a given round.

For example, if we make it to the 6th round of flipping (meaning you haven't yet made two consecutive heads) then there is a 38.4% chance your most recent (5th) flip was heads, and thus a 19.2% chance you'll get your second consecutive head on that 6th flip.

Puzzles

A while ago I came across a website purporting to list Google job interview questions, all of the brain teaser variety. I thought some of them were unlikely to appear in an actual interview as they've been kicking around for quite a while, but it revived in me a fascination with puzzles and brain teasers, and got me thinking about the different types and qualities of puzzles there are. I've decided to make something of a Monday tradition of presenting different puzzles and their solutions, for at least the next several Mondays.

Boy Country

In a country where people only want boys, every family continues to have children until they have a boy. If they have a girl, they have another child. If they have a boy, they stop. What is the proportion of boys to girls in the country?

Crazy Guy on a Plane

100 airline passengers are waiting to board a plane. They each hold a ticket to one of the 100 seats on the flight. (It doesn't matter, but imagine the first person has ticket #1, and so on.) The first person in line is crazy, and will select a seat at random, possibly even his own. Every person after him will sit in their own seat if it's available, and pick a random one if it isn't. You are the 100th person. What are your chances of getting your own seat?


These puzzles are both fine examples of what puzzles should be, in my opinion, because they fit three important criteria:

• The solution is interesting, because it's not what you expected and/or simpler than you expected
  
• Finding the solution requires only reasoning ability, not knowledge of higher mathematics
• It's not "tricky" in the sense that the solver has to make any less-than-obvious assumptions ("you can melt the ice", "turn the sweater inside out", etc.)

Boy Country
SOLUTION

Using simple reasoning and no mathematics at all, you should be able to convince yourself that this birthing strategy does nothing to alter the natural gender ratio of 50/50 (or 51/49, according to some sources). Families have children. Some are girls, some are boys. Some families continue having children, some don't. As more babies are born, some are girls, some are boys. And so on.

If you're not convinced, consider 64 families. On average, 32 firstborns are boys, and 32 firstborns are girls. Some nine months or more later, 32 of those families give birth again: 16 have boys, 16 have girls. Next round: 8 boys, 8 girls, etc. The mathematics gets a little sticky when you get down to that last baby, but by then you have 63 boys and girls each to back up the 50/50 argument, and on a larger scale it's even more convincing.

Crazy Guy on a Plane
SOLUTION

For any problem involving an arbitrarily large number, it's always best to imagine it on a small scale first and see if any predictable patterns emerge. If it's just you and the crazy guy occupying 2 seats in a Cessna, your chances are 50%. Add one more person. Now the crazy guy has three options: his own seat ("good"), yours ("bad"), or the other person's seat. If he picks the other person's, then that other person has two options: the crazy guy's seat ("good") and yours ("bad"). Still 50%. Now consider the 100 person version. Crazy guy has one "good", one "bad" and 98 other options. If he sits in, say, passenger 57's seat, then passengers 2-56 get their own seats, and #57 has one "good", one "bad", and 42 other options. Any way you cut it, the odds will be 50%.