100 men are in a room, each wearing either a white or black hat. Nobody knows the color of his own hat, although everyone can see everyone else's hat. The men are not allowed to communicate with each other at all (and thus nobody will ever be able to figure out the color of his own hat).
The men need to line up against the wall such that all the men with black hats are next to each other, and all the men with white hats are next to each other. How can they do this without communicating? You can assume they came up with a shared strategy before coming into the room.
The men go to stand agains the wall one at a time. If a man goes to stand against the wall and all of the men already against the wall have the same color hat, then he just goes and stands at either end of the line. However, if a man goes to stand against the wall and there are men with both black and white hats already against the wall, he goes and stands between the two men with different colored hats. This will maintain the state that the line contains men with one colored hats on one side, and men with the other colored hats on the other side, and when the last man goes and stands against the wall, we'll still have the desired outcome.
Allan, Bertrand, and Cecil were caught stealing so the king sent them to the dungeon.
But the king decided to give them a chance.
He mad them stand in a line and put hats on their heads.
He told them that if they answer a riddle, they could go free.
Here is the riddle: "Each of you has a hat on your head. You do not know the color of the hat on your own head. If one of you can guess the color of the hat on your head, I will let you free. But before you answer you must keep standing in this line. You cannot turn around. Here are my only hints: there are only black and white hats. At least one hat is black. At least one hat is white."
Allan couldn't see any hats.
Bertrand could see Allan's hat but not his own.
Cecil could see Bertrand's hat and Allan's hat, but not his own.
After a minute nobody had solved the riddle. But then a short while later, one of them solved the riddle. Who was is and how did he know?
Bertrand knew the answer because Cecil didn't say anything after one minute. If Bertrand and Allan's hats were both the same color, then Cecil would know what color his hat was. But Cecil didn't know. So Bertrand knew that Allan's hat was a different color than his. Since Allan's hat was black, Betrand knew his hat was white.