Guess a Number—with Lying
Joel Spencer · Mathematics Magazine · 1984
Someone thinks of a number between one and one million (which is just less than 220). Another person is allowed to ask up to twenty questions, to each of which the first person is supposed to answer only yes or no. Obviously the number can be guessed by asking first: Is the number in the first half-million? and then again reduce the reservoir of numbers in the next question by one-half, and so on. Finally the number is obtained in less than log2(1000000). Now suppose one were allowed to lie once or twice, then how man)' questions would onie need to get the right answer?