(Close Window) 
Topic: A hat problem 


Ever head of a forest called Gnome Man's Land? Guess who lives there? Gnomes of course! These gnomes have lived in this dark forest for so long that their pointy little hats, which were either red or blue, had grown attached to their heads. Noone knew any longer the colour of his own hat. Every day, they went along a narrow path in the woods to a big clearing, where the headgnome would do a head count and see that all 424 gnomes were present. But, one day the headgnome said: "Folks, I am getting old, and I can't see very well, particularly when all your blue and red hats are so mixed up. It's all a bit of a blur. Tomorrow, just to make it easier for your old chief, would you please all stand according to colour." And the next day, all the gnomes trolled down the path to the clearing one by one, and stood exactly as the head gnome had requested: all the blue hats on one side of the clearing, all the red hats on the other. And the chief looked at the red hats, looked at the blue hats, and saw that all were present. But the question is how they had managed to do it, given that they could not possibly know the colour of their own hats, and they would never dream of asking each other the colour of their own hats or, worse still look in a mirror and they didn't tell each other where to stand... 


One would be in charge and say you (blue hat ) on this side,and you (red hat) stand on this side,then when all are sorted,he stands in between them and says where do I stand, then next time to stand in the same place.Mike 


Its not as simple as that mike, I think there are some rules and restrictions that were not mentioned in the original post. :kewl: 


This would take a long time, but it could be done this way. A group of two gnomes would have no idea if they had hats of the same color, but no other gnome would join them if they did not. IF they did have the same color, then a third would join them. If it's color was the same, the other two would stay. If they saw it was different from their partned, they would wander off and join another group (and would know the color of their hat). In this way, everyone would quickly know the color of their hats, never admitting to the others that they had forgotten. 


Assuming there is at least one Blue hatted gnome this could work: They decide that after N minutes N Blue hatted gnomes should walk to a certain spot IF there is exactly N Blue hatted gnomes in the forest. It will take at most 7 hours and 4 minutes so they will be ready in good time for the next day. /Tomas 


Hmmm, the strategy I posted will work even if there are no Blue hatted gnomes, I realize. In that case everyone would think they have Blue hats and move to that spot at minute one, only to find that everyone that joins has Red hats. The conclusion then will be that everyone has Red hats and the problem is still solved. /Tomas 


I know the solution to this but wont spoil it for everyone. you guys will like it. its almost like a "self working trick" This is not a matter of time tomas. it could even take them couple of minutes to sort themselves out. Did I give away too many clues ? ? :) :kewl: 


Mike's suggestion of ordering people where to stand is not allowed, as was stated in the final sentence of the puzzle. Sapients suggestion of joining groups is sort of on the right lines. Thanks Mehtas for not saying the solution. Would I be right in assuming that you heard this on the Radio? 


Stephen, someone asked me few days ago. it took me ten minutes to get the solution right. :kewl: 


Fortunately at least one of then had an elf friend who gave them small buttons to match their hats. 


[quote] On 20050805 06:16, TomasB wrote: Assuming there is at least one Blue hatted gnome this could work: They decide that after N minutes N Blue hatted gnomes should walk to a certain spot IF there is exactly N Blue hatted gnomes in the forest...[/quote] Tomas, please explain how this would happen. 


Jonathan, Let's assume there is a single Blue hatted gnome. He would look around and se all Red hatted gnomes so he'd know that he is a Blue hatted gnome and move to the spot at minute 1. Assume there are two Blue hatted gnomes. Everyone but them would see two Blue hatted gnomes while they would only see a single Blue hatted gnome each. When they have nott seen the Blue hatted gnome move to the spot in minute 1 they of course both go at minute 2. Same strategy if there are more Blue hatted gnomes: If you see M Blue hatted gnomes and they have not moved to the spot in minute M, then you yourself should move to that spot at the next minute. This will lead to that all Blue hatted gnomes will go to the spot at the same time. While this works, I'm very curious about the solution that doesn't involve time slots. /Tomas 


Ah, instead of using time slots you could use 424 positions in the forest. If a gnome sees M Blue hats he stands in the position numbered M. ...and all of a sudden I see a solution. ;) The rule is: If you see an even number of Blue hats, stand on the left, and if you see an odd number of Blue hats, stand on the right. /Tomas 


The problem with that suggestion is that you may end up with reds standing on either side of the blues 


