Waste less time on Facebook — follow Brilliant.
×

Variant of hat problem.

I came across this interesting variant of the typical hat problem, in which people are supposed to guess if their hat is black or white:

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. Furthermore, they are not allowed to repeat a color that was already announced. 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.

Source: Konstantin Knop and Alexander Shapovalov (Tournament of the Towns)

Note by Calvin Lin
2 years, 10 months ago

No vote yet
1 vote

Comments

Sort by:

Top Newest

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. □ Anqi Li · 2 years, 10 months ago

Log in to reply

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 Harsh Depal · 2 years, 10 months ago

Log in to reply

@Harsh Depal Don't you think that saving the last man would be sort of a waste? After all, he is the one that can convey the most information to the rest. Not to sound harsh, but a random strategy can guarantee \( > 1 \) man to be safe. But indeed, what you mentioned is the indeed the idea we should employ: to try to bring as much info as possible to the first few people say. Anqi Li · 2 years, 10 months ago

Log in to reply

@Anqi Li Anqi Li , At first even i was thinking how could we provide information using the last guy to the other men about the hats but i could not find a way because of the restriction that they cannot repeat same color more than once Harsh Depal · 2 years, 10 months ago

Log in to reply

@Harsh Depal Exactly, that's the hard part. But we can manoeuvre past it if we solve the simpler version of the problem first, and notice that the last man gets to choose between 2 different hats. 2 different hats, like I mentioned above in my solution, is the motivation for considering parity. Anqi Li · 2 years, 10 months ago

Log in to reply

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? Shourya Pandey · 2 years, 10 months ago

Log in to reply

@Shourya Pandey Actually not really. The last man can't know his colour because one hat is not being used! Clearly he can hazard a guess but it is obvious that that's not going to be optimal. Anqi Li · 2 years, 10 months ago

Log in to reply

@Shourya Pandey there are 101 hats so the last man still has to guess between 2 colours Starwar Clone · 2 years, 10 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...