The Truth-teller, the Liar, and AmbiguousDate: 7/9/96 at 3:47:5 From: Humphrey Clerx Subject:The Truth-teller, the Liar, and Ambiguous Hello Dr. Math, There are three people in front of you. You know that: One of them is God. He knows everything, and always tells the truth. One of them is the Devil. He also knows everything, but lies. The third person knows nothing, but answers questions as if he knows the answers. His answers, however, are completely useless and could be right or wrong. You can ask a total of three questions that can correctly be answered with yes or no, each to one of the persons. You may choose whom to ask. Determine who is who... Regards, Humphrey Date: 7/18/96 at 16:38:56 From: Doctor Sydney Subject: Re: The Truth-teller, the Liar, and Ambiguous Dear Humphrey, What a great problem! I had a fun time working on it. The solution is certainly not obvious, in my opinion - that is part of what made it so interesting. But, so that you, too, can enjoy the fun of solving the problem yourself. I'll give you a few hints, and then you can work on it. If after having worked on it more you are still stuck, write back, and I can help more. No. 1 No. 2 No. 3 a G D K b G K D c D K G d D G K e K D G f K G D 2. Given a set of questions, we can, for each different way G, D, and K are standing, determine what the answers to those questions will be. For instance, suppose we were looking at the following set of questions: i. (To individual #1) Is G standing in the middle? ii. (To individual #2) Is D to the left of G (assume, this is the left from our perspective, not theirs. Thus, above in row f, K is to the left of G and G is to the left of D and K is to the left of D)? iii. (To individual #3) Does D tell the truth? Then, if G, D, and K are standing in order (a) where G is in the #1 spot, D is in the #2 spot, and K is in the #3 spot, then we will get the following answers: i. No. (G tells the truth, and the truth is that G isn't in the middle). ii. Yes. (D always lies, and the truth is that D is NOT to the left of G). iii. No or Yes (K could answer either way - K lies and tells the truth arbitrarily). So, the point of all of this is that, given a set of questions, we can determine for each case a, b, c, d, e, and f, what the answers will be. Our goal, then, is to come up with a set of questions such that when we figure out what a, b, c, d, e, and f will say, they will all be distinguishable from one another. So, does the above set of questions work? In other words, could we have had a sequence of answers No Yes No or No Yes Yes from one b, c, d, e, or f? Well, you can look at b, c, d, e, and f, and discover that this wasn't really a good set of questions. Row b might answer the same way row a answered, and so, if we were to get the answers No Yes Yes, we wouldn't know whether we had arrangement a or arrangement b. So, we need to search for a better set of questions. How can we do that? Well, certainly one way to do that is trial and error. Think of three questions you think might give you enough information to figure out who's who. This is a method that will sometimes randomly work, but if you are like me, you probably won't be lucky enough to happen upon the solution, so perhaps a further analysis of the problem is needed. Let's make some more observations: 3. Your three questions CAN depend on previous answers. Thus, your rule for asking three questions might be something like the following: First, ask question a. If the answer to question a is yes, then ask question by. If the answer to question a is no, then ask question bn. Now do the same thing for question c - let it depend on question b's answer. So, the following scheme sums it all up: a -- yes -- by -- yes -- cyy a -- yes -- by -- no -- cyn a -- no -- bn -- yes -- cny a -- no -- bn -- no -- cnn So, the first line of the scheme indicates that if the answer to question a is yes, ask by. If the answer to question by is yes, ask question cyy. Okay, this is very important, and will most likely help you come up with a good set of three questions. Okay, my observations are over. The neat thing about logic problems like this is that there are lots of different ways to look at them. No one way is "better" than another, so while my way works, you might be able to come up with a different but also completely valid way of doing the problem. Thus, I don't want to say a whole lot more. I suggest you think about the above observations for a bit and see if anything comes to you. Just in case you need an extra boost, I'll just mention one more thing which you can look at now if you want or later, after you have thought about what I've said above. Think about your first question. Without loss of generality, we can assume you will ask your first question of the person in the No.1 position. If the answer to the first question is yes, then we will know a certain amount of information, and if it is no, we will know a certain amount of information. Step back for a minute and don't worry about what question you will ask. Try to figure out what you would like the answers to be for the 6 different orderings, a through f. Suppose that for your first question, ordering a will give you a yes, ordering b will give you a yes, and ordering c will give you a yes, and ordering d will give you a no. Because K is in position No.1, we have no idea whether or not K will answer the first question with a yes or a no, right? So, we can sum up this information by saying that if we get a yes answer, we know the group we are dealing with is in order a,b,c,e, or f. If we get a no answer, we know we are dealing with the group d,e, or f. Okay, so the point is we will, after the first question break the 6 orderings into 2 groups based on the response. Orderings e and f will always be in both groups, but depending on the question we ask, we can decide which of the two groups we want to put a,b,c, and d into. Thus, if we want to, we could probably find questions such that the answers would break the group into the following to groups: a,b,e,f for an answer of, say, yes, and c,d,e,f, for an answer of no. Okay, that was just an example. Now you need to go back and look at the different orderings and see how you would like to break the groups up. Keep in mind that if you can break them up in such a way that in place No.2 or place No.3 there can only be D's or G's that will help you because then you can ask your second question to person No.2 or No.3, respectively, and if you ask a question to which you already know the answer, you can figure out quite easily if you are dealing with G or D. Once you know where either G or D is, you can ask G or D about the ordering of the seating and since you know G always tells the truth and D always lies, you will be done! So, I know this was rather long, and somewhat vague, but I didn't want to give away the solution to the problem that I came up with, both because you may come of with your own neat solution that is different and also because it is more fun to get things for yourself. If you were confused by any of the smaller details of what I wrote above, don't worry - just think about the stuff that wasn't confusing or write back for clarification. I'd love to hear how you do with the problem, so do feel free to write back to give your own answer or ask for more help. I really had a good time working on this problem, so thanks very much for sending it in! I hope that you, too, enjoy working on it. Good luck! See also the Classic Problem "Liars and Truthtellers" in the Dr. Math FAQ: http://mathforum.org/dr.math/faq/faq.liar.html . -Doctor Sydney, The Math Forum Check out our web site! http://mathforum.org/dr.math/ Date: 05/15/2000 at 02:35:35 From: Leif Terry Subject: Your solution to The Truth-teller, the Liar, and Ambiguous Hello, I believe that your answer to the puzzle "The Truth-teller, the Liar, and Ambiguous" is incorrect in its assertion that there is, in fact, a solution. You can ask only 3 yes/no questions, and that can only distinguish among 2^3 = 8 possibilities. At first glance it appears that there are 3! = 6 possible states, one for each ordering of the truth-teller (T), liar (F), and random (R). These are: TFR, TRF, FTR, FRT, RTF, RFT However, R's answers may either be true (t) or false (f) (not necessarily with equal probability) and we don't know which. Thus there are actually 12 possible states that we have to distinguish among. These are: TFt, TFf, TtF, TfF, FTt, FTf, FtT, FfT, tTF, fTF, tFT, fFT Since we can not possibly distinguish among these 12 states with 3 yes/no queries, we can not find a line of questioning that will tell for certain who is who. I find your site very entertaining and helpful but I think you goofed on this one. Cheers, Leif Date: 05/15/2000 at 11:48:00 From: Doctor Rick Subject: Re: Your solution to The Truth-teller, the Liar, and Ambiguous Hi, Leif. If you'll ignore your proof that the problem can't be solved, and make use of Doctor Sydney's hints, you'll find a solution in short order. I found his hints to be very helpful. If you asked one question and got responses from all three individuals, the set of 3 answers would be one of the 12 possibilities you list. But you aren't asked to determine how each individual would answer a particular question. You are only asked to determine which is the truth-teller, which is the liar, and which is the random answerer. There are only 6 possible states, as Doctor Sydney enumerates. If you follow Doctor Sydney's suggestions, after the first question you will have four possibilities left. Furthermore, you will know that one of the individuals can't be a random answerer, so you can make use of all the information you get from that point on. Two questions are then just enough to distinguish among the 4 possible states. I'm glad you like our site. I hope you'll like it even more now that you know that we never goof! ;-) No, really, if you find another goof, let us know -- readers do catch real mistakes now and then, and we appreciate it. - Doctor Rick, The Math Forum http://mathforum.org/dr.math/ Date: 05/16/2000 at 02:01:30 From: Leif Terry Subject: Re: Your solution to The Truth-teller, the Liar, and Ambiguous Hello again Dr. Math, >If you'll ignore your proof that the problem can't be solved, and make >use of Doctor Sydney's hints, you'll find a solution in short order. I >found his hints to be very helpful. I'd be more willing to ignore my "proof" if someone could point out the fallacy in it. I think it is very important for students to be able to figure out what can be solved and what can't. That way we can spend our time productively working on the unsolved problems instead of wasting time on the unsolvable (as amusing as the Bridges of Koenigsberg are). I've read and re-read the hints, but I still don't see a solution. I'm entirely willing to be wrong on this one, but I must admit that I find your counter-arguments unsatisfying. >If you asked one question and got responses from all three >individuals, the set of 3 answers would be one of the 12 possibilities >you list. But you aren't asked to determine how each individual would >answer a particular question. You are only asked to determine which is >the truth-teller, which is the liar, and which is the random answerer. >There are only 6 possible states, as Doctor Sydney enumerates. I don't see what the distinction that you are trying to make is. If you find the random answerer you also know how he answered your question so you must know what state he is in. The only way to avoid this is to never ask the random answerer a question, which is impossible to guarantee. >If you follow Doctor Sydney's suggestions, after the first question >you will have four possibilities left. Yes, I can do that. Of course, I count 6 possibilities not four. >Furthermore, you will know that one of the individuals can't be a >random answerer, Yes, but one of them could be. For example, we could ask the first person: 1) Are you random? If yes, then we are in one of the following 4 (6) states: FTR, FRT, RTF, RFT If no then we are in one of these 4 (6): TFR, RTF, TRF, RFT Suppose the outcome was "yes". What shall our next question be? The best one I've found so far is: 2) Are you random? If yes then we have it narrowed down to two (2), FRT or RFT. In fact, since we know that T is the last one, we have a solution -- but only for this one case. We have *not* solved the puzzle. If the answer to (2) was "no" then it could be either one of these three (4) states: FTR, RTF or FRT. Obviously no matter how you count states we have hit a dead end here. Here is further evidence that you need to include the random state of the Ambiguous into your count of possibilities: Consider a simpler puzzle. You have two men, one of which is omniscient and always tells the truth. The other answers randomly. Determine who is who. Since there are only 2 [sic] states TR or RT, you only get *one* question to put to the man of your choice. This puzzle is not solvable as stated. The reason is obvious: R may answer either yes (y) or no (n) regardless of the question so there are really four possible states: Ty, Tn, yT, nT This puzzle *is* solvable if you are given 2 questions, as you would expect. I ask you to reconsider your posted "solution" to this problem. If you still believe me to be in error, then please point out the fallacy in my "proof" or send me your solution. Regards, Leif "Mathboy" Terry Date: 05/16/2000 at 10:39:12 From: Doctor Rick Subject: Re: Your solution to The Truth-teller, the Liar, and Ambiguous Hi, Leif. I agree that an important element of problem solving is to do whatever you can do up front to determine whether the problem has a solution, and if so, what general characteristics the solution must have. In advising you to ignore your "proof" of impossibility, I was not saying that you shouldn't use such reasoning. I was, in fact, applying the same principal to a new problem, namely, that of identifying the fallacy in your reasoning. By solving the (original) problem first, we establish up front that there must indeed be a fallacy -- we're not on a wild goose chase. Furthermore, in solving the original problem, we may stumble on something that could help you to see where the fallacy lies. And I think we will! With this in mind, let's start with my solution. >There are three people in front of you. You know that: > >One of them is God. He knows everything, and always tells the truth. >One of them is the Devil. He also knows everything, but lies. >The third person knows nothing, but answers questions as if he knows >the answers. His answers, however, are completely useless and could be >right or wrong. > >You can ask a total of three questions that can correctly be answered >with yes or no, each to one of the persons. You may choose whom to ask. > >Determine who is who... Line up the three individuals, front to back, and number them #1, #2, and #3. I'll abbreviate as you do, T for truth-teller, L for liar, and R for random answerer. (Question 1) Ask #1, "Is R immediately behind L?" If he answers yes, then either he is T and the order is TLR, or he is L and the order is LTR, or he is R and the order can be either RTL or RLT. Thus we have divided the 6 states like this: Q1 yes Q1 no ------ ----- TLR TRL LTR LRT RLT RLT RTL RTL Notice that if the answer was yes, then #2 cannot be R. So (Q2y) ask #2, "Are you R?" If the answer is yes, you know this is a lie, so #2 must be L. This leaves two possible states: TLR or RLT. To distinguish between these states, (Q3yy) ask #2, "Is #3 T?" You know he will lie, so an answer of yes means TLR, and an answer of no means RLT. If the answer to Q2y was no, then you know this is the truth, and #2 must be T, leaving two possible states: LTR or RTL. To distinguish between these states, (Q3yn) ask #2, "Is #3 L?" You know he will tell the truth, so an answer of yes means RTL, and an answer of no means LTR. If the answer to Q1 was no, then #3 cannot be R (see the table above). You can follow exactly the same procedure as above, except that you switch #2 and #3. In summary, here is a flow chart of the questions you ask: (Q1) #1, Is R immediately behind L? Yes --> (Q2y) #2, Are you R? Yes --> (Q3yy) #2, Is #3 T? Yes --> TLR No --> RLT No --> (Q3yn) #2, Is #3 L? Yes --> RTL No --> LTR No --> (Q2n) #3, Are you R? Yes --> (Q3ny) #3, Is #2 T? Yes --> TRL No --> RTL No --> (Q3nn) #3, Is #2 L? Yes --> RLT No --> LRT After three questions, we know who is who. Does this solution work for you? The key was to ask a first question that gave me enough information to allow me to ask the second question of someone who was definitely not R. As Doctor Sydney suggested, I first wrote down the two sets of states that I wanted to distinguish by means of the first question. Then I hunted for a question that would have this result. Random selection of the first question is very unlikely to have a helpful result! Here's why your simpler problem has no analogous solution: it takes at least two questions to make this method work. As long as it's possible that you're speaking to a random answerer (and this is possible on the first question), you can't distinguish R from either T or L. That first question, however, CAN give us real information about ANOTHER individual, as you see from the solution. We get this information by leveraging the information we already have, namely, that there is exactly one of each type. I admit this is counterintuitive; that's what makes the problem interesting. Now that we have something concrete on the table, I'll take another shot at explaining why your state scenario doesn't apply. You say: >However, R's answers may either be true (t) or false (f) (not >necessarily with equal probability) and we don't know which. Thus >there are actually 12 possible states that we have to distinguish >among. These are: > > TFt, TFf, TtF, TfF, FTt, FTf, FtT, FfT, tTF, fTF, tFT, fFT If we had to know how EACH individual answered a particular question (truthfully or falsely), then this list of states might be relevant. But if you examine the solution, you will see that only the first question is asked of someone who might be R, and it is asked of #1 only. Thus the only possible states that arise in the course of the solution are: TFR, TRT, FTR, FRT, tTF, fTF, tFT, fFT That's 8 states, exactly the right number to be distinguished by 3 questions. This answers your comment: >I don't see what the distinction that you are trying to make is. If >you find the random answerer you also know how he answered your >question so you must know what state he is in. The only way to avoid >this is to never ask the random answerer a question, which is >impossible to guarantee. We do indeed avoid asking the random answerer a question, if he is #2 or #3. Have we resolved the problem yet? I understand your desire to see exactly what was wrong with your argument, in order to avoid making similar mistakes in the future. In problems like this, I often doubt my initial general conclusions, because I suspect I may be missing some possibility, just as you did in this problem. I wish I could tell you what to do, but all I can say is "don't be too sure too soon!" - Doctor Rick, The Math Forum http:// mathforum.org /dr.math/ Date: 05/17/2000 at 03:30:38 From: Leif Terry Subject: Re: Your solution to The Truth-teller, the Liar, and Ambiguous Hello again Dr. Math, Thank you for patiently explaining the solution to that problem to me. I understand it now. No small part of my difficulty came from assuming that each person had to be asked a question. It certainly is a devilish problem. I doubt I could have solved it the way it was intended but perhaps I would have been less sure of its impossibility. Thank you for your help, -Leif |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/