On Mon, 2004-10-11 at 22:51, Bruno Marchal wrote: > As a Price, I give you the (known?) Smullyan McCarthy
As a Price, or a Prize? :) > puzzle. You are in front of three Gods: the God of Knights, the > God of Knaves, and the God of Knives. The God of Knight always > tells the truth. The God of Knaves always lies, and the God of Knives > always answers by "yes" or "no" randomly. > You must find which is which, through some questions. > You can ask no more than three yes-no (answerable) questions. > (Each question must be asked to one God, but you can ask > more than one question to a God; only then there will be a > God you can no more ask a question). > And (added McCarthy) I let you know that all the Gods, although > they understand English, will answer the yes-know question by > either "JA" or "DA", and you are not supposed to know which > means "yes" and which means "no". Wow, that was a hard one! I have been thinking about it all day, but I think I got to the solution. Let's see... I developed a whole method for solving this kind of problem. :) Labelling the Knights' God as T, the Knaves' God as F, and the Knives' God as R, we have 6 possible 'states' we want to distinguish, which are all the permutations of them. I'll make 3 questions, which can have two possible outcomes each, "JA"(J) or "DA"(D). This means that in the end my "experiment" has 8 possible outcomes. >From this initial analysis it is clear that I cannot aim to ask questions which would give me information about the statements "JA=YES" or "JA=NO", because for that I would need to distinguish between 12 states. But since I have 2 outcomes more than states, it is possible that I might in some cases get this last answer, but only as a bonus. So I make a table where I try to fit a set of 3 questions whose outcomes are going to distinguish these states. One possible table is the following: State 1st J D JJ JD DJ DD Final ----------------------------------------------- TRF J J J JJJ TFR D J J DJJ FRT J D J JDJ FTR D D J DDJ RTF J/D J D D D JJD/DDD RFT J/D D J D D JDD/DJD ----------------------------------------------- The blank spaces mean that we don't care what would be the answer in those cases, because they have been already ruled out. It's important to leave blank spaces in at least two lines which correspond to 'R's in the same column, because we can always make the question to the the God in that column so that we can arrange the random answers to fall in those places. The columns 'J', 'JJ' and so on indicate the outcomes that I wish the next question to have given outcome 'J', 'JJ' and so on for the previous questions. Some more thought shows that you can always come up with *some* question that fits whatever choice of outcomes you want, given the constraints above. So we have a lot of freedom to choose the outcomes in the above table, the only problem will be to think of the corresponding verbal questions. So the first problem is to come up with some question which would be answered as in the '1st' column. This question could be, using the idea of Jesse Mazer, but with an extra trick: "If I asked you "Is the 2nd God the 'R'", would you say 'JA'?" The interesting thing is that this question does not tell us if JA is YES or NO, but a minute of thought shows that the outcomes are the same whatever JA means. After some thought, the other questions can be: Column'J': "3rd god, if I asked you 'Are you the 'F'', would you say 'JA'?"; Column'D': "2nd god, if I asked you 'Are you the 'F'', would you say 'JA'?"; Columns 'JJ' and 'JD': "3rd god, if I asked you 'Is the 2nd god 'R'', would you say 'JA'?"; Columns 'DJ' and 'DD': "2nd god, if I asked you 'Is the 3rd god 'R'', would you say 'JA'?". So I think these would solve the problem. It was a lot of fun! Let me see what you guys think. As an extra challenge, can you think of a way to find out if JA=YES in some of the outcomes? It would involve different questions, but I think it should be possible in principle. Eric.
