At a competition, a group of 16 members is divided into 4 teams of 4 members each. The procedure of the competition is as follows:
Each team will be seated in a different room and after which every one will be given a cap either red or blue, i.e., total of 16 caps out of which 8 are red and 8 are blue and one from each room has to shout one of these words: Yes/No/OK and only once. They have to shout loud enough so that all other teams of their group can hear.
Then, one from each group(all 4 together) has to go to another room where they should tell the number of red and blue caps each of the other teams wore.
Before the competition started, all 16 of them are asked to devise a strategy together for every team to accomplish the task successfully.
They are also told that they should not take the caps off their heads and should not talk to members of other teams until the competition is over.
Can you find out the strategy they used? It is known that all the 3 words have been shouted at least once and one of the guys said,"In this case, anyone one of four of us could have told you the distribution of hats even if we came here individually"?
Assume all their voices are indistinguishable.
There are any number of strategies that these teams might have used, but we're not asked to devise a strategy that will workwe're asked to determine the strategy they picked based on the outcome they experienced.
Here is one possibility:
shout "YES" when the number of red hats on your team is zero or one
shout "NO" when the number of red hats on your team is three or four
shout "OK" when the number of red hats on your team is two
When you send your team member to the next room, send a team member with a blue hat when the number of red hats is zero or three, and send a member with a red hat when the number of red hats on your team is one, two, or four. The combination of seeing the hat color of the representative and knowing what that team shouted is enough to resolve the situation uniquely. (Remember, the hats don't come off until after the competition is over, so they're still being worn when the team representatives meet.)
HOWEVER, according to the puzzle, it must be possible to have had a situation where each possible word was shouted at least once (which requires two each shouted once and one shouted twice) AND that the results can be determined without seeing the hat color of the various representatives.
That very scenario could have occurred with this strategy had either "YES" or "NO" been shouted twice. The "OK" and "NO" results together require either 5 or 6 hats, and so require either 2 or three hats among the other two teams. If both were "YES" the maximum number of hats would be 2 so it would follow that the teams had 4, 2, 1 and 1 hats each. If one was "YES" and one was "NO", the minimum number of hats would be 3 and so that would require the teams having 3, 3, 2, and 0 hats.
So we can't tell (at least with this strategy) exactly what the configuration of hats was, but we do know that there are scenarios that are consistent with what happened in the puzzle.

Posted by Paul
on 20080703 20:22:22 