Hats and Rooms
Source: Tanya Khovanova’s Math Blog
Problem: The Sultan decided to test the wisdom of his wizards. He collected them together and gave them a task. Tomorrow at noon he will put hats of different colors on each of the wizard’s heads.
The wizards have a list of the available colors. There are enough hats of each color for every wizard. The wizards also have a list of rooms. There are enough rooms to assign a different room for every color.
Tomorrow as the Sultan puts hats on the wizards, they will be able to see the colors of the hats of the other wizards, but not the color of their own. Without communicating with each other, each wizard has to choose a room. The challenge comes when two wizards have the same hat color, for they must choose the same room. On the other hand, if they have different hat colors, they must choose different rooms. Wizards have one day to decide on their strategy. If they do not all complete their task, then all of their heads will be chopped off. What strategy would you suggest for the wizards?
Update (Dec 04, 2010)
Solution: One solution posted by Siddhant Agarwal (EE 4th year, IITB) in comments! Another solution posted independently by Hasan Kumar Reddy (mintuhouse) (CSE 2nd year, IITB) and Saurabh Joshi (PhD Student, CSE, IITK). Thanks.
Problem: The Sultan decided to test the wisdom of his wizards. He collected them together and gave them a task. Tomorrow at noon he will put hats of different colors on each of the wizard’s heads.
The wizards have a list of the available colors. There are enough hats of each color for every wizard. The wizards also have a list of rooms. There are enough rooms to assign a different room for every color.
Tomorrow as the Sultan puts hats on the wizards, they will be able to see the colors of the hats of the other wizards, but not the color of their own. Without communicating with each other, each wizard has to choose a room. The challenge comes when two wizards have the same hat color, for they must choose the same room. On the other hand, if they have different hat colors, they must choose different rooms. Wizards have one day to decide on their strategy. If they do not all complete their task, then all of their heads will be chopped off. What strategy would you suggest for the wizards?
Update (Dec 04, 2010)
Solution: One solution posted by Siddhant Agarwal (EE 4th year, IITB) in comments! Another solution posted independently by Hasan Kumar Reddy (mintuhouse) (CSE 2nd year, IITB) and Saurabh Joshi (PhD Student, CSE, IITK). Thanks.
May be this can be tried.
ReplyDeletestrategy would be all of them assemble in front of each room , count the number of ppl wearing a hat of that colour and say wizard X would go inside if he can see alteast one guy wearing a hat of colour corresponding to that room. someone else could atleast two guys, he also enters it. And this continues. Finally everyone would know the number of people wearing hats of that colour if they count the people inside. If the number of people inside is one less than what he counted initially, he must have been wearing a hat of that colour. Now everyone would move to next room and this continues till evry one knows which hat he is wearing.
I hope this soln is right:
ReplyDeletenumber the rooms from 0,1,..,n-1 in some order
and the colours C0,C1,...,C(n-1).
now a person who sees Ci1,Ci2,Ci(n-2)
should go the room i1+i2+...+i(n-2) mod (n).
Clearly if two persons hav the same hat colour they will see identical colour pattern on other people and hence will go to same room. Also as (if i,j belongs to 0,1..,(n-1) and (i-j)=0 (mod n) implies i=j) implies people with different hat colurs will go to different rooms
Well, we can come up with an ordering on color. For example, if there are 3 color, R < G < B. Now, we can divide them into two partition, R and not R. This reduces to black and white hat puzzle, so every wizard with R will be able to figure out that they have R in O(R) time. So they pick a room, next the divide between G and B. Same thing can be done for arbitrarily large color. This is a naive strategy however, and I am sure it can be improved.
ReplyDeleteThis strategy allows at most 1 wizard to die but no more. Number the rooms from 1 to m and the colors from 1 to n. Now the first wizard sums all the colors on the hats of all the other wizards and computes Sum mod n. He then speaks out the color corresponding to that number. He may or may not be right. But this allows all the other wizards to infer what is the color of their hats. This is because lets say there are 10 wizards, the first wizard sums all the hat colors of the 9 wizards hats to say X and computes X mod n. The 2nd wizard now computes the sum of the remaining 8 wizards hat colors that he can see to say Y, then based on the uniqueness of Y mod n, Y+1 mod n, Y+2 mod n ... Y+n-1 mod n, he knows what number/color his hat has so that Y+c mod n = X mod n.
ReplyDelete@mintuhouse.. It makes sense. In fact, the solution you are suggesting is a variation of http://pratikpoddarcse.blogspot.com/2009/10/another-hat-puzzle.html
ReplyDelete@siddhant. I think your solution is correct. Thanks.
@saurabhjoshi.. thanks for commenting. your solution is same as mintuhouse's solution
@achilles.. I think you are trying to solve a different problem. :P
Cheers!
The source of the problem is http://blog.tanyakhovanova.com//?p=255