Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!utgpu!water!watmath!clyde!rutgers!ucla-cs!zen!ucbvax!LINC.CIS.UPENN.EDU!tim
From: tim@LINC.CIS.UPENN.EDU.UUCP
Newsgroups: comp.ai.digest
Subject: Mr. S and Mr. P
Message-ID: <8708241737.AA01288@linc.cis.upenn.edu>
Date: Mon, 24-Aug-87 13:37:25 EDT
Article-I.D.: linc.8708241737.AA01288
Posted: Mon Aug 24 13:37:25 1987
Date-Received: Sat, 29-Aug-87 16:35:25 EDT
Sender: usenet@ucbvax.BERKELEY.EDU
Distribution: world
Organization: The ARPA Internet
Lines: 34
Approved: ailist@stripe.sri.com


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