Minimum number of questions for finding the right number in a guessing game I'm working on the following exercise:
Alice and Bob play the following game: Alice thinks of a number between $1$ and $1 \ 000 \ 000$. Bob can ask Alice questions to find said number and Alice answers them truthfully, but is allowed to lie at most once.
What is the minimum number of questions Bob has to ask Alice? Describe the method that Bob can use. Does your method work if Alice did not lie? What happens if Alice changes the number during the game?
My first idea was that Bob could use the BINARY-SEARCH procedure to find the number. Furthermore he could ask every question three times in a row to see if Alice lies or not. But I'm not sure if this procedure requires the lowest amount of questions. Am I on the right track with this exercise?
 A: This is not an answer in the sense that it gives an optimal method an proves it. It is just a better method than presented by the OP.
If you have a set $X$ to which your unknown number belongs, you can partition it into 3 almost equal parts $X_1,X_2$ and $X_3$, then ask 3 questions: 


*

*Does the number belong to $X_1 \cup X_2$? 

*Does the number belong to $X_1 \cup X_3$?

*Does the number belong to $X_2 \cup X_3$?


If all answers are thruthfull, you get 2 'yes' and one 'no' and can conclude to which of $X_i$ the set belongs, and continue. If the lie was on the question that should have been 'no', you get 3 'yes', no further info, but know that the lie has been 'used up' and continue with a binary search for $X$. If the lie was on a question that should have been a 'yes', you get 1 'yes' and 2 'no', so you know that the 'yes' answer was correct, so can conclude to wich $\frac23$ of $X$ the number belongs, and can again continue with a binary search.
This method reduces the possible space to wich the unknown number belongs by a factor of 3 for every 3 questions that are answered truthfully, until the lie happens, which will be a round that in the worst case gives no further info, but then can be followed by optimal binary search.
This is better than the originally proposed scheme wich creates a reduction by a factor of 2 for every 3 questions.
Note that the originally proposed scheme can be made better by just asking each binary reduction questions twice. If one gets the same answer, one knows it is the truth and can continue without a third question. Only if the answers differ one needs a third question, which must then be truthfully answered. This scheme produces a reduction by a factor of 2 for every 2 questions until the lie is discovered.
My scheme gives 'on average' for each question a reduction by $\sqrt[3]{3} \approx 1.44...$ while the improved original scheme gives a reduction by $\sqrt{2} \approx 1.41...$
I assume however that an optimal algorithm will take longer stretches of uncertainty if the lie has already occured. 
