In a small town there are N married couples in which one of the pair has committed adultery.

Additional material

[ Editor: the solution in verse. ]

SMULLYAN'S TOWN OF ILL REPUTE
                a solution in poetry by Mike Soss

In a quiet, little town
Lay a church on hallowed ground.
Every joyous Sabbath day
The village gathered there to pray.

The townsfolk felt a little twitch
When seven years had caused that itch,
Undressing neighbors with their eyes
Despite commandment number nine.

But that's not all, and here's the twist.
Such fantasy's just a quick fix.
So when that itching did persist,
Some even broke commandment six!

The members of the congregation
Knew who else did fornication.
But every man was quite content;
He thought his own was innocent.
Yet if that person did find out,
He'd wait 'till church to have a clout
Then leave from there back to his house
So he could oust the lousy spouse!

There is one man who hates this truth --
The priest inside the little booth!
The guilty names would be suppressed;
He can't reveal what's been confessed!
Yet just beneath his very chin
Did lie a den of filth and sin.
This lesson that he had to teach
He stood to preach and made this speech,

        "To rid the town of sinful vermin
         I'm adding something to my sermon.
         In that booth I heard you mumble:
         Someone's had an extra tumble!"

The priest just simply had to wait.
The guilty would be scorned by fate
When evident became the source
Of all this extra intercourse.

The first week no one stood and said,
"My wife's been in another bed!"

Now if the adulteresses were two,
No one would know what he should do
Except for nervous Mister Y,
Who wonders if his wife did lie.
   "Oh, that poor old Mister X.
    No other wife I know had sex.
    Shouldn't he have had a strife
    To publicly denounce his wife?
    That must mean she's not unique;
    He would have said something last week!
    The other one, who could it be?
    My very wife!  It must be she!
    Oh no!  My God!  She cheats on me!
    I'll scold her next for all to see!"
(And Mister X does equally
 Sans loss of generality.)

Let's suppose they number N.
Just what would happen then and when?
The men whose wives had extra fun
Know of the other N less one.
Just as many weeks would pass
Before those wives are scorned in mass.
   "Yet why was nothing said or done
    In that week N minus one?"
Each man does ponder on and on 'till
He learns his wife's been horizontal!
They all await the Sunday next
To tell the town their wives had sex!

Thus revealed implicitly
Are those who act illicitly.
And so announced by this induction:
All unholy reproduction!

-- Mike Soss <soss@cs.mcgill.ca>

[ Editor: a mail to Chris Cole, February 1994: ]

You write, on rec.puzzles, quoting from the rec.puzzles archive,

    ==> logic/smullyan/priest.p <==
    ...,  everyone [except each adulterer's respective spouse] knows
    about everyone else's infidelity.  ...

It seems to me that the solution given in the FAQ relies not merely 
on the assumption that the condition quoted above is true, but on 
the assumption that it is "common knowledge."  That is, everybody 
knows it, everybody knows that everybody knows it, everybody knows 
that everybody knows that everybody knows it, and so on ad infinitum.  
(Well maybe something in the neighborhood of N levels, where N is 
the actual number of adulterers, would be adequate.) 

For example, suppose that the quoted condition is true, but is not 
common knowledge, and suppose there is only one adulterer.  The priest 
announces that there is at least one adulterer.  The adulterer's 
wife in fact knows about all the other adulterers (none) in the village, 
but perhaps she doesn't *know* that she knows about all the adulterers
(except possibly her husband) in the village.  Thus the wife can't
conclude with certainty that the adulterer whose existence is announced 
by the priest is in fact her husband, and so she cannot denounce 
him. 

Am I quibbling?  I think not.  For some logic puzzles, it may be fair 
to expect readers to assume implicitly that a condition given in 
the problem statement is in fact common knowledge, as defined above.  
This problem hinges entirely on the subtle difference between "common 
knowledge" and "what everyone knows." (In particular, the priest's 
announcement makes the occurrence of adultery in the village common 
knowledge, when it was not common knowledge before, even though everbody 
knew about it.)  Therefore, failure to be explicit about which facts 
are common knowledge seems like a definite flaw in the problem statement. 


-- Jim Saxe <saxe@src.dec.com>

[ Editor: a rec.puzzles reply of August 1995 to the archive entry; the
quoted problem and solution are omitted. ]

> Is the priest correct?  Will this result in every adulterer being denounced?

NO!!!

[ Editor: and, after the quoted solution: ]

Bad reasoning.  First of all, there is an additional assumption not
originially stated in the problem:  Everyone knows everyone else knows
there bussiness...  This is an even higher level of intelligence than
was originally stated that eveyone knows eachother's bussiness.  i.e.

   I know.
   I know you know.
   I know you know I know.

These are all successively higher levels of awareness...

OK, now lets go with your assumption that they do know everyone knows
everone elses bussiness.  Lets look at the N=2 case.

Man A and Man B's wifes are adulters, and noone else'ss wifes.  The
preist announce there is an adulter, and Sunday arrives.

Man A is sitting there thinking I know it is Man B's wife, and visa versa.
Man A and Man B don't initially come forward.  Man X is sitting there
waiting for A and B to come forward.

Man A is sitting there thinking why doesn't Man B come forward?  Is he
scared or such?  Likewise Man B has the same thought about Man A.  Man
X knows they are both running through the same logic, so he doesn't 
worry yet.

After awhile of sitting, it finially occures to Man A that there could be
two adulters, and his wife must be the other.  So he comes forward and
denounces his wife.

Man B sees Man A finially comming forward and thinks, awe that is it he
must have been scared...  Then it occures to him that mayber there were
two adulters.  He can't be certain if Man A was scared or if there were
two adulters, so rather than risk unjustly accusing his wife he stays
sighlent.

Man X thinks why doesn't B come forward?  He relizes it could either
be there are really 3 adulters, or Man B is uncertain of Man A's 
motivation for waiting.  Since he can't be certain he stays sighlent
rather than falsely accusing his wife.

If you follow through this line of logic, you'll find the correct answer
is:

    max(1,N-1)  If men getup one at a time, and don't want to falsely
                accuse their wife.
    >= N        Otherwise.

So, the priest is incorrect.  Most likely, there will still be adulters
on the lose, or many innocent women will be accused...  In the real
world, both.

-- Bill C. Riemers <bcr@physics.purdue.edu>