Knight or Knave (Inspired by Pi Han Goh)
I am thinking of an integer between 1 and 10000 inclusive, and you know I either always tell the truth or always lie. You are allowed to ask questions in the form "Is the number in the set X ?" for any set X of integers. How many questions are needed to determine the number?
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
2 solutions
A strategy to guarantee finding the number in 14 questions does not exist:
Each possible situation I could choose (a number and whether I lie or tell truth) can be represented by a pair ( n , t ) where 1 ≤ n ≤ 1 0 0 0 0 and t ∈ { T R U E , F A L S E }
Note that if you find n after asking some number of questions, you will also figure out t , based on any one of my answers and the value of n .
Each question you ask splits the space of possible situations into two disjoint parts (one of them is still allowed if the answer is YES, the other of them if the answer is NO). Hence one of the answers (YES or NO) will still keep at least half of the possible situations consistent with all the previous questions.
As there are 20,000 legal situations to start with, after 14 questions there will be 2 1 4 = 1 6 3 8 4 possible ordered lists of answers. Some of them will correspond to more than one situation (and see above why they can't correspond to a single value of n , just different t s). Hence a strategy guaranteeing the answer in 14 questions cannot exist.
For a second there I was really confused. "I didn't write this solution, did something in the site glitch?"
For some reason I think it is none of the above. First would be is it in the set of 1-10000 then just halves. Right?
Based on the possible answers and the fact the question is posted als a logic problem I figured the desired number is a binary number, so the stated binary upper bound 10000 equals 2 4 = 1 6 as a decimal number.
Each subsequent question ask: "Is the number x ?" with x ∈ { 1 , 2 , 3 , . . . , 1 5 } .
If you are unlucky at guessing and all of 15 questions are answered either all with "yes" or all with "no" then no other question is necessary because the correct number is the final and 16th one.
If you are lucky and quess the correct number with your 1st attempt, you cannot know this yet, and you need two more attempts. A "Yes-No-No" reveals you are a truthteller and a "No-Yes-Yes" reveals you are a liar. In both cases the first stated number is the correct one.
Therefore at least 3 and at most 15 questions are required.
How you know that the real number is 16 , it may be 18 etc.. , Can you please elaborate more how the binary upper bound is helpful in this case
Log in to reply
In response to Syed Baqir.
Alex Li states his problem: "I am thinking of an integer between 1 and 10000 inclusive."
First of all we're trying to figure out an integer number, not a real number as you wrote.
Secondly, I figured that Alex meant binary numbers instead of decimal Numbers when he wrote: "... 1 and 10000...".
Now, the stated lower binary bound 1 equals 2 0 = 1 in it's decimal representation.
And the stated upper binary bound 10000 equals 1 ⋅ 2 4 + 0 ⋅ 2 3 + 0 ⋅ 2 2 + 0 ⋅ 2 1 + 0 ⋅ 2 0 = 1 6
So with 16 possible integer numbers to choose from, we need at most 15 questions under the given restrictions.
Hope this helped more!
Your first question can be "Is the number 0 ?" This answer will tell you whether I lie or tell the truth. Then, based on that, you can determine the number in 1 4 more questions by asking "Is the number greater than x ?", because 2 1 3 < 1 0 0 0 0 < 2 1 4 , so it takes 1 5 questions in total. (I am pretty confident but not 100% certain that there is no way to find the number in 1 4 questions. If you find a way, by all means let me know!)