I’ve been reading up more about hinged dissections and came across a shorter paper than the one I mentioned in my previous post. This paper proves that hinged dissections are PSPACE-hard using a reduction from NCL with some neat gadgets.
Now, the puzzle. This is a puzzle I heard from Rachael Harding and is another variant of the prisoner’s hats puzzles:
Suppose you have 5 prisoners. Each prisoner gets a hat with equal probability of being either a red or a blue hat. The prisoners must guess the color of their own hat. They may choose to say “Red,” “Blue,” or “Pass.” If at least one of the 5 prisoners guesses correctly and no prisoner guesses incorrectly (i.e. guesses the wrong color: “Pass” does not mean the prisoner guesses correctly and it does not mean she guesses incorrectly), then they go free. The friendly warden again allows them to discuss a strategy beforehand. However, before the warden hands them their hats, they must choose an order to be asked what hat is on their heads. Then, the warden will give them their hats and ask the prisoners according to the specified order. The prisoners may hear the answers of the prisoners who answered before them.
What is their optimal strategy for being released with high probability?
The answer to the previous puzzle is explained below (highlight to see):
Some figures may be found at http://www.archimedes-lab.org/workshoptangram4.html. The idea is that although the shapes look similar, if you zoom in, the proportions are slightly different. I guess some of you might not like the puzzle as much because the original puzzle figures may not be to scale.