Want to buy or sell something? Check the classifieds
  • The Fedora Lounge is supported in part by commission earning affiliate links sitewide. Please support us by using them. You may learn more here.

The Puzzle of 100 Hats

jazzncocktails

A-List Customer
Messages
484
Location
Long Beach, California
Ok, don't know if this is the appropriate forum for this post, but given the hat-centric nature of the article, here it is:

The New York Times offers a science quiz that hat aficionados of the Fedora Lounge might appreciate. Just imagine the word "hat" means fedora. Thought some of you might like to take a shot at this:

The link:

http://tierneylab.blogs.nytimes.com/2009/03/23/the-puzzle-of-100-hats/?scp=2&sq=Tierneylab&st=cse

The full article:

"The Puzzle of 100 Hats"
By John Tierney

Ah, the genius of Lab readers. Lots of you correctly solved the Puzzle of the 3 Hats. (Schin provided an especially clear explanation.) And now we have a clever puzzle involving even more hats and higher stakes — death! It was submitted by Terence Gaffney, a mathematics professor at Northeastern University. He told me he’s found that puzzles are a great way to interest non-mathematicians in math, and he wishes more math courses involved this sort of problem-solving.

“Currently our teaching more closely resembles a karate school with its endless repetition of forms,” Dr. Gaffney said. “Some of that is certainly necessary, but if that’s all there is, it kills folks’ interest in the subject. I hope someday to be able to tell people I’m a math professor and have them volunteer their favorite problem, instead of telling me how much they hated the subject or how bad they were at it.”

Dr. Gaffney wins the contest prize, a copy of Marcel Danesi’s puzzle book, “The Total Brain Workout,” for suggesting a classic brain-twister he came across a few years ago and has been using in his classes. Here’s the Puzzle of 100 Hats:

One hundred persons will be lined up single file, facing north. Each person will be assigned either a red hat or a blue hat. No one can see the color of his or her own hat. However, each person is able to see the color of the hat worn by every person in front of him or her. That is, for example, the last person in line can see the color of the hat on 99 persons in front of him or her; and the first person, who is at the front of the line, cannot see the color of any hat.

Beginning with the last person in line, and then moving to the 99th person, the 98th, etc., each will be asked to name the color of his or her own hat. If the color is correctly named, the person lives; if incorrectly named, the person is shot dead on the spot. Everyone in line is able to hear every response as well as hear the gunshot; also, everyone in line is able to remember all that needs to be remembered and is able to compute all that needs to be computed.

Before being lined up, the 100 persons are allowed to discuss strategy, with an eye toward developing a plan that will allow as many of them as possible to name the correct color of his or her own hat (and thus survive). They know all of the preceding information in this problem. Once lined up, each person is allowed only to say “Red” or “Blue” when his or her turn arrives, beginning with the last person in line.

Your assignment: Develop a plan that allows as many people as possible to live. (Do not waste time attempting to evade the stated bounds of the problem — there’s no trick to the answer.)​

You’re already got enough information to solve the puzzle. But if you’d like an extra hint, you can find it here.

Feel free to post answers here, and to submit more puzzles, either in a comment here or in an email to tierneylab@nytimes.com. (Please indicate whether your puzzle submission is original or not, and please send a solution to tierneylab@nytimes.com.) Thanks for all the answers and puzzles that were submitted previously (including a 20-hat puzzle from Assapopoulos that was received later than Dr. Gaffney’s.) There’ll be another puzzle to solve here at the Lab next Monday.
 

Esov

New in Town
Messages
17
Location
Puerto Rico
Since there's no restriction on how they say "red" or "blue", one strategy is to have everyone except the last person in line call the color they just heard if it was spoken loudly or the opposite color if it was spoken softly. They should speak loudly if the color they are calling matches the color of the hat on the person in front of them; otherwise they should speak softly.

For everyone except the last person, there are four possible scenarios. Naming colors "X" and "Y":

1. You hear "X" loudly and the person in front of you has a color X hat, then say "X" loudly.
2. You hear "X" loudly and the person in front of you has a color Y hat, then say "X" softly.
3. You hear "X" softly and the person in front of you has a color X hat, then say "Y" softly.
4. You hear "X" softly and the person in front of you has a color Y hat, then say "Y" loudly.

