wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Hard: Truth, Falsehood, Randomness
        
(Message started by: ootte on Jul 24^th, 2002, 4:00pm)

Title: Hard: Truth, Falsehood, Randomness
Post by ootte on Jul 24^th, 2002, 4:00pm

Ask the three guys one question that they can't answer correctly (e.g. they don't have the knowledge, yada yada)

the liar tells you YES, the truthteller NO, the randomteller: YES/NO.

If two people answer NO and one answers YES, the YES-teller is the liar. If two people answer YES and one answers NO, the NO-teller is the liar.

In the first case, ask the liar who of the both others left is the truthteller. He will give the wrong answer (= tells you the randomteller).

In the second case, ask the truthteller who of the both others left is the liar. He will give the right answer.

So one can correctly identify the three.

--
Oliver

Title: Re: Hard: Truth, Falsehood, Randomness
Post by tonza on Jul 25^th, 2002, 2:33am

But you just made four questions, first one for everyone and after that one for the liar or truthteller...

Title: Re: Hard: Truth, Falsehood, Randomness
Post by ootte on Jul 25^th, 2002, 2:55am

on 07/25/02 at 02:33:40, tonza wrote:

But you just made four questions, first one for everyone and after that one for the liar or truthteller...

Yeah, you're right. Then ask two random guys what the answer of all three would be:

{T, F, R}
possibilities are:

the truthteller would answer: NO, YES, YES/NO
the randomteller would answer: YES/NO, YES/NO, YES/NO
the liar would answer: YES, NO, YES/NO

In case you caught the truthteller and the liar, all answers from one will be negations of the other. Then go on asking guy 1 how guy2 would answer "Is the guy1 the liar?". Negate the answer and you got the liar. The other guy is the truth teller and the last guy is the random one.

In case you caught the truthteller/liar and the randomteller.
Look for answers that are the same. If there is one, one guy has to be a liar/truthteller the other one is the randomteller.
Ask the third guy the same question like above, and you are done.

PS: I must admit there are some flaws in this reasoning, but it was a five minute shot.

--
Oliver

Title: Re: Hard: Truth, Falsehood, Randomness
Post by Steven Noble on Jul 27^th, 2002, 5:51pm

to me a yes/no question is a question that can only be answered by one yes or one no. By asking only three questions you are only allowed three answers.

here is a sol'n that follows these rules without any "bending"

first note that there are only six possible states
(T=truth teller, R=Random Answerer, L=Liar)
[T,R,L,},{T,L,R},{L,R,T},{L,T,R,},{R,T,L,},{R,L,T]
ask the first person if either the following statements are true
the second person is the Truth Teller
the third person is the Liar

in other words the question is "is (person 2 T) or (person 3 L)

if the answer is yes you know the 3rd person is not random
if the answer is no you know the 2nd person is not random

the rest is easy. you can ask the non-random person if he is random. then ask him if the first person is random.

There are obviously other questions that will work but I am curious if there are any other strategies... in other words a strategy that the first question doesn't reveal a player that can't be Random

Title: Re: Hard: Truth, Falsehood, Randomness
Post by tim on Jul 28^th, 2002, 1:44am

No, the first question must always eliminate a man from being random.

If the first man you ask is random, you get no information, and both possibilities (RTL and RLT) remain. The best you can do with the other four possibilities is split them evenly between yes and no answers. So either answer gives you four cases to consider.

If you cannot determine a non-random man, then there is a case in which you get a random answer. We'll assume you can split the other three cases reliably between yes and no. However, the random case goes both ways -- meaning that for the last question there is always the chance that you will have three cases and only a single yes/no question left to distinguish them. Oops.

So the only possible solutions are ones that positively identify a non-random person in the first round.

Title: Re: Hard: Truth, Falsehood, Randomness
Post by tim on Jul 28^th, 2002, 2:17am

There is one somewhat sneaky question you might be able to employ.

Label the men 1, 2, and 3. Ask 1 whether 2 would say yes if you asked him "Would 1 say yes if I asked him whether 1 equals 1?" Assume that their brains don't explode trying to process the convoluted question. Regardless of its complexity, the truth value is well-defined and it is in fact a yes/no question.

Let's consider the cases:

