So, there are two drunkards. After a night of inebriated jollity, they find themselves on a busy street, each tied to a lamppost, naked, both with their hair dyed shocking pink.
“Robert! What the HELL happened last night?” shrieks Daniel, suddenly conscious and aware that he's not in a particularly tenable position, particularly as the sun looks to be rising.
“Well, we seem to be naked, and your hair is... well, we're naked.” replies a bleary Robert.
Neither party decides to mention that their friend's hair is pink, as they both have enough to worry about as it is. As such, Robert and Daniel both go completely unaware of their own new hair colours until Chief Inspector Jaffa arrives on the scene.
“'ello, you 'orrible miscreants!”. Jaffa never really had much of a grasp on the real world. He figured stereotypes were there to be fulfilled.
“I 'ope you know that being naked in public is a punishable offence!”
“We know Officer, we're sorry. It's just that we're a bit tied up!”
“I can see that! Let it not be said that I'm an unfair man. I'll give you 'orrid sods a sporting chance. At least one of you has had his hair dyed pink, presumably during your night of sickening debauchery. When I blow my whistle, I want each one of you to say whether you think you have pink hair.”
Inspector Jaffa blows his whistle, and both drunkards raise their hands.
“Bugger”, exclaims Jaffa, who was quietly confident that the odds were on his side. He arrests them anyway, for outsmarting a policeman and some other offences he made up on the way to the station.
In a parallel dimension the same thing happened, only this time only Robert's hair was pink, and only Robert raised his hand. Likewise, in a further alternative universe, Daniel was the sole pink-haired chap, and again they both managed to figure out their own hair colour. How could this be?
This is my own (slightly hard to believe) example of a common knowledge problem. You may have encountered this before, perhaps in a different form with more subjects – three men with different coloured hats, or monks with blobs of paint on their heads being common variations. The logic (in the original case where they both have pink hair) involved goes like this:
Robert could see that Daniel had pink hair, and vice versa. Before the policeman arrived, there was not enough information for either of the men to realise that their own hair was pink.
“At least one of you has pink hair”.
This has given both Daniel and Robert some new information – both originally knew that at least one of them had pink hair, but they didn't know that they both knew this. At this point, Daniel is able to think to himself “I can see that Robert has pink hair. Since he hasn't shown any signs of embarrassment, he must have looked at me and have seen that I have pink hair, which in his mind rules out that definitely has pink hair. So I must have pink hair! Curses.”. Robert goes through the same logical process, and they both raise their hands.
This works for all configurations. If only Robert had pink hair, the logic would be:
Robert: “Daniel hasn't got pink hair. I must have, then! Curses”. Robert blushes.
Daniel: “Robert is visibly embarrassed. Poor bugger must have looked at me, seeing that I don't have pink hair, and come to the correct conclusion that he does.”
(This obviously works out for the other configuration, with Daniel and Robert trading places)
Now the general concept is (hopefully) explained, let's take it a step further. There are 50 prisoners, each with a red paint mark on their backs. The warden is feeling especially mean, and offers to set them free if they can pass his test (like Chief Inspector Jaffa, believing that the odds are on his side). The test is such:
Each time the warden rings his bell, the prisoners must raise their hands if they suspect that they have a red blob on their own backs. The test is passed when all blobbed prisoners have successfully deduced their blobular status, however if any false positives are made then it is counted as automatic failure and it's back to porridge for the inmates. It doesn't matter how many bell rings it takes – as long as nobody raises their hand when they don't have a blob. The warden makes it clear that at least one inmate has a blob – now common knowledge.
Oh, I should probably mention that this is a high security prison for expert logicians, who have all committed the crime of being too damned clever by half.
The bell rings, and nobody raises their hand. On the 50th ring all hands are raised, and logic has freed them all.
The common knowledge is the key here – in any circumstance, n inmates will be able to deduce their blob status after n rings of the bell, from what they know that the other inmates know. This is essentially a process of mathematical induction in a word problem form.
This node is inspired by the first chapter from Ian Stewart's excellent book “Math Hysteria”, where a cheeky monk has been putting blobs on other monk's heads.