Variant of hat problem.

Let us attempt an easier problem first, and see how this problem can help us solve the above variant:

A king decides to give 100 of his wise men a test. The wise men will stand in line, one behind the other, so that the last person in the line sees everyone else. The king has 2 hats, black and white, and the wise men know all the colors. The wise men can only see the colors of the hats on people in front of them. Then, in any order they want, each wise man guesses the color of the hat on his own head. Each hears all previously made guesses, but other than that, the wise men cannot speak. Each wise man who guesses his color wrong will get his head chopped off, and the ones who guess correctly go free. Find a strategy that will minimize the number of wise men who die.

This is an all time classic, but let us still solve it anyways. A (quite) reasonable preliminary guess is that at least half of the wise men need to risk their life. But this is under the assumption that they make random guesses . As we shall see, we can drastically minimise the number.

Basically, the "I know that you know that I know, etc." idea should be employed here, to let the wise man, on their turn, convey as much information as he can to the other wise men before him. So what can he encode? Let us examine our options, in fact, we don't really have much:

1. The colour of the hats of the people before him. Well, we see that he can see one more hat than the wise man directly in front of him. This motivates us to think of parity. WIth this in mind, we are done, for we can assign each hat a weight according to the colour of the hat, say, $\text{white} = 1, \text{black} = 0$ and he announces the corresponding colour on his turn. This way, everyone else would live.

2. I give up (obviously not the choice)

Now we are done with the classical one, let's attempt yet still a modified version of this:

A king decides to give 100 of his wise men a test. The wise men will stand in line, one behind the other, so that the last person in the line sees everyone else. The king has 101 hats, each of a different color, and the wise men know all the colors. The king puts all but one of the hats on the wise men. The wise men can only see the colors of the hats on people in front of them. Then, in any order they want, each wise man guesses the color of the hat on his own head. Each hears all previously made guesses, but other than that, the wise men cannot speak. Each wise man who guesses his color wrong will get his head chopped off, and the ones who guess correctly go free. Find a strategy that will minimize the number of wise men who die.

The solution to this problem is motivated by that to the classical one. There, if you see closely, we took $\pmod{2}$. Taking up the idea there, in fact it is error-correcting codes, we should encode the colours here by $\pmod{101}$. I suggest that the interested reader to pursue reference books on this topic.

But here's the tough and problematic part of the original puzzle: They are not allowed to repeat a color that was already announced. Let us try to be smart and modify our previous strategy to overcome this obstacle. So we notice that if a wise man that is "before" the last has his colour of his hat already said then he will screw up the whole plan for the people before him. Is it possible for him to indicate to the rest that he is forbidden to say that particular colour? (This is always the question to ask - can we convey more information?) Well, yes. Let us recall that they each have a different coloured hat. So if the unlucky wise man says the colour of some specified wise man, then he can indicate to them that he is screwed. The best bet would then, logically, be the first man. This fixes our strategy.

However, although we have achieved sacrificing way less that half of the people, I feel that the answer should be, just like the classical problem, to be $1$. Now, my thoughts are that since there are $101$ colours and only $100$ men, 1 colour will not be used! As we have seen above, the problematic part is really what happens if we have repetitions. But now the last wise man has 2 colours to pick, but which should he choose?

Again, the idea of having 2 colours to choose from should motivate the idea of encoding odd and even. But odd and even what? Let us think. What does an ordered $100$-triple like $\{c_1, c_2, \ldots, c_{100} \}$ remind you of? Why, permutations! Thus, like the idea of an ordered triple, assign each colour a number (isn't that what we do in cryptography?) and the last wise man chooses the hat that forms an even permutation. Clearly, each wise man before the last guy (he still has $\frac{1}{2}$ the probability of staying alive) has just to choose between $2$ permutations that differ by an element. They always pick the one with the even permutation. It is clear that we are done. □

If the wise men know all the colours, the last person can easily know his colour. Then the second last man , who hears the last man, can also know his colour...and so on. Is this correct, or did I interpret the question incorrectly?

I think at least 1 man can be saved, the wise men will make a strategy, they will assign some kind of code for ex- let the second last man be wearing a hat of color 'xyz', they will make a code according to which if the man before shouts 'abc' that will imply that next man is wearing a hat of color 'xyz'. So this can be one of the strategy which can save some wise men . I don't know how many but i am sure this strategy will save at least 1 of the wise men . i.e atleast the last man will be safe