Three gods - True, False and Random

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Prelates, Moderators General

Re: Three gods - True, False and Random

Postby jestingrabbit » Fri Sep 10, 2010 6:49 am UTC

Slaggagary wrote:I suppose, if these God's are all knowing, then they would know my name.

so the easiest way to break down the three would be to ask them all on separate occasions "Is my name ______" to which one would, without question answer yes, that is your name and one would definitely answer no and the third would either answer yes or no.
If the random God answers yes, it would be a matter of asking a series of obvious, entirely tangible questions until chance played it's part and the random God lied. Seemed pretty simple, really....


Except that you've used an arbitrary number of questions, rather than the three the puzzle requires. You waste your three asking the same question to all three gods, at the end of which you have only identified one of the gods.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
User avatar
jestingrabbit
 
Posts: 5470
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

Re: Three gods - True, False and Random

Postby Slaggagary » Fri Sep 10, 2010 10:17 am UTC

jestingrabbit wrote:
Slaggagary wrote:I suppose, if these God's are all knowing, then they would know my name.

so the easiest way to break down the three would be to ask them all on separate occasions "Is my name ______" to which one would, without question answer yes, that is your name and one would definitely answer no and the third would either answer yes or no.
If the random God answers yes, it would be a matter of asking a series of obvious, entirely tangible questions until chance played it's part and the random God lied. Seemed pretty simple, really....


Except that you've used an arbitrary number of questions, rather than the three the puzzle requires. You waste your three asking the same question to all three gods, at the end of which you have only identified one of the gods.


ah... fair point... let me think about it.
Slaggagary
 
Posts: 8
Joined: Fri Sep 10, 2010 2:00 am UTC

Re: Three gods - True, False and Random

Postby redrogue » Mon Oct 11, 2010 11:07 pm UTC

I've modified this: http://www.rinkworks.com/brainfood/s/discrete39.shtml

...to what I believe is a correct solution:
Spoiler:
Code: Select all
Case   A      B      C
I   True   False   Random
II   True   Random   False
III   False   True   Random
IV   False   Random   True
V   Random   True   False
VI   Random   False   True

1. (to A):   If I ask B and C if I'm human, is B more likely to say 'Da'?
   Da:   Go to 2 (B is not Random)
   Ja:   Go to 5 (C is not Random)
2. (to B):   If I ask you, 'Are you random?', would you answer 'Da'?
   Da:   Go to 3 (B is False)
   Ja:   Go to 4 (B is True)
3. (to B):   If I ask you, 'Is A more truthful than C', would you answer 'Da'?
   Da: Case VI
   Ja: Case I
4. (to B):   If I ask you, 'Is A more truthful than C', would you answer 'Da'?
   Da: Case III
   Ja: Case V   
5. (to C):   If I ask you, 'Are you random?', would you answer 'Da'?
   Da: Go to 6 (C is False)
   Ja: Go to 7 (C is True)
6. (to C):   If I ask you, 'Is A more truthful than B', would you answer 'Da'?
   Da: Case II
   Ja: Case V
7. (to C):   If I ask you, 'Is A more truthful than B', would you answer 'Da'?
   Da: Case IV
   Ja: Case VI
Is 'no' your answer to this question?
redrogue
 
Posts: 119
Joined: Tue Dec 15, 2009 9:17 pm UTC

Re: Three gods - True, False and Random

Postby freddyfish » Tue Oct 19, 2010 4:15 am UTC

I feel like this was assumed but all the gods speak the same language right? so da will always mean yes always mean no independent of who we ask?
freddyfish
 
Posts: 69
Joined: Sat Oct 20, 2007 3:08 am UTC

Re: Three gods - True, False and Random

Postby jestingrabbit » Tue Oct 19, 2010 5:53 am UTC

freddyfish wrote:I feel like this was assumed but all the gods speak the same language right? so da will always mean yes always mean no independent of who we ask?


Yeah. I don't think its explicitly stated though.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
User avatar
jestingrabbit
 
Posts: 5470
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

Re: Three gods - True, False and Random

