The origin of the blue eyes puzzle

The Blue Eyes puzzle is possibly the most popular induction-based puzzle known. Is it really known who was the first to come up with it (in any form).

I didn't come up with the idea of this puzzle, but I've written and rewritten it over the the years to try to make a definitive version. The guy who told it to me originally was some dude on the street in Boston named Joel.

However, it doesn't claim that this stranger was the first to create the puzzle.

So can we safely conclude that the original author is not known? And is there any reward for satisfactorily proving that you are the original author of the puzzle?

-
It's the standard example for introducing people to dynamic epistemic logic and I've seen it in a couple of forms. Since it's relatively simple, I guess many people (especially logicians) have made thoughts in that direction and finding the original author might be as hard as finding the inventor of the wheel... – Cedric Reichenbach Mar 3 at 9:48

For the muddy children variant of this problem, there are several earlier sources. For instance, A.A. Bennett (Problem No. 3734, American Mathematical Monthly 42, 1935, page 256) formulated the following version back in 1935:

A car with $n>2$ passengers of different speeds of mental reaction passes through a tunnel, and each passenger acquires unconsciously a smudge of soot upon his forehead. Suppose that each passenger

1. laughs and continues to laugh as soon as and only so long as he sees a smudge upon the forehead of a fellow passenger;
2. can see the foreheads of all his fellows;
3. reasons correctly;
4. will clean his own forehead when and only when his reasoning forces him to conclude that he has a smudge;
5. knows that (1), (2), (3) and (4) hold for each of his fellows.

Show that each passenger will eventually wipe his own forehead. (For the case of $n=3$, this has been proposed in conversation by Dr. Church of Princeton.)

-
Interesting that it specifies different speeds of mental reaction--in the "blue eyes" puzzle and in the wives puzzle, night is a focal point for action, which everyone uses as part of their reasoning. – Milo Price Mar 2 at 17:09
The "different mental speed" would be a problem. If two out of three are dirty, then everyone laughs, and the two dirty ones who see only one person with soot will eventually figure it out and clean themselves. But if all three are dirty and see two dirty faces, they can never know that the other two aren't just very slow figuring it out. – gnasher729 Mar 3 at 7:12
I think there is an important difference between this puzzle and the blue eyes puzzle: in the blue eyes puzzle nothing would happen if the guru didn't say anything, and in this version there's no need for an external source of common knowledge. – JiK Mar 3 at 11:26

The earliest occurrence of the puzzle that I am aware of is from 1958.

George Gamow and Marvin Stern: "Puzzle Math", Viking Press (February 7, 1958)

Here is the Amazon page for this book:
http://www.amazon.com/Puzzle-math-George-Gamow/dp/0670583359

Chapter 1 of the book contains several mathematical puzzle stories on the great Sultan Ibn-al-Kuz of Quasiababia. The third of these stories is called "FORTY UNFAITHFUL WIVES". and deals with the blue eyes puzzle.

Gamow and Stern state in a footnote that this puzzle was communicated to them by Dr. Victor Ambarzuminian.

-
Are you that Gamow? – Lawrence Mar 2 at 16:30
@Lawrence: That would be creepy. George Gamow died in 1968: en.wikipedia.org/wiki/George_Gamow – Gamow Mar 2 at 16:32
Oops, apologies for lack of research! – Lawrence Mar 2 at 16:35
Why two answers? Is it to double the rep earned? – ghosts_in_the_code Mar 2 at 16:36

A version of this puzzle, involving three ladies with dirty faces laughing at one another, appears in J. E. Littlewood's "A Mathematician's Miscellany," published in 1953. Littlewood writes that this is "a well-known puzzle that swept Europe a good many years ago and in one form or another has appeared in a number of books." The puzzle involves just three ladies, but on the next page Littlewood says "But further, what has not got into the books so far as I know, there is an extension, in principle, to $n$ ladies, all dirty and laughing."

-

And here is the puzzle version formulated in the book by George Gamow and Marvin Stern:

The great Sultan Ibn-al-Kuz was very much worried about the large number of unfaithful wives among the population of his capital city. There were forty women who were openly deceiving their husbands, but, as often happens although all these cases were a matter of common knowledge, the husbands in question were ignorant of their wives’ behavior. In order to punish the wretched women, the sultan issued a proclamation which permitted the husbands of unfaithful wives to kill them, provided, however, that they were quite sure of the infidelity. The proclamation did not mention either the number or the names of the wives known to be unfaithful; it merely stated that such cases were known in the city and suggested that the husbands do something about it. However, to the great surprise of the entire legislative body and the city police, no wife killings were reported on the day of the proclamation, or on the days that followed. In fact, an entire month passed without any result, and it seemed the deceived husbands just did not care to save their honor.

“O Great Sultan,” said the vizier to Ibn-al-Kuz, “shouldn’t we announce the names of the forty unfaithful wives, if the husbands are too lazy to pursue the cases themselves?”

“No,” said the sultan. “Let us wait. My people may be lazy, but they are certainly very intelligent and wise. I am sure action will be taken very soon.”

And, indeed, on the fortieth day after the proclamation, action suddenly broke out. That single night forty women were killed, and a quick check revealed that they were the forty who were known to have been deceiving their hus-bands.

“I do not understand it,” exclaimed the vizier. “Why did these forty wronged husbands wait such a long time to take action, and why did they all finally take it on the same day?”

“Very simple, my dear Watson.” The sultan chuckled. “As a matter of fact I expected this good news exactly on that day. My people, as I suggested before, may be too lazy to organize the shadowing of their wives for the purpose of establishing their faithfulness or unfaithfulness, but they have certainly shown themselves intelligent enough to resolve the case by purely logical analysis.”

“I do not understand you, Great Sultan,” said the vizier.

“Well, assume that there were not forty unfaithful wives, but only one. In this case, everybody with the exception of her husband knew the fact. Her husband, however, believing in the faithfulness of his wife, and knowing no other case of unfaithfulness (about which he would undoubtedly have heard) was under the impression that all wives in the city, including his own, were faithful. If he read the proclamation which stated that there are unfaithful wives in the city, he would realize it could mean only his own wife. Thus he would kill her the very first night. Do you follow me?”

“I do,” said the vizier.

“Now let us assume,” continued the sultan, “that there were two deceived husbands, let us call them Abdula and Hadjibaba. Abdula knew all the time that Hadjibaba’s wife was deceiving himt and Hadjibaba knew the same about Abdula’s wife. But each thought his own wife was faithful.

“On the day that the proclamation was published, Abdula said to himself, ‘Aha, tonight Hadjibaba will kill his wife.’ On the other hand, Hadjibaba thought the same about Abdula. However, the fact that next morning both wives were still alive proved to both Abdula and Hadjibaba that they were wrong in believing in the faithfulness of their wives. Thus during the second night two daggers would have found their target, and two women would have been dead.”

“I follow you so far” said the vizier, “but how about the case of three or more unfaithful wives?”

“Well, from now on we have what is called mathematical induction. I have just proved to you that, if there were only two unfaithful wives in the city, the husbands would have killed them on the second night, by force of purely logical deduction. Now suppose that there were three wives, Abdula’s Hadjibaba’s, and Faruk’s, who were unfaithful. Faruk knows, of course, that Abdula’s and Hadjibaba’s wives are deceiving them, and so he expects that these two characters will murder their wives on the second night. But they don’t. Why? Of course because his, Faruk’s, wife is unfaithful, tool and so in goes the dagger, or the three daggers, as a matter of fact.”

“O Great Sultan,” exclaimed the vizier, “you have certainly opened my eyes on that problem. Of course, if there were four unfaithful wives, each of the four wronged husbands would reduce the case to that of three and not kill his wife until the fourth day. And so on, and so on, up to forty wives.”

“I am glad,” said the sultan, “that you finally understand the situation. It is nice to have a vizier whose intelligence is so much inferior to that of the average citizen. But what if I tell you that the reported number of unfaithful wives was actually forty-one?”

-
Classic orientalism – question_asker Mar 2 at 15:59