From X Sat Mar 27 17:26:54 MET 1993
Article: 2473 of rec.puzzles
Newsgroups: rec.puzzles
Path: news.uni-bielefeld.de!gmd.de!ira.uka.de!yale.edu!newsserver.jvnc.net!howland.reston.ans.net!zaphod.mps.ohio-state.edu!cs.utexas.edu!uunet!enterpoop.mit.edu!thunder.mcrcim.mcgill.edu!mouse
From: mouse@thunder.mcrcim.mcgill.edu (der Mouse)
Subject: Re: Knights, Knaves, Spies, and Spoilers :-)
Message-ID: <1993Mar26.165845.27624@thunder.mcrcim.mcgill.edu>
Organization: McGill Research Centre for Intelligent Machines
References: <1993Mar21.062356.2105@galaxy.gov.bc.ca>
Date: Fri, 26 Mar 93 16:58:45 GMT
Lines: 288
In article <1993Mar21.062356.2105@galaxy.gov.bc.ca>, bohara@galaxy.gov.bc.ca writes:
> Knights: Always tell the truth.
> Knaves: Always lie.
> Spies: Lies or tells the truth as it suits him.
> The setup for all the puzzles that follow is the same in all cases
> unless otherwise noted: three individuals (call them A, B and C) are
> brought before a judge. It is known that one is a [k]night, one is a
> knave and the other is a spy. Of course it is not known which is
> which.
It also appears to be assumed that "not known which is which" refers to
only the judge; the puzzles seem to assume that A, B, and C all know
what type each of them is. I'll assume this is true throughout.
> Puzzle 1
> A: "C is a knave"
> B: "A is a knight"
> C: "I am the spy"
The knight is neither B nor C, obviously; take it from there.
> Puzzle 2
> A: "I am not a spy"
> B: "I am a spy"
> Now C (who was in fact the spy) was asked by the judge, "Is B really
> a spy?"
> Problem: What did C answer so as not to convict himself?
Convict himself of what? We haven't been told why the judge is talking
to these people to begin with. The assumption that makes the most
sense to me is to assume that C does not want the court to know he's a
spy. Given the two statements made so far, there are three
possibilities: A=T, B=L, C=S; A=T, B=S, C=L; A=S, B=L, C=T. (T is a
truther (knight), L a liar (knave), and S a spy.) In each case, C can
answer "no".
> Puzzle 3
> A spy, whose name is Murdoch is brought to trial with a knight and a
> knave neither of whose names were Murdoch.
I have to assume that all persons involved (A, B, C, judge) know that
the spy, and only the spy, is named Murdoch.
> A: "My name is Murdoch"
> B: "That is true"
> C: "I am Murdoch"
> Problem: Which one is the spy?
Can't tell without knowing what order the statements were made in. B
must be the knight because neither A nor C can be, so the spy is the
person to whose statement B's "that" refers. In order for B's
statement to be true, it must be meaningful, so it cannot be first.
This leaves four orders: ABC, ACB, CBA, and CAB. When B's statement is
last, there are two possible referents, of which it seems to me that
the most recent is more likely.
> Puzzle 4
> Same setup as 3
> A: "My name is Murdoch"
> B: "That is true"
> C: "I am not Murdoch"
> Problem: Which one is the spy?
This is interesting. At first, it appears that order matters, but in
fact it doesn't! We can immediately tell that A is not the knight and
C is not the knave. If B is not the spy, or if spies are constrained
to statements that are either true or false, then B's statement cannot
be first. (I assume, as I did in puzzle 3 without explicitly stating
it, that there are no previous statements that could serve as the
referent of B's "that".) Then, given the six orders, and assuming when
B goes last that his statement refers to the most recent other
statement,
ABC A=L, B=S, C=T (if B=T, then A=S, so C=L but told the truth)
ACB A=L, B=S, C=T (if B=T, then C<>S so A=S, rest as case ABC)
CAB A=L, B=S, C=T (same logic as case ABC)
CBA A=L, B=S, C=T (same logic as case ACB)
If spies are allowed to make statements that are neither true nor
false, then we also have
BAC A=L, B=S, C=T (B=S, A<>T, C<>L)
BCA A=L, B=S, C=T (B=S, A<>T, C<>L)
Amusingly, in all six cases the outcome is the same.
> Puzzle 5
> A: "B is the spy"
> B: "C is the spy"
> C, pointing to one of the other two: "He really is the spy!"
> Problem: The judge convicted the spy. Which one did he convict?
We can't tell.
- If A is the knight, B is the spy and C must be a knave, and must have
pointed to A.
- If B is the knight, C is the spy and could have pointed to either A
or B (and made a false statement); A is the knave.
- If C is the knight, we can't tell who the spy is, except that it's
the person C pointed to; both A and B made false statements.
Thus, the spy cannot be pinned down as A, B, or C, nor as the person C
pointed to, nor the one C didn't point to.
> Puzzle 6
> Judge, to A: "Are you the spy?"
> A:
> Judge, to B: "Did A tell the truth?"
> B:
> A: "C is not the spy!"
> Judge: "I already knew that. And [now] I know who the spy is."
> Problem: Which one is the spy?
Make a table of all possibilities:
1 2 3 4 5 6 7 8 9 10
A T T T L L L S S S S
B S S L S S T L L T T
C L L S T T S T T L L
Q1 answer no no no yes yes yes no yes no yes
Q2 answer no yes no no yes no yes no no yes
Sorting the cases according to the answer pattern (which is all the
information the judge has), we have
a: Q1=n,Q2=n 1,3,9 Spy can be any.
b: Q1=n,Q2=y 2,7 Spy can be either A or B.
c: Q1=y,Q2=n 4,6,8 Spy can be any.
d: Q1=y,Q2=y 5,10 Spy can be either A or B.
When A says that C is not the spy, this eliminates cases 3, 4, and 5.
Case 1: judge is a knight. Since the judge already knew that C was not
the spy, the answer pattern must have been b or d. Since A's
additional statement let the judge determine who the spy was, it must
have been d, and the spy is A.
Case 2: judge is a knave. Since it was not the case that the judge
already knew that C was not the spy, then (assuming enough intelligence
on the part of the judge to make the deductions I made above), the
answer pattern must have been a or c. In both cases, A's additional
statement does not provide enough information to determine who the spy
is, so the judge's (false) statement that "[now] I know who the spy is"
does not provide us with any additional information, and we can't
determine who the spy is either.
Case 3: judge is a spy. We can't tell anything from the judge's
statements; we're even worse off than in case 2.
The puzzle does not provide enough information to determine which case
(1, 2, or 3) holds, so we can't tell who the spy is. Since we can't
tell the difference between cases 2 and 3, we can't even tell whether
the judge is a spy.
> Puzzle 7
> Judge: "I shall ask a series of questions - all answers must be yes
> or no. If, at any point I have identified the spy, I shall convict
> him, and the case will be terminated. If, at any point, I know of
> any of you that you are definitely not the spy, then I shall [acquit]
> you before proceeding further."
For this puzzle I will assume the judge is a knight (or a spy who
happens to tell the truth); the puzzle depends too heavily on this
speech from the bench for me to do otherwise. I will also assume that
A, B, and C all answer either yes or no, as directed by the judge.
> Judge, to A: "Are you the spy?"
> A:
> Judge, to B: "Did A tell the truth?"
> B:
> Judge, to C: "Are you the spy?"
> C:
> The judge makes a conviction and the trial stops.
> Problem: Which one is the spy?
Refer to the tables in question 6 for the state after B's answer.
Since nothing happens at this point, the judge not only doesn't know
who the spy is (which we could already tell) but doesn't know anyone
who the spy isn't. Thus, the answer pattern must have been a or c.
Eliminating the now-impossible cases, dropping the answer to question 2
(which we can now deduce was "no"), and adding the answer to question
3, we have
1 3a 3b 4 6a 6b 8 9
A T T T L L L S S
B S L L S T T L T
C L S S T S S T L
Q1 answer no no no yes yes yes yes no
Q3 answer yes no yes no no yes no yes
Grouping by answer pattern again,
a': Q1=n,Q3=n 3a A=T,B=L,C=S
b': Q1=n,Q3=y 1,3b,9 Spy can be any
c': Q1=y,Q3=n 4,6a,8 Spy can be any
d': Q1=y,Q3=y 6b A=L,B=T,C=S
Thus, the spy is C. We can't tell which is which between A and B.
> Puzzle 8
> A certain Mr. Anthony attended a spy trial where it was known at the
> outset of the three defendants, A, B, C, that one of them was a
> knight, one was a knave, and the other was a spy.
> Judge, to A: "Are you the spy?"
> A:
> Judge, to B: "Did A tell the truth?"
> B:
> The judge then pointed to one of the three defendants and said, "You
> are not the spy so you may leave the courtroom." The man gladly did
> this. The judge then asked one of the remaining defendants whether
> the other was a spy. The defendant answered yes or no and the judge
> knew who the spy was.
I will once again assume the judge is a knight (or a spy who tells the
truth throughout). This is reasonable, since the defendant who was
told he may leave was in fact allowed to do so.
Once again, refer to the tables for problem 6. Since the judge knew
someone wasn't a spy, this person must have been C, and the answer
pattern either b or d. Deleting question 2 (which was answered yes)
and adding a line for which person the judge asks and the reply,
2b 2c 2d 5a 5c 5d 7a 7b 7c 10a 10b 10d
A T T T L L L S S S S S S
B S S S S S S L L L T T T
Q1 no no no yes yes yes no no no yes yes yes
J A B B A B B A A B A A B
Q3 yes no yes no no yes no yes no no yes yes
Sorting these by Q1-J-Q3 triple,
Q1-J-Q3 cases deductions possible
no A no 7a A=S,B=L (C=T)
no A yes 2b,7b none
no B no 2c,7c none
no B yes 2d A=T,B=S (C=L)
yes A no 5a,10a none
yes A yes 10b A=S,B=T (C=L)
yes B no 5c A=L,B=S (C=T)
yes B yes 5d,10d none
Since the judge knew who the spy was at this point, the triple must
have been no/A/no (A=S), no/B/yes (B=S), yes/A/yes (A=S), or yes/B/no
(B=S).
In what follows, I assume that Mr. Anthony told his friends the truth
in all statements made (or at least those that are relevant to this
puzzle). It gets too hairy to try to work it out if Mr. Anthony is a
knave, and impossible if he's a spy.
> Mr. Anthony told this case to a friend who told Mr. Anthony, "I don't
> have enough information to solve this case. Could you at least tell
> me whether the judge got the same answer to all three questions?"
> Mr. Anthony told him. It is not known whether the friend was then
> able to solve the puzzle.
The friend would have been able to solve it iff Mr. Anthony informed
him that the judge did get the same answer to all three questions.
> Mr. Anthony told the same problem to another friend. The second
> friend wanted to know whether or not the judge got at least two no
> answers. Mr. Anthony told him. It is not known whether the second
> friend was then able to solve the puzzle.
This friend would have been able to solve it iff Mr. Anthony said that
yes, the judge did get at least two no answers.
> What is known is that either both friends solved the problem, or
> neither one solved the problem, but we are not told which.
If one of them had been able to, the other one wouldn't have, so they
were both unable to, because Mr. Anthony answered both of them no.
> Problem: Which one is the spy?
B.
Very Smullyanesqe, but I don't think I've seen it before. Where'd you
get it?
der Mouse
mouse@mcrcim.mcgill.edu