Postby husky123 » Sat Oct 23, 2010 3:13 pm UTC

i haven't read through the replies here (been trying to work on this one for weeks, hope i'll crack it soon!, but kudos to everyone who solved this question. this question is touted as the "Hardest logic puzzle ever" !!
husky123
 
Posts: 1
Joined: Sun Oct 10, 2010 9:22 am UTC

Re: Three gods - True, False and Random

Postby lewikee » Wed Oct 27, 2010 7:14 pm UTC

Just to make it clear that I understand the rule:

If I ask the God (who happens to be the Truth God) if the God I point to (who happens to be the Random God) would answer a question in some way, the Truth God can't know the random outcome of the Random God's answer right? Or are the Random God's random answers pre-rolled and ready to go no matter what I ask?

Basically what I'm asking is when does Random God roll for his answer? Before my questions (he would just roll three times and have them ready in case I ask him all 3 questions)? Then the Truth God could know how to answer me... Or does he roll at the moment of my question? (where the the Truth God could not know)
lewikee
 
Posts: 47
Joined: Wed Oct 27, 2010 5:37 pm UTC

Re: Three gods - True, False and Random

Postby jestingrabbit » Thu Oct 28, 2010 12:15 am UTC

You shouldn't need any god to know how the random god will answer.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
User avatar
jestingrabbit
 
Posts: 5470
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

Re: Three gods - True, False and Random

Postby lewikee » Thu Oct 28, 2010 3:06 am UTC

jestingrabbit wrote:You shouldn't need any god to know how the random god will answer.


Let me give you a scenario where you would need a God to know how the Random God would answer:

Gods are left through right. You ask Left God (who in this case happens to be the Truth God) the following question about Middle God (who in this case happens to be the Random God). By the way, so far this situation is completely plausible.

"For my first question to Middle God, would Middle God answer "ja" to the question 'Is Left God the Truth God?'"

How would the Truth God know which answer Random God would randomly answer unless the random answers were pre-announced to all Gods? This is what I mean by a pre-roll: the Random God's answers are still random, but are pre-determined before the question-asking begins. If Random God's answers are randomly selected at the time of my question, Truth God cannot answer my question quoted above. However if Random God's answers are randomly pre-selected (ja-ja-da, ja-da,ja, etc...), Truth God can answer my question.

Now if your point was merely that the solution to this problem does not involve asking any God how the Random God would answer, that's fine but that is also a hint, and not an elaboration of the rules of the game. For those seeking to find the solution without any such hints (if of course, your comment hinted at the composition of the solution, which might not be the case) we would like to know the full constraints of the problem, including the conditions under which Random God picks his random answers.

In summary: Does Random God pre-select his random answers or does he select them at the time of his answer?
lewikee
 
Posts: 47
Joined: Wed Oct 27, 2010 5:37 pm UTC

Re: Three gods - True, False and Random

Postby t1mm01994 » Thu Oct 28, 2010 9:08 am UTC

He selects them at the time he has to answer. Also, he answers, if possibly, in the way to guide you through wrong thoughts. Yes, he can read minds.
User avatar
t1mm01994
 
Posts: 299
Joined: Mon Feb 15, 2010 7:16 pm UTC
Location: San Francisco.. Wait up, I'll tell you some tales!

Re: Three gods - True, False and Random

Postby Mewzle » Wed Nov 03, 2010 8:08 pm UTC

Redrogue: How wonderful it would be if that worked, though I don't think it does.

I'll try with an example. In this example, unknown to you, A is the Truth-teller, B is Random, C is False. Ja, stands for yes and Da stands for no.

Code: Select all
1. (to A):   If I ask B and C if I'm human, is B more likely to say 'Da'?
   Da:   Go to 2 (B is not Random)
   Ja:   Go to 5 (C is not Random)


B, the random, would answer either Da or Ja equally. C, however, would always answer Da. Therefore the truth teller would answer Da, no, B is not more likely to say Da.

Straight away, this says B is not random, which he is.

Then we move to 2,

