Hikaru's 3 Hat-Color Prisoner Problem

Posted Aug. 20, 2015. Updated Apr. 4, 2016.

puzzle The author of this puzzle is Hikaru Saito a physicist currently working at Kyushu University in Japan. This puzzle is a variant of the well-known red/blue hat prisoners in a row problem. The solutions are quite different though, and knowing the solution to the traditional problem may actually hinder your ability to solve this one. The puzzle was recently featured in Quanta Magazine's puzzle column alongside the 2 hat variant and a third which was unknown to me! Since the solutions are out there now, I have gone ahead and posted my solution to the puzzle here. The puzzle goes like this:
10 prisoners are lined up single-file. The warden puts colored hats that are either blue, red, or yellow on each of the prisoners. They are lined up such that each prisoner can see the colors of the hats of everyone in front of her, but does not know her own color or those of anyone behind. The warden then, starting from the back of the line, asks each prisoner to state the color of his/her hat. The prisoners are not permitted to say anything other than a color (red, blue, or yellow), and they can only speak it once. The warden will then go to the next prisoner and repeat the question and continue until all prisoners have been asked. At the end, those prisoners who answered incorrectly the color of their hat will be executed. Assuming that the prisoners are permitted to confer with each other before the line-up of doom, what plan could they conceive of which would maximize the number of lives saved? Let us assume that the warden can overhear this plan and adapt his hat-placement choices so as to counter any attempts at reducing deaths. e.g. if all the prisoners decide to announce blue as their color thinking that this could guarantee a 1/3 chance of survival, the warden could simply put red hats on everyone. Feel free to email me if you think you have an answer! (disclaimer: there is no prize for solving it)

The Checkpoint of Truth and Lies

Posted Nov. 10, 2015

puzzle You are a customs agent working at a security checkpoint in the cargo bay of a futuristic space-palace and in charge of ensuring that the food supplies received are of top quality. At the checkpoint, a series of robots bearing foodstuffs will arrive on a conveyor belt, and it is your job to sort the goods along with their robo-handlers into either high quality or low quality categories. High quality goods will go to the kitchens and low quality goods will be sent to the dungeons where a bunch of hungry prisoners (9 of them?) are waiting. The robots bearing the foodstuffs are aware of whether they are carrying high or low quality goods, but from the outside, they are indistinguishable boxes, and there is no discernible pattern as to which robots have high quality goods. After passing through an earlier checkpoint, the robots arriving at your checkpoint are either consistent liars or truth tellers - that is, if asked a yes or no question, they will evaluate its accuracy first and then respond outloud with a YES or NO that either reflects the truth or its opposite, though you do not know which robots are which. You have limited tools to perform the sorting: a display screen hanging above the conveyor belt upon which you can write a question for the robots to see, and a Y-shaped sorting belt which will either send robots on the conveyor belt off towards the kitchens if the word YES is uttered or towards the dungeons if the word NO is uttered. What question for the robots can you post on the display screen in order for the robots to be correctly sorted such that high quality goods go to the kitchens and low quality goods go to the dungeons? e.g. if you wrote "are you a robot?" then all the lying robots would say "NO" and get sent to the dungeons.