mersenneforum.org True and false oracles.
 Register FAQ Search Today's Posts Mark Forums Read

 2013-02-13, 08:06 #1 Mr. P-1     Jun 2003 100100100012 Posts 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.
2013-02-13, 08:18   #2
axn

Jun 2003

479010 Posts

Quote:
 Originally Posted by Mr. P-1 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?

2013-02-13, 09:31   #3
LaurV
Romulan Interpreter

Jun 2011
Thailand

8,963 Posts

Quote:
 Originally Posted by Mr. P-1 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

2013-02-13, 10:08   #4
LaurV
Romulan Interpreter

Jun 2011
Thailand

8,963 Posts

Quote:
 Originally Posted by axn 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

2013-02-13, 10:39   #5
axn

Jun 2003

2×5×479 Posts

Quote:
 Originally Posted by LaurV 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 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?

 2013-02-13, 10:57 #6 axn     Jun 2003 2×5×479 Posts 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
 2013-02-13, 11:13 #7 Jayder     Dec 2012 2·139 Posts May I let n=0?
2013-02-13, 15:50   #8
Mr. P-1

Jun 2003

7×167 Posts

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 Clarification required: Does this mean a false oracle can answer correctly to a question?
Yes.

Quote:
 Originally Posted by LaurV "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 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 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 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

 2013-02-13, 16:05 #9 LaurV Romulan Interpreter     Jun 2011 Thailand 8,963 Posts 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
 2013-02-13, 16:19 #10 Zeta-Flux     May 2003 110000010112 Posts 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.
 2013-02-13, 16:35 #11 Dubslow Basketry That Evening!     "Bunslow the Bold" Jun 2011 40

 Similar Threads Thread Thread Starter Forum Replies Last Post cheesehead Lounge 15 2017-04-04 01:26 Ale Miscellaneous Math 13 2016-01-03 13:55 science_man_88 Science & Technology 20 2011-05-11 20:48 xilman Forum Feedback 1 2006-04-23 18:14 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