Re: S, B, and a puzzle by Boolos, Smullyan, McCarthy
At 00:57 13/10/04 -0400, Jesse Mazer wrote: Nice work, Eric! Absolutely. I don't really need to add a thing, although when I got the time I will compare Eric's solution with Boolos' one (but I think they are quite the same). It looks Eric solved what Boolos called "The Hardest Logical Puzzle Ever" ;-) Bruno Your solution looks right to me. I now realize my mistake, I was thinking that if the gods are in a particular order (say, TRF) and Ja has a particular meaning (say, Ja=yes) and you get a particular series of answers (say, JJJ) then if you reverse the meaning of Ja and ask the same questions, that means you'll also get the reverse answers (in this case DDD). But if the question is of the form "If I asked X, would you say 'Ja'?" this isn't actually the case. The key seems to be that if you ask a question of the form "If I asked X, would you say 'Ja'?" then if X is true, both the knight and the knave will answer "Ja" regardless of whether Ja means "yes" or "no", and if X is false then both the knight and the knave will answer "Da" regardless of the meaning of Ja. So with that trick in mind, the solution to this problem will be exactly like the solution to the problem where the gods actually say "yes" and "no"...for example, I could take my previous solution to that problem: your first question should be to ask the first God "If I asked you 'is the second God the God of Knives', would you say 'yes'?" If the first God answers "yes", you know the God of Knives is either the first or the second God, so you can ask the third God, "If I asked you 'are you the God of Knights', would you say 'yes'?" and after that you can ask the third God "If I asked you 'is the first God the God of Knives', would you say 'yes'?" and this will be enough to tell you the identity of all three Gods. On the other hand, if the answer to your first question was "no", then you know the God of Knives is either the first or the third God, so you would ask the *second* God the same two subsequent questions as above. ...and simply replace every "yes" with "Ja" and every "no" with "Da": your first question should be to ask the first God "If I asked you 'is the second God the God of Knives', would you say 'Ja'?" If the first God answers "Ja", you know the God of Knives is either the first or the second God, so you can ask the third God, "If I asked you 'are you the God of Knights', would you say 'Ja'?" and after that you can ask the third God "If I asked you 'is the first God the God of Knives', would you say 'Ja'?" and this will be enough to tell you the identity of all three Gods. On the other hand, if the answer to your first question was "Da", then you know the God of Knives is either the first or the third God, so you would ask the *second* God the same two subsequent questions as above. ...keeping in mind, again, that if you ask a god "If I asked you X, would you say 'Ja'?", then if he says "Ja" that means X must be true if the god was a knight or a knave, and if he says "Da" X must be false if the god was a knight or a knave. Jesse http://iridia.ulb.ac.be/~marchal/
Re: S, B, and a puzzle by Boolos, Smullyan, McCarthy
On Wed, 2004-10-13 at 12:15, Eric Cavalcanti wrote: > 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. I thought about that problem more, and I am convinced that in fact we can't. The reason is that the first question can be answered by the random god, and in this case we don't gain any information out of that. So we only have really 6 'good' outcomes. On another view, we can say that the extra outcomes in the 'states' 5 and 6 represent the extra bit of information about what the random god actually answered. Eric.
Re: S, B, and a puzzle by Boolos, Smullyan, McCarthy
Nice work, Eric! Your solution looks right to me. I now realize my mistake, I was thinking that if the gods are in a particular order (say, TRF) and Ja has a particular meaning (say, Ja=yes) and you get a particular series of answers (say, JJJ) then if you reverse the meaning of Ja and ask the same questions, that means you'll also get the reverse answers (in this case DDD). But if the question is of the form "If I asked X, would you say 'Ja'?" this isn't actually the case. The key seems to be that if you ask a question of the form "If I asked X, would you say 'Ja'?" then if X is true, both the knight and the knave will answer "Ja" regardless of whether Ja means "yes" or "no", and if X is false then both the knight and the knave will answer "Da" regardless of the meaning of Ja. So with that trick in mind, the solution to this problem will be exactly like the solution to the problem where the gods actually say "yes" and "no"...for example, I could take my previous solution to that problem: your first question should be to ask the first God "If I asked you 'is the second God the God of Knives', would you say 'yes'?" If the first God answers "yes", you know the God of Knives is either the first or the second God, so you can ask the third God, "If I asked you 'are you the God of Knights', would you say 'yes'?" and after that you can ask the third God "If I asked you 'is the first God the God of Knives', would you say 'yes'?" and this will be enough to tell you the identity of all three Gods. On the other hand, if the answer to your first question was "no", then you know the God of Knives is either the first or the third God, so you would ask the *second* God the same two subsequent questions as above. ...and simply replace every "yes" with "Ja" and every "no" with "Da": your first question should be to ask the first God "If I asked you 'is the second God the God of Knives', would you say 'Ja'?" If the first God answers "Ja", you know the God of Knives is either the first or the second God, so you can ask the third God, "If I asked you 'are you the God of Knights', would you say 'Ja'?" and after that you can ask the third God "If I asked you 'is the first God the God of Knives', would you say 'Ja'?" and this will be enough to tell you the identity of all three Gods. On the other hand, if the answer to your first question was "Da", then you know the God of Knives is either the first or the third God, so you would ask the *second* God the same two subsequent questions as above. ...keeping in mind, again, that if you ask a god "If I asked you X, would you say 'Ja'?", then if he says "Ja" that means X must be true if the god was a knight or a knave, and if he says "Da" X must be false if the god was a knight or a knave. Jesse
Re: S, B, and a puzzle by Boolos, Smullyan, McCarthy
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 DJJ JD DJ DD Final --- TRF J J J JJJ TFR D JJ DJJ FRT J D J JDJ FTR D DJ DDJ RTF J/D J DD D JJD/DDD RFT J/D D JD 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.
Re: S, B, and a puzzle by Boolos, Smullyan, McCarthy
Bruno Marchal wrote: You made a relevant decomposition of the problem, and you are on the right track. Actually I'm not sure the "ja" "da" McCarthy's amelioration adds anything deep to the problem. It will be enough to take into account that a double negation gives an affirmation. I've thought about McCarthy's version for a while and I can't figure it out, even if I make the simplifying assumption of two truth-tellers and one random-answerer. It seems like the 3 bits of information you get from their answers just shouldn't be enough to tell the meaning of Ja vs. Da *and* tell you the identity of all three gods. 3 bits of information should only allow you to choose from 8 possibilities, but there seem to 12 possibilities here: (Ja=yes, god #1=knight, god#2=knave) (Ja=yes, god#1=knight, god#2=knife) (Ja=yes, god#1=knave, god#2=knight) (Ja=yes, god#1=knave, god#2=knife) (Ja=yes, god#1=knife, god#2=knight) (Ja=yes, god#1=knife, god#2=knave) (Da=yes, god #1=knight, god#2=knave) (Da=yes, god#1=knight, god#2=knife) (Da=yes, god#1=knave, god#2=knight) (Da=yes, god#1=knave, god#2=knife) (Da=yes, god#1=knife, god#2=knight) (Da=yes, god#1=knife, god#2=knave) Then I thought there might be a clever solution where you can figure out the identity of the gods without ever knowing the meaning of "Ja" and "Da". But if you don't figure out the meaning of "Ja" and "Da", it seems to me you're really only getting 2 bits of information from their answers, since it doesn't actually matter what the first answer is, only whether the second and third answer are the same as or different from the first--you can't distinguish between the answers Ja-Da-Ja and Da-Ja-Da, for example. 2 bits should only be enough to choose from 4 possibilities, but there are 6 possibilities you need to choose from to find the identity of all three gods: (god #1=knight, god#2=knave) (god#1=knight, god#2=knife) (god#1=knave, god#2=knight) (god#1=knave, god#2=knife) (god#1=knife, god#2=knight) (god#1=knife, god#2=knave) So either way I'm stumped...can you give me the solution? If you want to let other people keep trying to figure it out you can just email it to me. Jesse
Re: S, B, and a puzzle by Boolos, Smullyan, McCarthy
You made a relevant decomposition of the problem, and you are on the right track. Actually I'm not sure the "ja" "da" McCarthy's amelioration adds anything deep to the problem. It will be enough to take into account that a double negation gives an affirmation. Bruno At 16:55 11/10/04 -0400, Jesse Mazer wrote: Bruno Marchal wrote: As a Price, I give you the (known?) Smullyan McCarthy 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). Playing around with this for a while, I realized you can always trick the knave into giving the same answer as the knight to any question "X" by asking the more complicated question, "If I were to ask you question X, would you answer 'yes'?" The knight will always give the same answer to this question as he would to the question X itself, while the knave will always give the opposite answer that he would if you had actually asked him X, which means he will always answer the same as the knight! With this trick, the problem reduces to a simpler one where you have three guys with different names--say, Huey, Dewey, and Louie--and you know Huey and Dewey always tell the truth while Louie always answers randomly, and you have to figure out each guy's name with only three questions. In this case, you could ask the first guy, "is the second guy Louie?" Then if he answers "yes", you know the third guy must be either Huey or Dewey, so you ask the third guy "are you Huey?" and then ask "is the first guy Louie?" and you're set. On the other hand, if the first guy answered "no" to your first question, then you know the second guy is either Huey or Dewey, so you can ask the second guy the same two questions. Translating this back into the 3 Gods, problem, your first question should be to ask the first God "If I asked you 'is the second God the God of Knives', would you say 'yes'?" If the first God answers "yes", you know the God of Knives is either the first or the second God, so you can ask the third God, "If I asked you 'are you the God of Knights', would you say 'yes'?" and after that you can ask the third God "If I asked you 'is the first God the God of Knives', would you say 'yes'?" and this will be enough to tell you the identity of all three Gods. On the other hand, if the answer to your first question was "no", then you know the God of Knives is either the first or the third God, so you would ask the *second* God the same two subsequent questions as above. 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". Ugh, I'll have to think about that some more...but again, this is equivalent to a problem where you have three guys named Huey, Dewey and Louie, and Huey and Dewey always tell the truth while Louie answers randomly, but they all answer with "JA" or "DA" and you don't know which word means yes and which means no. If anyone else can figure it out feel free to jump in. Jesse http://iridia.ulb.ac.be/~marchal/
Re: S, B, and a puzzle by Boolos, Smullyan, McCarthy
Bruno Marchal wrote: As a Price, I give you the (known?) Smullyan McCarthy 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). Playing around with this for a while, I realized you can always trick the knave into giving the same answer as the knight to any question "X" by asking the more complicated question, "If I were to ask you question X, would you answer 'yes'?" The knight will always give the same answer to this question as he would to the question X itself, while the knave will always give the opposite answer that he would if you had actually asked him X, which means he will always answer the same as the knight! With this trick, the problem reduces to a simpler one where you have three guys with different names--say, Huey, Dewey, and Louie--and you know Huey and Dewey always tell the truth while Louie always answers randomly, and you have to figure out each guy's name with only three questions. In this case, you could ask the first guy, "is the second guy Louie?" Then if he answers "yes", you know the third guy must be either Huey or Dewey, so you ask the third guy "are you Huey?" and then ask "is the first guy Louie?" and you're set. On the other hand, if the first guy answered "no" to your first question, then you know the second guy is either Huey or Dewey, so you can ask the second guy the same two questions. Translating this back into the 3 Gods, problem, your first question should be to ask the first God "If I asked you 'is the second God the God of Knives', would you say 'yes'?" If the first God answers "yes", you know the God of Knives is either the first or the second God, so you can ask the third God, "If I asked you 'are you the God of Knights', would you say 'yes'?" and after that you can ask the third God "If I asked you 'is the first God the God of Knives', would you say 'yes'?" and this will be enough to tell you the identity of all three Gods. On the other hand, if the answer to your first question was "no", then you know the God of Knives is either the first or the third God, so you would ask the *second* God the same two subsequent questions as above. 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". Ugh, I'll have to think about that some more...but again, this is equivalent to a problem where you have three guys named Huey, Dewey and Louie, and Huey and Dewey always tell the truth while Louie answers randomly, but they all answer with "JA" or "DA" and you don't know which word means yes and which means no. If anyone else can figure it out feel free to jump in. Jesse
Re: S, B, and a puzzle by Boolos, Smullyan, McCarthy
> And here is another puzzle, which is not entirely > unrelated with both the KK puzzles and the current probability > discussion: I put three cards, two aces and a jack, on their > face in a row. By using only one yes-no question and pointing > one of the card, you must with certainty find one of the aces. > I know where the cards are, and if you point on a ace, I will > answer truthfully (like a knight), but if you point on the jack, I > will answer completely randomly! > How will you proceed? (The puzzle is one invented by Boolos, > as a subpuzzle of a harder one by Smullyan & McCarthy. > Cf Boolos' book "Logic, logic, and logic". According to > Boolos, it illustrates something nice about the practical > importance of the excluded middle principle. And this is > a hint, perhaps.) Although it is true that if you point at a Jack the answer doesn't give you any information, you don't really need much info in that case as you know that the other two cards are Aces. As long as you are going to finally choose a card different than the one you point at, any mistaken info you get from the Jack won't hurt you. You need to come up with a question which will work when you are pointing at an Ace, and which will lead to you choosing another card. For example, point at the card at one end and ask "Is the card on the other end an Ace?" If he says yes, choose that card on the other end, and if he says no, choose the middle card. This of course works if you are pointing at an Ace because he will tell the truth, and if you are pointing at a Jack it will work because both other cards are Aces. Hal Finney
Re: S, B, and a puzzle by Boolos, Smullyan, McCarthy
At 17:42 11/10/04 +1000, Eric Cavalcanti wrote: > And here is another puzzle, which is not entirely > unrelated with both the KK puzzles and the current probability > discussion: I put three cards, two aces and a jack, on their > face in a row. By using only one yes-no question and pointing > one of the card, you must with certainty find one of the aces. > I know where the cards are, and if you point on a ace, I will > answer truthfully (like a knight), but if you point on the jack, I > will answer completely randomly! > How will you proceed? (The puzzle is one invented by Boolos, > as a subpuzzle of a harder one by Smullyan & McCarthy. > Cf Boolos' book "Logic, logic, and logic". According to > Boolos, it illustrates something nice about the practical > importance of the excluded middle principle. And this is > a hint, perhaps.) Bruno, That is a nice one. It seems on a first thought that whatever question I decide to ask, if I point on the jack the answer will be random, so that I can't gain perfect information. I did that reasoning too! From which I conclude that by the case of pointing on the jack we should get an symmetrical answer, and from this I derive the jack should be placed at the middle. Now, you will refute me. I came up with a way out, but by making an assumption that is not explicit in your statement - that I can make a question which does not have an answer. I could ask you: "Is the answer to this question no?" In case I point to an ace, you cannot answer it. In case I point to a jack, you answer randomly. I would accept that solution ... and then reformulate the question. One other solution would be if I could ask a question about other cards. This has never been forbidden. Any yes-no question is accepted. You were right that we should have said "any *answerable* yes-no question" to avoid your preceding correct but "too easy" solution ;-) I could then point to the first one and ask: is any of the first two a jack? If you answer 'no' I know that card 2 is an ace. If you answer yes I know that card 3 is an ace. Nice! It is an original solution, which refutes my point above. The solution in the book did not! It is "point on the middle cart and ask if the card on the left is an ace". Then if you got the "yes" answer you know the left card (card 1) is an ace, if you got "no" the right card (card 3) is an ace. (It did confirm my too quick and wrong reasoning!). Your solution points on the need of only *logical* symmetry! --- --- --- As a Price, I give you the (known?) Smullyan McCarthy 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". Bruno http://iridia.ulb.ac.be/~marchal/
Re: S, B, and a puzzle by Boolos, Smullyan, McCarthy
> And here is another puzzle, which is not entirely > unrelated with both the KK puzzles and the current probability > discussion: I put three cards, two aces and a jack, on their > face in a row. By using only one yes-no question and pointing > one of the card, you must with certainty find one of the aces. > I know where the cards are, and if you point on a ace, I will > answer truthfully (like a knight), but if you point on the jack, I > will answer completely randomly! > How will you proceed? (The puzzle is one invented by Boolos, > as a subpuzzle of a harder one by Smullyan & McCarthy. > Cf Boolos' book "Logic, logic, and logic". According to > Boolos, it illustrates something nice about the practical > importance of the excluded middle principle. And this is > a hint, perhaps.) Bruno, That is a nice one. It seems on a first thought that whatever question I decide to ask, if I point on the jack the answer will be random, so that I can't gain perfect information. I came up with a way out, but by making an assumption that is not explicit in your statement - that I can make a question which does not have an answer. I could ask you: "Is the answer to this question no?" In case I point to an ace, you cannot answer it. In case I point to a jack, you answer randomly. One other solution would be if I could ask a question about other cards. I could then point to the first one and ask: is any of the first two a jack? If you answer 'no' I know that card 2 is an ace. If you answer yes I know that card 3 is an ace. Is any of these the book's solution? Eric.
