mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2013-02-13, 08:06   #1
Mr. P-1
 
Mr. P-1's Avatar
 
Jun 2003

100100100012 Posts
Default True and false oracles.

There are 2n+1 oracles. Most of them are genuine. These give a true yes-or-no answer to any suitable question you put to them. (The question must have a true answer which is either yes or no. Don't try to tie them up in a liar paradox or bad things will happen to you,) However up to n of them are false. These can answer yes or no to any question regardless of whether it is true or not.

You have n questions. You choose what to ask and which oracle to put your question to. You are free to put more than one question to the same oracle, but each question may be put to one oracle only.

Your task is to identify a true oracle.
Mr. P-1 is offline   Reply With Quote
Old 2013-02-13, 08:18   #2
axn
 
axn's Avatar
 
Jun 2003

479010 Posts
Default

Quote:
Originally Posted by Mr. P-1 View Post
However up to n of them are false. These can answer yes or no to any question regardless of whether it is true or not.
Clarification required: Does this mean a false oracle can answer correctly to a question?
axn is offline   Reply With Quote
Old 2013-02-13, 09:31   #3
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

8,963 Posts
Default

Quote:
Originally Posted by Mr. P-1 View Post
Don't try to tie them up in a liar paradox or bad things will happen to you
"oracle" like in "they can tell the future"?
May I ask oracle 1 if oracle n will tell me the true?
And then ask oracle 2 if oracle 1 was telling the true?
And then ask oracle 3 if oracle 2 was telling the true?
....
And then ask oracle k if oracle k-1 was telling the true?
....
k=2,n

(They are technically different questions, as k is different every time. )
Hmmmm is n odd or even?

Joking apart, this is like the "prince of persia" problems, where there are many doors, some have princesses behind, some have tigers, on the doors of the rooms with tigers is written a lie, like "this room contain a princess" or "room 467 contains a tiger", etc, on the doors with princesses there is a sentence in the same manner, but the sentence is true. The task is to open a door with a princess (and obviously marry her :P) and in the same time avoid opening a door with a tiger, which (again obviously) will eat you, therefore you (again obviously) are allowed to open ONE door only. And end up either eaten by a tiger, or married, which won't make too much difference, at the end...

For that problem I know how to find a solution, if one exists.

[edit 2: why you need n questions? the minimum number should be much smaller, if I can ask ANY question]

Last fiddled with by LaurV on 2013-02-13 at 09:39 Reason: s/is/if
LaurV is offline   Reply With Quote
Old 2013-02-13, 10:08   #4
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

8,963 Posts
Default

Quote:
Originally Posted by axn View Post
Clarification required: Does this mean a false oracle can answer correctly to a question?
Most probably not, otherwise there is no deterministic solution, one liar can chose to answer correctly to a number of your questions, so there can only be a "probabilistic" solution. A liar should ALWAYS tell lies. Also (see my little joke above) there should be clear specified what kind of questions I can ask, and what "different" means. I can ask first n oracles questions like, for oracle k, the question is "is k prime?", they are technically different, as the k is different, and if I only get wrong answers, then I can pick one oracle from the remaining n+1. If the questions are considered not to be different, I can ask any other question to which I know the answer (in all those cases, the puzzle is trivial).

Last fiddled with by LaurV on 2013-02-13 at 10:17
LaurV is offline   Reply With Quote
Old 2013-02-13, 10:39   #5
axn
 
axn's Avatar
 
Jun 2003

2×5×479 Posts
Default

Quote:
Originally Posted by LaurV View Post
Most probably not, otherwise there is no deterministic solution, one liar can chose to answer correctly to a number of your questions, so there can only be a "probabilistic" solution. A liar should ALWAYS tell lies.
A clarification would be nice.

Quote:
Originally Posted by LaurV View Post
Also (see my little joke above) there should be clear specified what kind of questions I can ask, and what "different" means. I can ask first n oracles questions like, for oracle k, the question is "is k prime?", they are technically different, as the k is different, and if I only get wrong answers, then I can pick one oracle from the remaining n+1. If the questions are considered not to be different, I can ask any other question to which I know the answer (in all those cases, the puzzle is trivial).
I interpreted that differently. You can ask the same question to different oracles. It is just that each would be considered a new question (and thus count towards your quota for n). Perhaps another clarification is in order?
axn is offline   Reply With Quote
Old 2013-02-13, 10:57   #6
axn
 
axn's Avatar
 
Jun 2003

2×5×479 Posts
Default

One more clarification: If I ask a true oracle to predict the answer a specific false oracle would give to a specific hypothetical question (say 'is 1 > 2?'), would that be a well-defined question with a definite answer, or will heads explode?!

Last fiddled with by axn on 2013-02-13 at 10:58
axn is offline   Reply With Quote
Old 2013-02-13, 11:13   #7
Jayder
 
Jayder's Avatar
 
Dec 2012

2·139 Posts
Default

May I let n=0?
Jayder is offline   Reply With Quote
Old 2013-02-13, 15:50   #8
Mr. P-1
 
Mr. P-1's Avatar
 
Jun 2003

7×167 Posts
Default

First of all, I made an error in posing the question, and a rather serious one at that. You have 2n-1 questions. My apologies.

Quote:
Originally Posted by axn View Post
Clarification required: Does this mean a false oracle can answer correctly to a question?
Yes.

Quote:
Originally Posted by LaurV View Post
"oracle" like in "they can tell the future"?
May I ask oracle 1 if oracle n will tell me the true?
And then ask oracle 2 if oracle 1 was telling the true?
And then ask oracle 3 if oracle 2 was telling the true?
....
And then ask oracle k if oracle k-1 was telling the true?
You have to ask a well-defined question:- one for which the answer is certainly "yes or no" at the time asked. Also the false oracles are free to choose which answer to give, just as you can choose what questions you will ask. Therefore you can't ask what answer a false oracle would give to a purely hypothetical question, since the answer is undefined. Nor can you ask what answer an oracle (true or false) will give, to a future question, because you might then choose not to ask that question to that oracle.

You might be thinking that you can get more than one bit of information per question, by asking things for which possible responses are "yes", "no", and "question not allowed". The solution I have in mind, doesn't use such questions. Nevertheless, I will allow them, with the proviso that if you use them, then I want a solution which requires substantially fewer than 2n-1 questions. Also questions which result in a "question not allowed" response count against your running total.

Quote:
why you need n questions? the minimum number should be much smaller, if I can ask ANY question]
It may be possible to do it in less than 2n-1 yes/not questions, though I don't know how. I can't see how it could be possible to do it in less than n questions. If you think you can, then let's see your solution.

