20130213, 08:06  #1 
Jun 2003
10010010001_{2} Posts 
True and false oracles.
There are 2n+1 oracles. Most of them are genuine. These give a true yesorno 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. 
20130213, 08:18  #2 
Jun 2003
4790_{10} Posts 

20130213, 09:31  #3  
Romulan Interpreter
Jun 2011
Thailand
8,963 Posts 
Quote:
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 k1 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 20130213 at 09:39 Reason: s/is/if 

20130213, 10:08  #4 
Romulan Interpreter
Jun 2011
Thailand
8,963 Posts 
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 20130213 at 10:17 
20130213, 10:39  #5  
Jun 2003
2×5×479 Posts 
Quote:
Quote:


20130213, 10:57  #6 
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 welldefined question with a definite answer, or will heads explode?!
Last fiddled with by axn on 20130213 at 10:58 
20130213, 11:13  #7 
Dec 2012
2·139 Posts 
May I let n=0?

20130213, 15:50  #8  
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 2n1 questions. My apologies.
Quote:
Quote:
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 2n1 questions. Also questions which result in a "question not allowed" response count against your running total. Quote:
Quote:
Quote:
Quote:
Quote:
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 2n1 questions makes no sense in this case. Therefore assume that n is a positive integer. Last fiddled with by Mr. P1 on 20130213 at 16:02 

20130213, 16:05  #9 
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 
20130213, 16:19  #10 
May 2003
11000001011_{2} 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. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
April Fools Day stories, true and false  cheesehead  Lounge  15  20170404 01:26 
x^2 = 2 , is it true?  Ale  Miscellaneous Math  13  20160103 13:55 
true or false  science_man_88  Science & Technology  20  20110511 20:48 
True ignore lists?  xilman  Forum Feedback  1  20060423 18:14 
too good to be true?  ixfd64  mersennewiki  5  20060102 08:21 