The tenth asylum: Crazy committees

Chapter 3, Problem 10 from [The Lady or the Tiger]

Here is a [calculational solution] to this problem.

Chapter 3 of "The Lady or the Tiger" is about asylums that contain sane and crazy people: the sane always speak the truth, and the crazy always lie. Every one of them is either a doctor or a patient. Something is wrong with an asylum if it has either a crazy doctor or a sane patient.

Problem 10 from this chapter can be summarized as follows:

Inspector Craig encounters an asylum where several committees have been formed. It is given that

(1) all patients form a committee;
(2) all doctors form a committee;
(3) everyone has exactly one best friend and one worst enemy within the asylum;
(4a) the best friends of all persons that form a committee, also form a committee;
(4b) the worst enemies of all persons that form a committee, also form a committee;
(5) for any two committees 1 and 2, there is a person P whose best friend believes that P is in committee 1, and whose worst enemy believes that P is in committee 2.
How did Craig prove that something was wrong with this asylum?

Representation

For all the problems from this chapter, we can use the following notations. x stands for an arbitrary person in an asylum, and p.x for an arbitrary statement involving (at least) x.

  D.x == "x is a doctor"
  S.x == "x is sane"
  x[p.x] == "x believes p.x"

With these notations, we can put down the following axiom:

  (A) x[p.x] == S.x == p.x

For this specific problem we additionally write k or l for a set of people, and

  Comm.k == "the people in set k form a committee"
  Fr.x = "the best friend of x"
  En.x = "the worst enemy of x"

The last two are allowed because of (3) above.

Solution

We have to prove that something is wrong, formally: (Ex: S.x =/= D.x).

We can model the given facts as follows, for every k and l:

  (1)  Comm.{x| !D.x}
  (2)  Comm.{x| D.x}
  (4a) Comm.{x| k.(Fr.x)} <= Comm.k
  (4b) Comm.{x| l.(En.x)} <= Comm.l
  (5)  (Ex: Fr.x[k.x] /\ En.x[l.x]) <= Comm.k /\ Comm.l

It is easily seen that from (5) follow two other statements that deal with just one committee: (5a) for each committee there is a person whose best friend believes he is in it; and similarly: (5b) for each committee there is a person whose worst enemy believes he is in it. Formally:

  (5a) (Ex: Fr.x[k.x]) <= Comm.k
  (5b) (Ex: En.x[l.x]) <= Comm.l

It turns out that we only need (1), (4a), and (5a) to solve this problem. We calculate as follows:

   Comm.{x| !D.x}                                --- given (1)
=>    "(4a) with k:={x| !D.x}"
   Comm.{x| !D.(Fr.x)}
=>    "(5a) with k:={x| !D.(Fr.x)}"
   (Ex: Fr.x[!D.(Fr.x)])
==    "(A)"
   (Ex: S.(Fr.x) == !D.(Fr.x))
==    "give Fr.x a name, working towards our goal"
   (Ex,y| y = Fr.x: S.y == !D.y)
==    "move (E...)"
   (Ey| (Ex: y = Fr.x): S.y == !D.y)
=>    "weaken range of (E...)"
   (Ey: S.y == !D.y)

which is our goal.

This page is brought to you by Marnix Klooster, and is part of his home page. Feel free to e-mail me with comments on the form and content of this page.

Changes to calc/tlott-3-10.html:

Sat Oct 30 12:38:39 MEST 2004  Marnix Klooster
  * Move from CVS to darcs: do not show the CVS date anymore.

Thu Feb  7 19:43:35 MET 2002  marnix
  * Updated all files to use the m4 template

Wed Sep  5 21:20:00 MEST 2001  marnix
  * Made explicit that last changed date is in GMT

Wed Sep  5 21:08:51 MEST 2001  marnix
  * Now 'last changed' is on its own line

Wed Sep  5 10:10:47 MEST 2001  marnix
  * Added date last changed

Wed Sep  5 08:50:24 MEST 2001  marnix
  * Initial revision