Quote:
Originally Posted by LaurV View Post
Most probably not, otherwise there is no deterministic solution, one liar can chose to answer correctly to a number of your questions, so there can only be a "probabilistic" solution.
Incorrect. There is a deterministic solution using no more than 2n-1 questions. Note that the problem does not require you to get a question answered by a true oracle. It doesn't even require you to know, at the end of the process, the correct answer to any of the questions you asked. All that is required at the end of the process is that you know the identity of at least one true oracle. If you wish to find out if your war ally is planning to betray you, you can ask that as your 2nth question.

Quote:
A liar should ALWAYS tell lies.
Indeed, but I did not say that the false oracles were liars. I'm familiar with the kind of problem where the solution is to construct a question that a truth-teller and a liar will answer the same way. This is not that kind of problem. In this problem, the false oracles may give either answer to any question. Your task is to figure out a way to deal with this.

Quote:
Also (see my little joke above) there should be clear specified what kind of questions I can ask, and what "different" means. I can ask first n oracles questions like, for oracle k, the question is "is k prime?", they are technically different, as the k is different, and if I only get wrong answers, then I can pick one oracle from the remaining n+1.
You can certainly do this. However, what do you do if all n oracles give the right answer?

Quote:
If the questions are considered not to be different, I can ask any other question to which I know the answer (in all those cases, the puzzle is trivial).
The questions are not required to be different. However, if you ask the same question to two different oracles (or the same question twice to the same oracle) then that counts as two questions.

Quote:
Originally Posted by Jayder View Post
May I let n=0?
Good question. if n=0 then you have only one oracle which you know without asking any questions at all is a true oracle (because it is stipulated that no more than n oracles are false). Clearly the requirement that you ask no more than 2n-1 questions makes no sense in this case. Therefore assume that n is a positive integer.

Last fiddled with by Mr. P-1 on 2013-02-13 at 16:02
Mr. P-1 is offline   Reply With Quote
Old 2013-02-13, 16:05   #9
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

8,963 Posts
Default

Ok, now the things are more clear.
For example, for n=1, you have 3 oracles, from which two are good, one is bad. You may ask a single question, and you get the right answer. How do you figure from here if you asked a good oracle or a false one who deliberately told you the truth... well this is a mystery for me now. Either the problem has no solution, as I said, or in case you are right and there is a solution, it means that I did not figured yet the right question to ask. If I solve this, I believe the general case is a piece of cake.

Don't post the answer yet, I am still thinking overnight
LaurV is offline   Reply With Quote
Old 2013-02-13, 16:19   #10
Zeta-Flux
 
Zeta-Flux's Avatar
 
May 2003

110000010112 Posts
Default

My friend came up with a similar puzzle involving three people who speak three different languages (whose yes's and no's happen to be "dak" and "spek", but not necessarily respectively). One is a truth teller, one always lies, and one is random. etc...

In the n=1 case, you ask oracle 1 the question: Is oracle 2 a true oracle? If the answer is no, oracle 3 is always a true oracle. If the answer is yes, oracle 2 is always a true oracle.

I haven't worked out the general case.
Zeta-Flux is offline   Reply With Quote
Old 2013-02-13, 16:35   #11
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3×29×83 Posts
Default

*snirk* This was posted today.
Dubslow is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
April Fools Day stories, true and false cheesehead Lounge 15 2017-04-04 01:26
x^2 = 2 , is it true? Ale Miscellaneous Math 13 2016-01-03 13:55
true or false science_man_88 Science & Technology 20 2011-05-11 20:48
True ignore lists? xilman Forum Feedback 1 2006-04-23 18:14
too good to be true? ixfd64 mersennewiki 5 2006-01-02 08:21

All times are UTC. The time now is 12:39.

Sat Dec 5 12:39:26 UTC 2020 up 2 days, 8:50, 0 users, load averages: 1.75, 1.57, 1.51

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.