tim@LINC.CIS.UPENN.EDU.UUCP (08/24/87)
I don't know the full history of the Mr. S and Mr. P puzzle, but I'm sure it goes back a long way. I first saw it when Will Dowling of Drexel University sent it to me with the suggestion that it might be easy to express the solution in Prolog. I posted it to Prolog-digest in November or October of 1984. There were several follow up posting, some of which discussed its history. You could explore the prolog digest archives at SUMEX-AIM for more information. Here is the puzzle as it was told to me: There are 2 integers n and m between 3 and 98 inclusive. Mr. S has been told their sum and Mr. P their product. The following truthful conversation occurs: P: I don't know n and m. S: I knew you didn't. Neither do I. P: Now I know them! S: Now I do, too!! What are the values of n and m? By the way, the answer to this version of the puzzle is NOT 4 and 13! I won't spoil anyone's fun by saying what the answer is, or by describing how one determines what it is or is not. This is a simple example of a general problem which requires one to model and reason about the beliefs and knowledge of other agents, a topic that has been receiving some attention lately. Halperin (IBM) and Moses (Stanford) have been using a similar puzzle (variously called "the cheating wives" and "the dirty children") in their recent work. Tim