My question is about Puzzle 11 in Chapter 3 of R. Smullyan's The Lady or the Tiger. Here is the context and problem:
"Inspector Craig of Scotland Yard was called over to France to investigate eleven insane asylums where it was suspected that something was wrong. In each of these asylums, the only inhabitants were patients and doctors – the doctors constituted the entire staff. Each inhabitant of each asylum, patient or doctor, was either sane or insane. Moreover, the sane ones were totally sane and a hunded percent accurate in all their beliefs; all true propositions they knew to be true and all false propositions they knew to be false. The insane ones were totally inaccurate in their beliefs; all true propositions they believed to be false and all false propositions they believed to be true. It is to be assumed also that all the inhabitants were always honest – whatever they said, they really believed.
The first thing Inspector Craig discovered in this asylum was that its inhabitants had formed various committees. Doctors and patients, he learned, could serve on the same committee and sane and insane persons might be on the same committee. Then Craig found out the following facts:
- All patients formed one committee.
- All doctors formed one committee.
- Each inhabitant had several friends in the asylum, and among them one who was his best friend. Also, each inhabitant had several enemies in the asylum, and among them one called his worst enemy.
- Given any committee, C, all inhabitants whose best friend was on C formed a committee, and all inhabitants whose worst enemy was on C also formed a committee.
- Given any two committees – Committee 1 and Committee 2 – there was at least one inhabitant, D, whose best friend believed that D was on Committee 1 and whose worst enemy believed that D was on Committee 2.
Craig was curious to know whether all sane inhabitants formed a committee and all insane inhabitants formed a committee. He could not settle these questions on the basis of facts 1, 2, 3, 4, and 5, but he was able to prove – and just on the basis of 3, 4, and 5 – that it was not possible for both of these groups to have formed committees. How did he prove this?"
The proof is given at the end of the chapter and makes sense, but somehow I've convinced myself that there can be no committee of insane inhabitants. The problem seems to suggest that that's not provable (at least not by Craig, who seems smarter than me), so I think there's an issue with my proof, but I can't find it:
Let $C_i$ be a committee of insane inhabitants. Then by fact 4 there exists a committee $C_i^{bf}$ of inhabitants whose best friends are insane and a committee $C_i^{we}$ of inhabitants whose worst enemies are insane. So by fact 5 there exists an inhabitant $x$ whose best friend $bf_x$ believes $x$ is in $C_i^{bf}$ and whose worst enemy $we_x$ believes $x$ is in $C_i^{we}$. That is, $bf_x$ believes $bf_x$ is insane and $we_x$ believes $we_x$ is insane. This is impossible, since an insane person cannot hold the true belief that they are insane and a sane person cannot hold the false belief that they are insane. So there can be no such committee $C_i$.
Update: I suppose it's possible for $C_i^{bf}$ and $C_i^{we}$ to be empty – that would just mean that everyone's best friend and worst enemy are both sane, which doesn't contradict any of the given facts I think. I don't know what that would mean though. Does my proof still hold if $C_i^{bf}$ and $C_i^{we}$ are empty? I think so, because it holds when $bf_x$ and $we_x$ are sane.
Best Answer
I don't think that the empty-committee case is a hole in the argument. The setup is slightly ambiguous, but there are two cases:
There is one other way to interpret the conditions to prevent this argument from working, but it prevents the argument in the solutions from working, too. Does condition 5 imply the following statement, obtained by setting committee 1 and committee 2 to be the same committee?
If it does, then the argument is just fine. If it does not, then we have to consider the case that $C_i^{bf} = C_i^{we}$: everyone either has an insane best friend and an insane worst enemy, or a sane best friend and a sane worst enemy. Note that in this case, everyone's best friend and worst enemy have identical beliefs!
Such a scenario is incompatible with conditions 1 and 2: if there is a committee of patients and a committee of doctors, then there should be a person $x$ whose best friend thinks $x$ is a patient, but whose worst enemy holds the contradictory belief that $x$ is a doctor.
However, reasoning only from conditions 3, 4, and the weak form of 5 (which requires its committees to be distinct), it is impossible to rule out the scenario where there is only one committee: the committee $C_i$ of insane inhabitants of the asylum. For this to happen, we must have $C_i^{bf} = C_i^{we} = C_i$, so for simplicity let's just say that everyone is simultaneously their own best friend and their own worst enemy. Now conditions 3 and 4 are satisfied, and the weak form of condition 5 has no two distinct committees to apply to.
I do not seriously advance the "weak form of condition 5" as a possibility, because the official solutions also do not check that two committees are distinct before applying it.
However, it's worth noting that even if we only allow condition 5 in the weak form, then it's still possible to solve problem 10. If we assume that committee $C_i$ exists, then in all cases except the case that $C_i^{bf} = C_i^{we}$, we already arrive at a contradiction. But if $C_i$ exists and $C_i^{bf} = C_i^{we}$, there cannot also be a committee $C_s$ of sane people.
If $C_i$ and $C_s$ both exist, there is an inhabitant $x$ whose best friend thinks $x$ is on $C_i$ and whose worst enemy thinks $x$ is on $C_s$. These are contradictory beliefs - but as we saw earlier, $C_i^{bf} = C_i^{we}$ means that $x$'s best friend and worst enemy must have identical beliefs!