The best lie ever
I am thinking of an integer between 1 and 2015 (inclusive). You are required to guess the integer, by asking yes/no questions about the properties.
If I'm only allowed to lie exactly once, what is the minimum number of yes/no questions you need to ask, in order to guarantee that you can find my integer?
Details and Assumptions :
-
As an explicit example, suppose the integer I'm thinking of is 2015. Then you can determine my number in 4030 questions by asking whether my number is 1, 1, 2, 2, 3, 3, ... , 2015, 2015 in that order. And I will only lie on the second last question.
-
You are not allowed to ask questions that don't directly relate to the number. E.g "what other people think of this number."
The answer is 15.
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.
1 solution
I'll have you convert the number to Hamming(15,11) code and ask you 15 yes/no questions to get each bit. That way, we reduce 2015 possibilities to 11 bits of information + 4 parity bits to detect and correct any single bit error.
I also thought that if we are allowed to ask like below to remove the effect of the lie... "If I ask you whether the first bit is 1, would you say yes?" then, we can essentially know the number in only 11 questions.