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