Hats of three colors

[bonanova]

One hundred prisoners stand in a straight line seeing those visible to them only from the back. You get the picture, back guy sees 99 others, front guy sees no one. They are fitted, one each, with a hat, whose color is uniformly randomly Red, White or Blue. Each prisoner must guess the color of his own hat, without having seen it, by saying one of the three colors, and he is executed if he is wrong. The guesses are made sequentially, from the back of the line to the front. The guesses are not identified as to their accuracy, and no prisoners are executed, until all 100 guesses are made.

The prisoners may collaborate on a strategy, with the object of guaranteeing as many survivors as possible. (Their communication ends, of course, once the first hat is placed.) How many can be saved, in the worst case?

[ThunderCloud]

I think…

Spoiler

99 can be saved. Let's assign numeric values to the colors: Red = 0, White = 1, Blue = 2. The person in the back of the line guesses the color corresponding to the sum of the 99 hat colors in front of him modulo 3. Then each of the other 99 prisoners can deduce their hat color from that total and from the other 98 hats (which they see ahead of them or listen for behind them).

 

[Izzy]

Here's a better solution. 

We can save 98 people. 

Let white = 0, red = 1, black = 2. Counting only the first 98 people, the last person in line states how many white hat he sees modulo 3. The next person says how many red hats he sees modulo 3. If the 97th person sees the same number of red and white hats modulo 3, he knows his hat is black. Otherwise, he sees one less red or white hat modulo 3, and knows that is the color of his hat. Continue in this fashion. 

[Izzy]

 

I can save at least... 

 

 

 

90 people for sure, and 93 people on average. Sacrifice the last ten people in line. Let white = 0, red = 1, black = 2. Counting in base 3, the last five people in line will say the colors of the hats that correspond to the number of white hats among the first 90 people in line.  For example, if there are 17 white hats among the first 90 people,  since 17 is 00122 in base 3, the last five people would say "White. White. Red. Black. Black."  Similarly,  the next group of five people repeats this process for the red hats. The remaining hats among the first 90 prisoners must be black.  Each of the remaining 90 prisoners will be able to deduce the colors of his or her hat by subtracting properly. For example, if it is known to the 90th prisoner that there are 30 red hats, 10 black hats, and 20 white hats, and he counts only 19 white hats before him, he knows that his hat is white, and says "White." Then, the 89th prisoner updates the running totals of each color of hat and continues this process. 

Note that it is possible to encode all numbers between 0 and 90 in base 3 by using  at most five digits. However, in the worst case scenario, there may be  at least 81 (10000 in base 3) white hats or red hats, requiring five people in encode a single number. Since this can happen in either order, ten sacrifices are required this way. I tried a slightly different method where the last prisoner signals the color for the least number of hats of a certain color, and then it only takes four prisoners to say the number of those hats, but if you continue with this process it still ends up taking ten prisoners in the end.

Of course, I am unsure if this is the absolute best method, but saving 90 people seems like a good start at least! 

Edited January 21, 2018 by Izzy

[Donald Cartmill]

Spoiler

Worst case is 50 saved.   The prisoners agree that beginning with #100 an even number ,,every even numbered prisoner will state that his hat is the color right in front of him .    I am  an odd numbered prisoner ,I know that the prisoner behind me will be calling the color of my hat.  It matters NOT how many different colors are in use.  The even numbered prisoner will be stating the color of the prisoner directly in front of him,  i.e. an odd numbered prisoner will always know his hat color.   This is worst case scenario 50 saved.     A case could be made ( with only 3 colors in play ) ,whereby statistically 1/3 of the remaining 50 even numbered prisoners  will have selected their own hat color as well.

 

Edited January 22, 2018 by bonanova
spoiler added

[Donald Cartmill]

Spoiler

 Proceeding like Izzys' solution.  99 can be saved .   # 100 says he can see 35 white hats ; 35 red hats but this does NOT allow him to guess his own color.  #99  If he sees the same number of white and red hats knows his hat is black.  Proceed in this manner and the only prisoner unable to be sure of color is prisoner #100

 

Edited January 22, 2018 by bonanova
spoiler added

[bonanova]

@Izzy Very close.

@Donald Cartmill OP restricts what each prisoner is allowed to say:

Each prisoner must guess the color of his own hat, without having seen it, by saying one of the three colors

[Donald Cartmill]

2 hours ago, Donald Cartmill said:

  Hide contents

Worst case is 50 saved.   The prisoners agree that beginning with #100 an even number ,,every even numbered prisoner will state that his hat is the color right in front of him .    I am  an odd numbered prisoner ,I know that the prisoner behind me will be calling the color of my hat.  It matters NOT how many different colors are in use.  The even numbered prisoner will be stating the color of the prisoner directly in front of him,  i.e. an odd numbered prisoner will always know his hat color.   This is worst case scenario 50 saved.     A case could be made ( with only 3 colors in play ) ,whereby statistically 1/3 of the remaining 50 even numbered prisoners  will have selected their own hat color as well.

 

 

[bonanova]

@ThunderCloud Nailed it.

@Izzy Honorable mention