[quote] On 20050805 11:31, TomasB wrote:...The rule is: If you see an even number of Blue hats, stand on the left, and if you see an odd number of Blue hats, stand on the right...[/quote] I'm missing something When I imagine this process I see: First blue hat comes over, sees zero and so stands to the left Second blue hat sees one, so stands to the right. Thrid sees two and so stands to the left. later on, a red hat comes along and sees to rows of blue hats. Please provide more details. 


Jonathan, they have a whole day to do this procedure in their part of the forest before the big meeting. They look at ALL other gnomes to see if they see a total of Blue hats which is odd or even. Stephen, I didn't see it specified which gnomes should stand where. But if it is, I do think that it is obvious that you are Red if you see that the other group is Blue and vice versa. So was there a rule against using the time before the meeting to solve the problem? /Tomas 


They do work out a strategy before hand. All the head gnome has stipulated that the gnomes divide into two groups dependant on colour. The solution you describe appears to assume that all the blues come in first and then all the reds. As for counting the number of hats for odd and even, that won't work. First gnome arrives (assume blue). Stands somewhere. Second gnome arrives (assume blue). Sees odd number, stands to right. Gnome three (red)  sees even number of blues, stands to left. Gnome four (blue)  sees even number of blues, stands to left of blues Gnome five (red)  sees odd number of blues, stands to right Which means that (depending on which side of the red hat gnome 4 stands), the grouping will be: red, blue, blue, blue, red; or blue, red, blue, blue, red Either way, the reds have already been separated 


Before we go any further, I should say that I know of only one solution to this problem that meets the rules stipulated above. There may be others (after all, there usually is more than one way to skin a cat...) I will say this about the solution I know  It will work for any number of people, and does not rely on prior knowledge of the number of blues or reds, nor has anything to do with odd or even numbers. I am open to reading your alternative solutions (provided they don't break the rules!) 


Stephen, the solution with counting Odd or Even the day before doesn't require them to go in with all Blues first. It just requires that they remember their own color the next day. The time solution I wrote is sure fire but it is commonly used as the solution to a similar but stricter problem. I do not see how any strategy can be agreed upon that will make them go directly to the correct place the following day. Assume the second gnome to enter sees a Red gnome standing to the right  how can he possibly decide if he himself should go right or left. If they can only base their choice on the gnomes they see have already arrived it is unsolvable. They have to make some calculations and observations beforehand OR be allowed to move around during the meeting. Are these the restrictions? 1. They just decide on a strategy but make no observations or counts before the meeting. 2. They can only observe the gnomes that arrived before them to the meeting and make their decisions from that. 3. Once in position you are not allowed to move around. Could you specify the restrictions again if I missunderstood something. /Tomas 


Would this be acceptable? The first gnome who arrives at the clearing stands in the middle. He's the first person in line. As other gnomes arrive in the clearing, they get in line according to the following rules. If the line consists entirely of redhats, get in the back of the line. If the line consists entirely of bluehats, get in the front of the line. Otherwise, get in the middle of the line, stepping in between the adjacent pair of different colored hats. Once hats of different colors are in line, no more gnomes will join the line at the very front or at the very back, so the extreme ends of the lines can "huddleup" a bit and not worry about keeping a strict "line." 


[quote] On 20050805 17:08, TomasB wrote: Are these the restrictions? 1. They just decide on a strategy but make no observations or counts before the meeting. 2. They can only observe the gnomes that arrived before them to the meeting and make their decisions from that. 3. Once in position you are not allowed to move around. [/quote] Stephen, I didn't think Tomas's #3 was called for in this problem. Did you intend it to be one of the restrictions? 


Stan, I like your sorting procedure to get a line divided in color. When I reread the problem I see that it is actually a solution since it doesn't say that there need to be a separation between the groups. So you can do your procedure left and right instead of front and back and they will be sorted as they arrive. You da man, as usual. ;) /Tomas 


"Da Man" has it! There is nothing to restrict anybody from moving about, so Stan's solution is valid. The only thing is (and it is a minor niggle) how "side" is defined. Stan's solution splits them front and back, and the head gnome wanted them each side. However, I don't think the Head Gnome will be too fussed about that minor detail ;) Anyway, that was the solution I was after  are there any other methods of sorting you good people can come up with? 


*coughs* Since they are allowed to move around I think both the Odd/Even count and the time consuming version works. They can then start the sorting and observations once at the meeting. Both procedures are definitely overkill for this problem though. /Tomas 