This week's brain teaser will boldly go where no puzzle has gone before. Try and keep up.
This week's puzzle was created by University of Kentucky mathematician Raphael Finkel, and recommended by io9 reader Shahab Tasharrofi. " I created the puzzle as a test case for some software I wrote that assists puzzle creators," Finkel told me when I asked for his permission to feature the puzzle in our weekly puzzle series. "I wanted to try out some pretty complex clues that my software handles." He adds: "I think, by the way, that this puzzle is extremely difficult."
Sunday Puzzle #10: Six Fearsome Heroes
Grobly Grizik is planning to write a novel fashioned after Star Trek: The Next Generation. In this novel, six of the crew members compete both at Fizzbin and at Tridimensional chess. Each crew member gets two independent rankings for ability at these games, with 1 ranked lowest and 6 highest. Every crew member has a personal hero among the crew, and every crew member is afraid of some crew member. Everyone is the hero of somebody, and everyone is feared by somebody. Nobody either fears him/herself nor counts him/herself as a hero. Nobody fears his/her own hero. From the given clues, discover every crew member's ranking at Fizzbin and at Tri-D chess, as well as whom he/she fears and whom he/she counts as a hero:
- Geordi ranks 2 at Tri-D Chess.
- Picard ranks two positions behind Troi at Fizzbin.
- Troi is feared by the person Geordi fears.
- Worf's hero ranks 3 times lower at Tri-D Chess than the crew member who is best at Fizzbin.
- Picard's hero fears Geordi.
- Data's hero is not Geordi.
- Data is the hero of Riker's hero.
- The person who is worst at Fizzbin is better than Troi at Tri-D Chess.
- The person ranked number 3 at Tri-D Chess is ranked 4 positions higher than Data at Fizzbin.
- Riker is feared by the person Picard fears and is the hero of Worf's hero.
- Riker is ranked 2 lower at Tri-D Chess than the crew member ranked 2 at Fizzbin.
We'll be back next week with the solution – and a new puzzle! Got a great brainteaser, original or otherwise, that you'd like to see featured? E-mail me with your recommendations. (Be sure to include "Sunday Puzzle" in the subject line.)
Art by Jim Cooke
Solution To Sunday Puzzle #9: The Puzzle Of 100 Hats
Last week, I asked you to save the lives of as many hat-wearing prisoners as you could. One of the hints I provided was that you could save a lot more than 50 of the 100 lives on the line. In fact, I said, the best plan would definitely save 99 lives, and leave only one life to chance.
Right away, several of you seized on a solution to this problem involving intonation that, I admit, is a pretty clever workaround. Xilonen03 was the first to provide this alternate solution and gave, I think, the clearest explanation for how it would be carried out:
I'd simply have the last person in line announce the color of the hat of the 99th person. Person 100 has a 50% chance of living, but from there on out, everyone can live. Person 99 now knows the color of their hat, and hopefully it's not covered in blood spatter. If the color of their hat matches that of the person in front of them, they will announce the color as a statement; if the color of their hat does not match that of the person in front of them, they will announce their color as a question.
So it would look something like this:
100: Red. (person 99's hat is red)
99: Red? (person 98's hat is blue)
98: Blue. (person 97's hat is blue)
97: Blue? (person 96's hat is red)
etc etc etc...
I actually really like this solution. It's quite clever. But it's not the answer I was looking for. And, in fact, many of you pointed out that Xilonen03's solution kind of violates the spirit of the puzzle, which is meant to be solved with logic, and need not be left to either the performance or interpretation of vocal quirks.
The first person to provide the solution we were looking for was Niro1, who wrote:
The solution below allows 99 prisoners to guess their hat color right with certainty.
the last prisoner in the column counts the number of red hats in front of him (he can see all the other 99) if he sees an odd number of reds he shouts RED and if he sees an eve number of red he shouts BLUE. the next person and all the other prisoners after that can deduce their color and shout the correct number.
For example lets assume that prisoner 99 has a red hat, 98 has a red hat and 97 has a blue hat and totally there are 46 blue hats and 53 reds:
Prisoner 100 sees 53 red hats so he shouts RED.
prisoner number 99 sees only 52 red hats (he cant see the one on his own head) which is an even number but prisoner 100 shouted RED for an odd number of reds so there is one red hat missing so he knows he is wearing a red hat.
Prisoner 98 sees only 51 red hats but he he knows that prisoner 100 saw an odd number of reds and prisoner 99 already shouted red so he should see an even number but he sees 51 (an odd number) so again one red hat is missing - the one on his head.
Prisoner 97 is expecting to see an odd number of red (because we started with an odd number of reds and 2 people behind him already said they are wearing red hats) and indeed he sees 51 red hats - so he shouts BLUE
And so on...
Northeastern University mathematics professor Terence Gaffney has some helpful advice on how to simplify, solve, and understand problems of this nature:
One hundred prisoners are too many to work with. Suppose there are two. The last person can save the guy in front of him by shouting out the color of his hat. OK, how about if there are three? The third prisoner can see 0,1, or 2 blue hats. There seem to be three possibilities but only two choices of things to say. But, two of the possibilities have something in common–namely the number of blue hats is even. So if the last prisoner yells "blue" then he can tell #1 and #2 that he sees an even number of blue hats. Then the second prisoner, by looking ahead and counting the number of blue hats, knows his must be blue if he sees one blue hat, and red if he sees no blue hats. The last prisoner agrees to yell "red" if the number of blue hats seen is odd. Then if #2 sees a blue hat on #1, his must be red, and if #1 has a red hat, his must be blue. By shouting out the color of his hat, #1 also knows his hat color. Two "blues" or two "reds" in a row mean he wears blue, while one blue and one red means he wears red. OK. This looks like this always works, because there are always only two possibilities as far as the number of blue hats worn–they are either even or odd. So, check as in the three person case that using this strategy ("blue" for an even number of blue hats "red" for an odd number) tells #99 the color of his hat, and then each prisoner in turn can learn the color of his hat by taking into account the parity of the number of blue hats he can see, the parity of the number of blue hats #100 saw and the number of prisoners behind him wearing blue hats.
Remember: Puzzles like this one can seem big and unwieldy at first glance, but can often be simplified. (Think back to the 100 Green-Eyed Dragons puzzle.) When approaching a new puzzle, always ask yourself: Have you seen this or a related problem before? Have you seen a similar unknown before? Can you restate the problem? If you can't solve this problem, can you solve a similar or simpler problem?
Previous Weeks' Puzzles
- You'll Need All 3 Clues To Solve This Puzzle
- Think You Know The Solution To This Classic Riddle? Think Again.
- "The Hardest Logic Puzzle In The World"
- 100 Green-Eyed Dragons
- Can you figure our this parking lot's numbering system?