TLR - "No" (Since 1 would say yes to 1=1, 2 would thus lie and say no, and 1 would truthfully report this)
LTR - "Yes" (1 would say no to 1=1, 2 would truthfully say no, and 1 will lie about 2 saying no)
RLT: Yes or no, randomly
RTL: Yes or no, randomly
TRL: 1 can't know what 2 would say since 2's answer cannot be known in advance. Answering either yes or no risks a lie. He has to be truthful and say "I don't know" or something similar.
LRT: Again, 1 can't know what 2 would say, and can't risk saying either "yes" or "no" because he might be telling the truth accidentally. He can't even use anything similar to the previous answer, since it would be true.

If you get a simple yes/no answer, ask the same question (replacing 1 with 3 and 2 with 1) to person 3. The same reasoning applies, and will tell you exactly who is who. Otherwise you already know who is who.

That takes only two questions, sometimes one. I strongly suspect that the wording of the question will be tightened up to exclude this thoroughly twisted solution.

Title: Re: Hard: Truth, Falsehood, Randomness
Post by Aleksi Liimatainen on Jul 31^st, 2002, 5:06am

Once you've successfully identified one nonrandom man with one question, the rest is easy. So all you need to do is figure out that one question.

You can force both liar and truthteller to give the same answer, jus ask them what the other one would say. The random one will of course answer randomly, but in that case he is the one you're talking to.

Here is the solution:

Call the men "A", "B" and "C".

1st question, to A: "Would your nonrandom friend call B random?"
(both liar and truthteller will answer "wrong". Random says whatever.)
"Yes"-> B is not random, or A is random-> B can't be random.
"No"-> B is random, or A is random-> C can't be random.

2nd question, to the nonrandom one: "Would your nonrandom friend call you a liar?"
Yes-> He's truthteller.
No-> He's liar.

3rd question, to the same man: "Is A random?"
Now you know if he is telling the truth, and can easily determine who is who.

Title: Re: Hard: Truth, Falsehood, Randomness
Post by Cheenius on Jul 31^st, 2002, 9:21am

>:(
Wait a minute, let's not beat around the bush, that answer is an IF statement:

IF B is ? THEN
Would C say B is ?
ELSE
Would B say B is ?

Is that legal? I mean it's not explicitly illegal, so in the vein of think outside the box it's legal. Us po' riddle doers ought to be warned about such badness though. Change the question to ok IF statements if IF statements are ok. I was putting myself in the no IF box just cause the other problem specifically excludes such things.

May one use a compound question too?

1.Is (B ? and C T) or (B ~ and C ?)
2.Does someone tell the truth?
3.Is A Random?

Get this crappy riddle out of here, or warn us about its lameness. (Alternately someone verify that there's a more reasonable answer...) I resent wasting all my time penned up thinking about an answer without a compound statement since the only reason I was trying to think of a non-compound statement was that the simpler 2 man version explicitly forbids it.

Title: Re: Hard: Truth, Falsehood, Randomness
Post by Pat Swanson on Apr 23^rd, 2003, 6:28pm

I think I have a simple solution: Ask one of the three a question they can't possible know the answer to. Since the truthteller doesn't know the answer, he can't be sure he'll tell the truth. He won't give an answer to your question. This goes for the liar as well. Only the random one can answer this question.

If you get an answer, move on to the other two. Ask one of them if he is an elephant, or something similarily obvious to you. Then you will know the identity of all three.

if you don't get an answer, ask the next guy a question he can't know the answer to. If he answers, he's the random one. Then just ask the elephant question to the guy who couldn't answer. You'll know all three again.

f he doesn't answer, the third guy must be the random one. Just ask the elephant question to one of the two guys you've already talked to.

I admit that this method is a bit sneaky, but it seems to work.

Title: Re: Hard: Truth, Falsehood, Randomness
Post by James Fingas on Apr 25^th, 2003, 2:00pm

Cheenius,

All "IF" statements can be written using just AND, OR, and NOT, so I would say an "if" statment is allowed, especially if you rephrase it. For instance:

"If I got hit on the head with a brick, then I am unconscious" is equivalent to "I am unconscious, or I didn't get hit on the head with a brick".

If you're looking for simpler, prettier answers, they're out there. Your first question could be:

"Does person #2 tell the truth more often than person #3?"

This question doesn't even involve ANDs or ORs, but still fulfills the need to find one non-random person.