The last person in line should say loudly the color of the hat on the person in front of him and cross his fingers!

This saves everyone except the last in line, who is saved only if the last two persons in line happen to have hats of the same color.
 

jazzncocktails

A-List Customer
Messages
484
Location
Long Beach, California
Esov said:
Since there's no restriction on how they say "red" or "blue", one strategy is to have everyone except the last person in line call the color they just heard if it was spoken loudly or the opposite color if it was spoken softly.
Wow, Esov, nicely done! And as long as we save the hat of the last in line, well then things look ok! :D
 

Mr. Paladin

My Mail is Forwarded Here
Messages
3,133
Location
North Texas
HarpPlayerGene said:
Well, if I can't SEE the brim of the hat I'M wearing then it's just not swooped enough - and I simply refuse to die in a poorly styled hat.

Or a red hat for that matter.:D

lol lol lol :eusa_clap
 

avedwards

Call Me a Cab
Messages
2,425
Location
London and Midlands, UK
HarpPlayerGene said:
Well, if I can't SEE the brim of the hat I'M wearing then it's just not swooped enough -
Maybe they thought of that and coloured the underside of the brim black?

Personally I'm not to keen on a red or a blue hat. Grey, brown, tan or black (or green if I'm feeling German) only for me.
 

jazzncocktails

A-List Customer
Messages
484
Location
Long Beach, California
HarpPlayerGene said:
Well, if I can't SEE the brim of the hat I'M wearing then it's just not swooped enough - and I simply refuse to die in a poorly styled hat.

Or a red hat for that matter.

:D
Nice, HPG! But it's a porkpie with the brim turned up...waaay up.

Or a stocking cap.

Or a fez.

In any case, the quiz maker doesn't seem to know hats![huh]
 

avedwards

Call Me a Cab
Messages
2,425
Location
London and Midlands, UK
I have something of a strategy, which could guarantee most people their lives, although it hinges on two factors/assumptions. Firstly that there are 50 red hats and 50 blue ones. Secondly, that all the participants have excellent memories.

So what we do, is that the person at the back looks at the hats in front of him/her and counts how many red and how many blue there are and therefore works out what he/she probably has. The next in line has to remember the result (and all the previous ones) and using that information (as he/she will have heard the gunshot or lack of one) and seeing which hats are in front, he/she works out which hat is probably on his/her head.

Just at a random guess, this should save at least 50%. This is an alternative in case they all have to speak at the same volume.
 

Lefty

I'll Lock Up
Messages
8,639
Location
O-HI-O
nope

Here’s a hint for the Puzzle of 100 Hats in the above post: One plan will save just about all of the people, and there’s a chance that everyone will be saved. This plan is not based on a trick. Nor, by the way, does it depend on assuming that there will be 50 red hats and 50 blue hats — as far as the people know, the hats could be all red, all blue or any mix of the two colors.

If you’re satisfied with that hint, stop reading. But — Spoiler Alert — if you want another hint, you can get one by reading on to the next paragraph.

Here’s the further hint: It is possible to definitely save all but one person, and there’s a 50-percent chance the plan could save everyone.
 

Lefty

I'll Lock Up
Messages
8,639
Location
O-HI-O
The winner answered:

The 100th guy at the end of the line just needs to be instructed to say blue if there is an odd number of blue hats in front of him, and red if there is an even number of blue hats.

All the individuals in front of him will be able to deduce their own hat by counting the number of blue hats in front of himself.
 

Esov

New in Town
Messages
17
Location
Puerto Rico
avedwards: Excellent memories is not an assumption, it is in the problem statement: "... everyone in line is able to remember all that needs to be remembered and is able to compute all that needs to be computed."

Here's the solution based on parity:
http://tierneylab.blogs.nytimes.com/2009/03/23/the-puzzle-of-100-hats/#comment-121571

Although I agree that this is a more elegant solution, voice timing or modulation were not prohibited in the problem statement. If either tactic prompts the executioner to start chopping off heads or to force people to start answering in a rigid format he would be changing the problem at that point. If the executioner considers that a violation of the spirit of the rules he should have prohibited these tactics from the beginning.
 

Forum statistics

Threads
109,140
Messages
3,074,927
Members
54,121
Latest member
Yoshi_87
Top