Hats and Rooms
Sergei just came back from MOP — Mathematical Olympiad Summer Program, where he was a grader. The first question I asked him was, “What was your favorite math problem there?” Here it is:
There are wisemen, hats and rooms. Hats are of different color and there are enough hats of each color for every wisemen. There are enough rooms, so that you can assign a different room for every color. At some moment in time the sultan puts hats on the wisemen’s heads, so as usual they see all other hats, but do not see their own hat color. At the same time, each wiseman has to choose a room to go to. If two wisemen have the same hat color, they should go to the same room. If they have different hat colors, they should go to different rooms. What strategy should the wisemen decide upon before this event takes place?
Oh, I forgot to mention the most interesting part of this problem is that you shouldn’t assume that the number of wisemen or hats or rooms is finite. You should just assume that they have the power of choice.
Share:
Srichand:
Well, one person could be assigned as the “sorter”. Once the sorter groups everybody based on their color in front of one door for one color, each person “knows” what color hat is on their head based on the group color they see around them. Then, the group that sees their color on the sorter’s head then claims the sorter.
5 July 2010, 2:56 pmBill:
Before the event, each of the n wisemen is assigned a unique number from 1 to n.
After the hats are placed, you (as one of the wisemen) can assign each of the t colors a unique consecutive number from 1 to t, in the order that they appear on the numbered wisemen’s heads.
Add together the binary representations of the numbers for the colors of which you see an even number of hats. You will add these binary numbers together without carrying (XOR addition).
The final result will be the binary representation of the room number you should enter.
I think this is correct, since your number will differ from the number of an outside observer by a unique binary code that only applies to your color.
If I got it right, I learned the technique from participating in this blog!
5 July 2010, 6:41 pmBill:
Okay, this won’t work, because the wisemen who have the first appearance of each color will order the colors differently. Also, if any color only belongs to one hat, that wiseman will not even know the correct number of colors.
Nevermind.
5 July 2010, 6:46 pmcolorblind:
Srichand: I there is an error in your solution. The sorter can only enter their room after identifying all other wisemen’s rooms. The problem states they must all enter at the same time.
I assume we can safely assert we need only consider 1 room of each color. Duplicates will be ignored.
Each unique room will be assigned a number r from 1 to R.
Each wiseman will be assigned a number w from 1 to W.
Each hat color will be assigned a number c from 1 to C. whenever r = c the the color of room(r) is the same color as hat color(c).
Wiseman(w) will stand in front of room(r) whenever r=w. At the time of choosing wiseman will point to all hats such that hat color (c) matches the color of room (r). If and when w > max(r) that wiseman(w) need not participate in the pointing. At the assigned time, each wiseman will go into the room of the wiseman who pointed at them was standing in front of.
My only concern with this solution is that it is possible that any one room (or all of them!) may house infintely many wiseman. The wiseman who has to point to infinitely many of his neighbors would be very taxed, to say the least.
6 July 2010, 12:03 amSergei:
The problem should state that there is no communication between the wise men once they see the hat colors of the other wise men. Each wise man simply sees the colors on the heads of the other wise men, and from that information alone he must decide which room to go to.
6 July 2010, 11:09 amJBL:
I consider the following problem:
There are W wisemen and C ≥ W colors. The wisemen are forced to play the following game: at the beginning, they may meet to decide on a strategy. Afterwards, they are locked in separate cells, and each is given a hat in one of the C colors. From a cell, the only possible communication is to observe the color of the hats given to the other wisemen. Each cell contains a keypad with R ≥ C buttons (and the wisemen were aware of this during their strategy session). After observing the colors of the hats of the other wisemen, each must press a button. The wisemen win if two wisemen press the same button if and only if they have the same color hat on.
Solution included in this comment; don’t read if you want to keep working!
Tanya, this reminds me of the chessboard and pawns problem. The wisemen choose an abelian group of order C, a bijection between the elements of this group and the possible colors and an injection from the group to the buttons. Then they play as follows: each wiseman observes the colors of the hats of all other wisemen, associates to each hat its group element, computes the sum of these elements, and presses the associated button. Under this scheme, two wisemen press the same button if and only if they are wearing the same color hat. This procedure works for any cardinalities, provided we have enough axioms to ensure an abelian group of every cardinality.
6 July 2010, 4:13 pmBill:
Does this solution assume that the wise men know how many colors there will be? Even after the hats are assigned, each wise man doesn’t know if his hat is a unique color. Also, the original problem doesn’t say that the number of rooms equals the number of colors, only that there are “enough” rooms. Does this allow the possibility that there may be more?
And yes, I think we must assume there is no communication between the wise men other than seeing the hats. Otherwise, they could just ask each other what color hats they have and discuss who should go to what room.
7 July 2010, 6:53 pmJBL:
Yes, my solution assumes that the wisemen know (an upper bound on) the number of colors. In this case it doesn’t matter if there are more rooms (in my phrasing, buttons) than the number of colors, since they may just agree to consider a subset of the buttons of the same cardinality as the set of colors.
8 July 2010, 7:37 ammisha:
@JBL: If the number of the wisemen and the colors are both infinite, you need the infinite sums i.e., some extra structure in your group of colors, i.e. a bit more than an abelian group structure.
10 July 2010, 7:35 pmmisha:
Actually you need infinite sums even if the number of wisemen is infinite, and it’s not clear it works out.
10 July 2010, 7:41 pmmisha:
Let us take an example. Assume the hats are black or white, the number of men wearing black hats is infinite, as well as the number of men wearing white hats. What algorithm should they use, JBL?
10 July 2010, 9:51 pmJBL:
Yes, you’re right, my solution requires a finite number of wisemen (but allows any cardinality of the color set).
11 July 2010, 11:06 amIlya:
If the numbers are infinite then I know how to use the axiom of choice to make sure that all but finitely many of them will come to the right rooms (i.e. all but finitely many wise men with the hats of the same color will be in the same room, and in any but finitely many rooms all the hats will be of the same color, and in the remaining rooms all but finitely many hats will be of the same color), but I wonder if the problem as you have stated it has a solution?
12 July 2010, 7:35 amIlya:
In fact what I had in mind allows to find a strategy for a stronger problem: namely, if the rooms are colored in the colors of hats, and all but finitely many persons must get to the correct room. However, the idea seems to be similar. Let me consider for simplicity the case of only 2 colors but infinitely many wise men. let us order the wise men and consider sequences of 0 and 1 ordered by the set of wise men. Say two sequences are equivalent if they coincide everywhere but at finitely many places, and let us choose a sequence in each equivalence class. Now the strategy is the following: the rooms are labeled by 0 and 1. Any wise men sees the whole sequence of 0 and 1 but his own digit, hence he sees the equivalence class. He compares the chosen element with what he sees and counts the number of disagreements. He ads to this number the digit that appears in the chosen representative at his own place, and if the result is even he goes to room 0 otherwise to room 1.
12 July 2010, 12:36 pmTanya Khovanova:
Ilya,
What will happen if he doesn’t add the digit in his own place?
12 July 2010, 2:54 pmIlya:
Tanya, I’m not sure I understand the question. If he doesn’t add the digit in his own place the algorithm can’t work since all people with correct hat (i.e. the number on the hat coincides with the corresponding digit in the chosen representative) will go to the same room…
13 July 2010, 11:05 amTanya Khovanova’s Math Blog » Blog Archive » Hats and Rooms. Take II:
[…] recently published a puzzle about wizards, hats of different colors and rooms. Unfortunately, I was too succinct in my description and didn’t explicitly mention several […]
16 July 2010, 5:19 pm