Code: Select all
2. (to B):   If I ask you, 'Are you random?', would you answer 'Da'?
   Da:   Go to 3 (B is False)
   Ja:   Go to 4 (B is True)


He would be random. Lets say he goes Ja.

Code: Select all
4. (to B):   If I ask you, 'Is A more truthful than C', would you answer 'Da'?
   Da: Case III
   Ja: Case V 


Again, random, so lets go Ja again.

Case V says A is random, B is true and C is false, which is unfortunately not correct. Sorry! (Unless i've made a mistake, which is perfectly possible)
Mewzle
 
Posts: 7
Joined: Sat Oct 30, 2010 5:03 pm UTC

Re: Three gods - True, False and Random

Postby Mewzle » Wed Nov 03, 2010 8:58 pm UTC

Spoilers ahead, for the curious!

Spoiler:
A helpful task in this is discerning, at the very least, a non-random god which we can ask two questions to find other gods, and therefore find the third by elimination. So, we need to find in one question a non-random god, though it doesn't matter which.

In this, we're going to ask 'B'. It doesn't quite matter which, but just for arguments/examples sake, i'm going to ask B.

If we ask him a question concerning one of the other two to decide which is not random, and B is random, it doesn't matter which direction he points us in, as both will point us to a non-random person.

We therefore need a question that makes the truth teller point us to the liar, and the liar point us to the truth teller. For this, we just need a 'If I asked you X, would you say Y'. We don't want the random, so we use 'If I asked you is <A or C> random, would you say <Ja or Da>"

Say we use A and Ja, and Ja is true. A is the Liar, B is the Truth Teller, and C is random. We ask B, the truth teller, whether he would say A is random. He would answer da, no. If he answers da, we move to A as A is a non-random character. If A was Random, B the truth teller and C Random, he would say ja, and so we go to C. If A was the Truth teller, B was the Liar and C random, the liar would say da, and so we move to A. If A was Random, B the Liar and C the truth teller, he would say ja, and so we go to C.

If he says Ja, we go to C for the final two questions (Of which there are many), and if he says Da we go to A.

It works for the reverse, So we're using A again, and Ja, but Ja is false this time. A is the Liar, B is the truth teller and C is random. B, the truth teller, is asked if A is random, which he isn't, therefore A would say Ja, false. If asked, would he say ja, he would say da, yes he would say ja. As we said earlier, if he says da, we go to A, which is the liar. It works for the rest.

So, we ask B "If I asked you is A random, would you say 'Da'", and we then move our questions to A if he says da, and C if he says ja.

Next, finding one of the gods. We need to ask him a question about what he would answer, as this causes the truth teller and liar to always say either ja or da, depending which is true. In this case "If I asked you whether you were the <Truth teller or liar>, would you say <ja or da>. Lets use Truth teller and Ja. We ask the truth teller, he always says ja (Either ja is true, and so he would answer true to yes he is the truth teller, or ja is false, and he would answer no when asked would he say that he isn't the truth teller). The reverse goes for the liar, who says da.

So, the second question could be "If I asked you 'If I asked you 'Are you the truth teller', would you say ja?", and we now know whether he is the truth teller or the liar.

The last question can work in very much the same way.

"If I asked you 'Is B random", would you say ja?". If B is random, the truth teller says 'true', and so says ja if ja is true and ja if da is true. The liar says ja if ja is true, and ja if da is true. If B isn't random, the truth teller says Da if ja is true, and da if da is true, and the liar says da if ja is true, and da if da is true.

If he says ja, B is random. If he says da, the person who hasn't answered a question is random. The third is found by elimination.

1. Ask B "If I asked you is A random, would you say 'Da'", and we then move our questions to A if he says da, and C if he says ja.
2. "If I asked you 'If I asked you 'Are you the truth teller', would you say ja?" if he says Ja, he is the truth teller, Da, he is the liar.
3. "If I asked you 'Is B random", would you say ja?" If he says ja, B is random, if he says da, the unspoken-to-god is random.
Mewzle
 
Posts: 7
Joined: Sat Oct 30, 2010 5:03 pm UTC

Re: Three gods - True, False and Random

Postby mike-l » Mon Nov 15, 2010 9:42 pm UTC

jestingrabbit wrote:
freddyfish wrote:I feel like this was assumed but all the gods speak the same language right? so da will always mean yes always mean no independent of who we ask?


Yeah. I don't think its explicitly stated though.


This is not really needed though for at least one solution. It is for another, though it's easily changed to not need it. So in some sense, any solution which relies on this fact is 'weaker' than one that doesn't.
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.
mike-l
 
Posts: 2675
Joined: Tue Sep 04, 2007 2:16 am UTC

Re: Three gods - True, False and Random

Postby Wnderer » Thu Nov 18, 2010 4:50 pm UTC

mike-l wrote:
jestingrabbit wrote:
freddyfish wrote:I feel like this was assumed but all the gods speak the same language right? so da will always mean yes always mean no independent of who we ask?


Yeah. I don't think its explicitly stated though.


This is not really needed though for at least one solution. It is for another, though it's easily changed to not need it. So in some sense, any solution which relies on this fact is 'weaker' than one that doesn't.


Spoiler:
There are two phrases used in solving these puzzles. One is the "If I were to ask you". Given a statement that is either True or False, the Truth teller is a function T(statement) where T(True) = True and T(False) =False and the Liar is L(statement) where L(False) = True and L(True) = False. Then the "If I were to ask you" gives you the nested functions T(T(True)) = L(L(True)) = True and T(T(False)) = L(L(False)) = False.

The second phrase "would you say da" or "would you say ya" translates to (da = yes) or (ya = yes)

the truth tables then looks like
Code: Select all
   A                B             A=B    Answer
statement     (ya = yes)
True              True           True       ya
True              False          False      ya
False             True           False      da
False             False          True       da

or
   A                B              A=B    Answer
statement     (da = yes)
True              True           True       da
True              False          False      da
False             True           False      ya
False             False          True       ya

So by how you ask the question you define what ya and da mean.
User avatar
Wnderer
 
Posts: 626
Joined: Wed Feb 03, 2010 9:10 pm UTC

Re: Three gods - True, False and Random

Postby mike-l » Thu Nov 18, 2010 6:14 pm UTC

Wnderer wrote:
mike-l wrote:
jestingrabbit wrote:
freddyfish wrote:I feel like this was assumed but all the gods speak the same language right? so da will always mean yes always mean no independent of who we ask?


Yeah. I don't think its explicitly stated though.


This is not really needed though for at least one solution. It is for another, though it's easily changed to not need it. So in some sense, any solution which relies on this fact is 'weaker' than one that doesn't.


Spoiler:
There are two phrases used in solving these puzzles. One is the "If I were to ask you". Given a statement that is either True or False, the Truth teller is a function T(statement) where T(True) = True and T(False) =False and the Liar is L(statement) where L(False) = True and L(True) = False. Then the "If I were to ask you" gives you the nested functions T(T(True)) = L(L(True)) = True and T(T(False)) = L(L(False)) = False.

The second phrase "would you say da" or "would you say ya" translates to (da = yes) or (ya = yes)

the truth tables then looks like
Code: Select all
   A                B             A=B    Answer
statement     (ya = yes)
True              True           True       ya
True              False          False      ya
False             True           False      da
False             False          True       da

or
   A                B              A=B    Answer
statement     (da = yes)
True              True           True       da
True              False          False      da
False             True           False      ya
False             False          True       ya

So by how you ask the question you define what ya and da mean.


Yes, and none of that depends on
Spoiler:
what ya and da mean to any god other the one you are asking.

So this solution actually works for the puzzle:
Each god speaks in a language to which ya is either yes or no (possibly different for each god), and you have no idea what the other word is (and it may be different for each god), how can you ask 3 yes or no questions to figure out all of their identities.

There's also a solution which is essentially the same but uses the phrasing
Spoiler:
Are either both or neither of (statement) and (da="yes") true, to which the response will be "da" whenever the statement is true. But since I'm explicitely asking if da means something, then it is affected if they speak different languages. It's trivially fixed by changing it to (da="Yes" in your language)
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.
mike-l
 
Posts: 2675
Joined: Tue Sep 04, 2007 2:16 am UTC

Re: Three gods - True, False and Random

Postby redrogue » Thu Nov 18, 2010 11:06 pm UTC

Mewzle wrote:Redrogue: How wonderful it would be if that worked, though I don't think it does.


I believe I have that first question's answers backwards. Sorry.

Spoiler:
Repeated cases:

Case A B C
I True False Random
II True Random False
III False True Random
IV False Random True
V Random True False
VI Random False True


Here are two questions without the 'da/ja' confusion. I've replaced Da with 'Yes' in A1, and Da with 'No' in B1... AND switched the answers around:

A1. (to A): If I ask B and C if I'm human, is B more likely to say 'Yes'?
No: Go to 2 (B is not Random)
Yes: Go to 5 (C is not Random)

vs.

B1. (to A): If I ask B and C if I'm human, is B more likely to say 'No'?
Yes: Go to 2 (B is not Random)
No: Go to 5 (C is not Random)

A1's answers (for each scenario) are:
I: No
II: Yes
III: No
IV: Yes
V: Random Y/N
VI: Random Y/N

B1's answers are:
I: Yes
II: No
III: Yes
IV: No
V: Random Y/N
VI: Random Y/N

...but because the yes/no answers switch as well, the rest of it works.

We end up in the correct place if we swap the 'Da' and 'Ja' answers. The FIRST question should be this (note change in bold):

1. (to A): If I ask B and C if I'm human, is B more likely to say 'Da'?
Ja: Go to 2 (B is not Random)
Da: Go to 5 (C is not Random)


Edit: After some analysis, I've realized that all my questions are off.

Corrected solution, detailed explanation:
Spoiler:
Code: Select all
Case   A      B      C
I   True   False   Random
II   True   Random   False
III   False   True   Random
IV   False   Random   True
V   Random   True   False
VI   Random   False   True

1. (to A):   If I ask B and C if I'm human, is B more likely to say 'Da'?
   [b]Ja[/b]:   Go to 2 (B is not Random)
   [b]Da[/b]:   Go to 5 (C is not Random)
2. (to B):   If I ask you, 'Are you [b]the True god[/b]?', would you answer 'Da'?
   [b]Ja[/b]:   Go to 3 (B is False)
   [b]Da[/b]:   Go to 4 (B is True)
3. (to B):   [b]If I ask A and C if I'm human, is A more likely to say 'Da'?[/b]
   Da: Case VI
   Ja: Case I
4. (to B):  [b] If I ask A and C if I'm human, is A more likely to say 'Da'?[/b]
   Da: Case V
   Ja: Case III
5. (to C):   If I ask you, 'Are you [b]the True god[/b]?', would you answer 'Da'?
   [b]Ja[/b]: Go to 6 (C is False)
   [b]Da[/b]: Go to 7 (C is True)
6. (to C):   [b]If I ask A and B if I'm human, is A more likely to say 'Da'?[/b]
   Da: Case II
   Ja: Case V
7. (to C):   [b]If I ask A and B if I'm human, is A more likely to say 'Da'?[/b]
   Da: Case VI
   Ja: Case IV



Question 1 is to locate a god who is not the random god.
If I ask B and C if I'm human, is B more likely to say 'Da'?

'Da' Means 'Yes'
True,False,Random --> 'Ja' (No, B isn't more like to say Yes)
True,Random,False --> 'Da' (Yes, B is more likely to say Yes)
False,True,Random --> 'Ja' (No, B isn't more likely to say Yes)
False,Random,True --> 'Da' (Yes, B is more likely to say Yes)
Random,True,False --> Random
Random,False,True --> Random

'Da' Means 'No'
True,False,Random --> 'Ja' (Yes, B is more like to say No)
True,Random,False --> 'Da' (No, B isn't more likely to say No)
False,True,Random --> 'Ja' (Yes, B is more likely to say No)
False,Random,True --> 'Da' (No, B isn't more likely to say No)
Random,True,False --> Random
Random,False,True --> Random

In all cases, 'Ja' tells us B is either False or True, and 'Da' tells us C is either false or true. Note that when we ask Random the question, we get a Random answer, but since the Next Question isn't directed at him, it doesn't matter. We split to 2 & 5.


Questions 2 & 5 determine if I'm talking to True or False.
If I ask you, 'Are you Truthful?', would you answer 'Da'?

'Da' Means 'Yes'
True --> Da (Yes, I would answer Yes)
False --> Ja (No. I would answer Yes, but since I'm lying...)

'Da' Means 'No'
True --> Da (No, I wouldn't answer No)
False --> Ja (Yes. I wouldn't answer No, but since I'm lying...)


Questions 3, 4, 6, & 7 - Determine the identity of the other gods
If I ask A and (insert other god here) if I'm human, is A more likely to say 'Da'?

See first question, same logic.
Is 'no' your answer to this question?
redrogue
 
Posts: 119
Joined: Tue Dec 15, 2009 9:17 pm UTC

Re: Three gods - True, False and Random

Postby math » Mon Jan 24, 2011 2:58 am UTC

Is this three questions each? Or three altogether?
Ghostly, she stood in front of him and looked into his eyes. "I am here," she said. "I am here. I want to touch you." She pleaded: "Look at me!" But he would not see her; he only knew how to look at the outside of things.
User avatar
math
 
Posts: 30
Joined: Sun Oct 24, 2010 4:25 am UTC

Re: Three gods - True, False and Random

Postby jestingrabbit » Mon Jan 24, 2011 4:32 am UTC

math wrote:Is this three questions each? Or three altogether?


Three altogether. One respondent per question.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
User avatar
jestingrabbit
 
Posts: 5470
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

Re: Three gods - True, False and Random

Postby math » Tue Jan 25, 2011 3:13 am UTC

I can only guess at how to figure out which is true or false, and then get two that might be the other or random. So difficult, my mind is blown.
Ghostly, she stood in front of him and looked into his eyes. "I am here," she said. "I am here. I want to touch you." She pleaded: "Look at me!" But he would not see her; he only knew how to look at the outside of things.
User avatar
math
 
Posts: 30
Joined: Sun Oct 24, 2010 4:25 am UTC

Re: Three gods - True, False and Random

Postby teelo » Fri Jan 28, 2011 12:08 pm UTC

Just ask the same question to each of them infinite times until one of them changes their answer. Bam you know who the random god is.
teelo
 
Posts: 429
Joined: Thu Apr 08, 2010 11:50 pm UTC

Re: Three gods - True, False and Random

Postby t1mm01994 » Fri Jan 28, 2011 12:59 pm UTC

teelo wrote:Just ask the same question to each of them infinite times until one of them changes their answer. Bam you know who the random god is.


You fail forever. Read the first post again.
User avatar
t1mm01994
 
Posts: 299
Joined: Mon Feb 15, 2010 7:16 pm UTC
Location: San Francisco.. Wait up, I'll tell you some tales!

Re: Three gods - True, False and Random

Postby Lenoxus » Fri Feb 17, 2012 7:39 pm UTC

It should be noted that even if it were possible to query a single god an infinite number of times (and if, for simplicity's sake, the gods all answered in English), the correct inference from an inifite number of "Nos" to "Do pigs have wings?" or an infinite number of "Yeses" to "Is the Pope Catholic?" would be that the god you were talking to was definitely not False, was True with probability 1 (or "almost surely" True), and was Random with probability 0 (or "almost surely" not Random). In probability theory, that's one of the weird consequences of performing an infinite number of trials. See Wikipedia's page on almost surely for more.

Meanwhile, I'm fairly positive that if the False god is removed, the puzzle becomes unsolvable in any number of questions, due to Random's ability to perfectly simulate the reverse of the actual situation, and your lack of a "spare" god you can afford to ditch. I also think it's unsolvable with more than one Random, amid any number of Trues (but I'm less certain about that).
User avatar
Lenoxus
 
Posts: 91
Joined: Thu Jan 06, 2011 11:14 pm UTC

Re: Three gods - True, False and Random

Postby Nitrodon » Fri Feb 17, 2012 8:18 pm UTC

It is impossible when at least half of the gods are Random (but you can find an algorithm which almost surely terminates), and possible when fewer than half of the gods are Random.
Spoiler:
Suppose at least half of the gods are Random. There is some true configuration of the various gods. Consider any alternate configuration in which every true non-Random is Random (which exists because there are at least as many Randoms as non-Randoms). There is a nonzero probability that each response is consistent with the alternate configuration, so it is impossible to tell the configurations apart.

Now, suppose fewer than half of the gods are Random. You can ask each god which set of gods is Random (by asking n-1 questions per god), and the non-Randoms will all agree with each other. The correct set of Randoms is thus the set that more than half of the gods agree on. This is a very inefficient solution, but proves that it is possible.
Nitrodon
 
Posts: 461
Joined: Wed Dec 19, 2007 5:11 pm UTC

Re: Three gods - True, False and Random

Postby Lenoxus » Sat Feb 18, 2012 1:29 am UTC

Nitrodon wrote:It is impossible when at least half of the gods are Random (but you can find an algorithm which almost surely terminates), and possible when fewer than half of the gods are Random.
Spoiler:
Suppose at least half of the gods are Random. There is some true configuration of the various gods. Consider any alternate configuration in which every true non-Random is Random (which exists because there are at least as many Randoms as non-Randoms). There is a nonzero probability that each response is consistent with the alternate configuration, so it is impossible to tell the configurations apart.

Now, suppose fewer than half of the gods are Random. You can ask each god which set of gods is Random (by asking n-1 questions per god), and the non-Randoms will all agree with each other. The correct set of Randoms is thus the set that more than half of the gods agree on. This is a very inefficient solution, but proves that it is possible.


Aha! Yes, that makes sense, and it's easy to translate with some Falses thrown in by the meta-question trick.

I wonder if there are any puzzles like this where the question is "What is the fewest number of questions in which you are guaranteed to figure out who's who?"
User avatar
Lenoxus
 
Posts: 91
Joined: Thu Jan 06, 2011 11:14 pm UTC

Re: Three gods - True, False and Random

Postby hamsterofdeath » Thu Mar 01, 2012 8:31 pm UTC

if you ask
Spoiler:
"is <true/false-question here> XOR are you going to lie to me?", then you force any of the gods to tell you the answer to your question :)

truth god:
<your question> XOR no:
yes xor no -> yes
no xor no -> no

lie god:
<your question> XOR yes:
yes xor yes -> no, but the god lies so it becomes yes
no xor no -> yes, but the god lies so it becomes no

random god:
same as one of the above. to not give an invalid answer that leads to a paradox ("this sentence is false"), the god has to decide whether to lie or to speak the truth.

anyway, now you can go ahead and ask "is the sun hot xor are you going to lie to me". the answer is the word for yes.
and there are 6 possibles states for the gods, but only 2 questions left. fail :(
hamsterofdeath
 
Posts: 4
Joined: Sun Feb 26, 2012 8:54 pm UTC

Re: Three gods - True, False and Random

Postby nishank » Fri May 11, 2012 11:46 pm UTC

Spoiler:
T
F
R

Are you random.
True- no (he cannot answer)
False-no( he can't really know either so he'd have to say no since he cant know true or false)
random(may say yes) only random can answer yes.

on (1)
if i can ask them same questions recursively.

If (2), find random god by asking same Q's repeatedyly
Second question.

Have you been random,
recurse,
true will answer in no
false answer in yes.
random may answer yes or no.
you get true, hence you get false too

i am assuming from 1 and 2 .
assumptions from puzzle on front page.
viewtopic.php?f=3&t=84249
nishank
 
Posts: 29
Joined: Fri May 11, 2012 9:58 pm UTC

Previous

Return to Logic Puzzles

Who is online

Users browsing this forum: MSNbot Media and 2 guests