Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Can you solve the hardest logic problem?

  1. Sep 2, 2015 #1
    Maybe you know that that problem was about 3 gods. 1 tells the truth, other always lie, and the last god gives a random answer. The gods can only answer a yes/no question.
    Can you tell what god lies, tell the truth or give a random answer with only 2 And ONLY 2 questions? Harder than it was, of course. In aprox 5 days I'll tell you the answer.
    Clue: a question here equals a question with the answer of the god.
     
  2. jcsd
  3. Sep 2, 2015 #2

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    What happens with questions where both "yes" and "no" are incorrect (for the truth-god) or correct (for the liar-god)?

    Without abusing those questions (this option depends on the answer to my question), there are at most 4 different answers, but you have to distinguish 6 different cases, which is not possible in general.
    You can always identify at least one god, however.
     
  4. Sep 2, 2015 #3
  5. Sep 3, 2015 #4
  6. Sep 3, 2015 #5
    Then that would have to take it from "hardest" to "impossible", wouldn't you think? It could depend what constraints you modify.
     
    Last edited: Sep 3, 2015
  7. Sep 8, 2015 #6
    Is not true. What if we ask a god "what would the random God will answer to the question Q in this moment? We'll know what god/s are not random.
     
  8. Sep 8, 2015 #7
    You are allowed to only made 2 Yes-No questions.
    My question for all 3 gods: Are you god ?
    You have 2 cases [(Truth god+Random god ) vs (Random god+Liar god)] (e.g To such a question, Truth god always says Yes, you don't know about random god, Liar god always says No and you don't know about random god)
    Because you didn't mention how many times I can repeat the same question, I will make the question "Is this guy random God ?" 1000 times to each case.
    Liar god knows but he will always lies, so he would always say No while the random god will switch repeatedly between yes and no :biggrin:, so I can find out the random god in case 2. and so can the similar explanation be done for the first case.
     
  9. Sep 8, 2015 #8

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    I think that counts as three questions.
    And that as 3000.
     
  10. Sep 8, 2015 #9

    Vanadium 50

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor

    No. Provably no.

    You are asking to determine the identities of all 3 gods. There are six possibilities - LTR, LRT, RLT, RTL, TLR, TRL. Two questions have four and only four possible answers: YY, YN, NY, NN. You cannot map the four answers to the six possibilities. QED.
     
  11. Sep 9, 2015 #10

    Vanadium 50

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor

    A more interesting question a) better defines the Random answer and b) involves a puzzle like "Which door leads to the lady, and which to the tiger". I would argue that a Random answer involves a) flipping coins in advance on whether to tell the truth or lie, b) letting the other gods see the coin, and c) providing the same answer to the same question and not re-flipping. There are other definitions one could use - one could have a supply of Liars and Truth-Tellers and randomly pick one for the third god. This actually makes things easier than the previous definition.

    Suppose you had N gods on the island, one Liar, one Truth-Teller, and N-2 Randoms. How many questions would you need? You need to identify either the Liar or Truth-Teller, and get the answer to one question. The second part is one bit of information. The first part can be represented as the number in some list of the god in question, and so needs log2(N) bits to represent that. So our answer is log2(N)+1 or log2(2N). That doesn't mean that this can be solved in that many questions - it means it cannot be solved in fewer than that many questions.

    So, for three gods and one door, you need no fewer than three questions to determine which door to open. You also need no more than three - you can ask each god the following question: "If I were to ask the non-Random member of the other two gods which door had the tiger behind it, what would he say?' Now, either two or three gods point at the same door. That one has the lady behind it.
     
  12. Sep 9, 2015 #11

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    The easiest definition is a god that simply flips a coin each time it has to answer. For meta-questions (e.g. ask the truth god "what would A answer" with A=random), the god will insert a random answer which is then processed as usual.
    At least N-1. Even if you ask a different god each time, the first N-2 gods can be random, which means you cannot use the answers reliably to get certainty about anything. I expect the true number to be much higher. A nondeterministic approach is probably much better in terms of expectation value: "Are you the truth god"? => every "no" means the god is random, as expectation value you need ~ 2 N questions.

    For one door? ;) For three doors, you can guarantee to find the door with three questions, in 1/3 of the cases you actually know it after the second question.
    If the random god is either "always truth" or "always lie", then two questions are sufficient.
     
  13. Sep 9, 2015 #12
    Working it out now, but the questions need to be the stripe of asking one about the others. Either it's "is the guy next to you a god" or "would the guy next to you tell me you're not a god?"

    How about asking 1 if 2 would tell me that 1 and 3 aren't gods, and then asking 2 if 1 would tell me that 2 and 3 are gods?
     
    Last edited by a moderator: Sep 9, 2015
  14. Sep 9, 2015 #13

    Vanadium 50

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor

    I guess that for one door, it's zero questions. :smile:

    I was thinking two doors. For three doors, you need only an extra half-bit, so I believe you that you cam solve that one in three questions as well.
     
  15. Sep 9, 2015 #14

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    For three gods and two doors, two questions are sufficient.
    The first question gives you one god that is not random, the second one gives you the door.
     
  16. Sep 11, 2015 #15
    There are 3 gods: god 1, god 2, god 3.
    Look this algorithm:

    Ask god 1 "What would the random God will answer to the question Q (you can choose the correct answer to question Q) in this moment?":
    if god 1 don't answer (becouse don't know the answer, so isn't the random god, and this question hasn't got a value):
    -god 1 can't be the true god.
    -ask god 1 question Q:
    if god 1 tells the truth, god 1 is the True God:
    -ask god 1 if god 2 or god 3... you know the next(if not, post me).

    Can you see that its posible with 2 questions?
     
  17. Sep 11, 2015 #16

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    .. then it violates the condition that the gods give an answer. That's what I was asking about in post 2 - what happens if neither "yes" nor "no" is a valid answer? If you can get a third possible reaction from the god, things are different.
    Why not? It cannot be random, but it could lie.
     
  18. Sep 11, 2015 #17
    It can't because the random answer Yes/No is asked to be answer by the random god in a certain time ("this moment"), so when I ask to god 1 "What would the random God will answer to the question Q in this moment?" If god 1 wasn't the random god, he never could answer, becouse the random god never answer in that time("this moment", and that was the question. god 1 can't answer yes or no becouse it's imposible to know a imposible situation.

    As I made the answer as an algorithm, if god 1 wasn't the random god, he would don't answer.
    About what happend about question where yes and no answers are incorrect I didin't say nothing, so it doesn't violates any rules
     
  19. Sep 11, 2015 #18

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    I don't follow your argument (that might be a possible interpretation, but then you have to define the behavior of the gods much more precisely - again, see post 2), but this is in conflict with your other statement that it cannot be the truth god if we don't get an answer.
     
  20. Sep 11, 2015 #19

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

  21. Sep 11, 2015 #20
    Mmm... I'll try to explain how the gods behave. The truth/liar gods are OBLIGATED to tell the truth or lie (that means that it know the correct answer in case of the truth god or the wrong answer in case of the liar god), but the random god can do what he whants! This is intuitive.
    Of course the key of the answer is to ask YES/NO questions where yes and no are both incorrect becouse the god don't know! You had the key, and it was correct!

    If god 1 don't answer, he isn't the random god becouse he can't answer the truth or the lie of something that he can't know!!!!! He can't know what random god will answer to question Q in that moment if he's not random-god. Is mathematical!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Can you solve the hardest logic problem?
  1. Can you solve this? (Replies: 6)

  2. Can you solve (Replies: 1)

Loading...