$\left[\begin{array}{l}\text { Theory of algorithms (other) }) \\ {[\underline{\text { Estimation + example }}]}\end{array}\right.$

You need to find out a five-digit phone number by asking questions that can be answered with "yes" or "no." What is the minimum number of questions required to guarantee finding the number (assuming that the answers to the questions are correct)?
We need to ask questions in such a way that each subsequent question approximately halves the number of remaining possible options.

## Solution

Initially, when we know nothing about the phone number, there are $10^{5}=100000$ possible options for the phone number. We ask the question: "Is the number greater than 50000?". Regardless of the answer, we reduce the number of remaining possible options by half. Thus, after the first question, no more than 50000 possible options remain for the phone number. If the answer to the first question is "yes," we ask: "Is the number greater than 75000?". After the answer to this question, no more than 25000 options remain. And so on - if after the n-th question, k possible options remain, we can ask the (n+1)-th question in such a way that after the answer, no more than [k/2]+1 possible options remain. Thus, we get the following dependence of the number of remaining possible options on the number of questions asked: After the first question - 50000 options, after the 2nd - 25000, 3rd - 12500, 4th - 6250, 5th - 3125, 6th - 1563, 7th - 782, 8th - 391, 9th - 196, 10th - 98, 11th - 59, 12th - 30, 13th - 15, 14th - 8, 15th - 4, 16th - 2, 17th - 1. Thus, after 17 questions, only one option remains, i.e., the phone number can be guessed. On the other hand, it is impossible to guess the number in 16 questions. Indeed, after 16 questions, there are $2^{16}<100000$ sequences of answers to the questions. Therefore, at least two phone number options will correspond to some sequence of answers. Thus, if the desired number is any of these two numbers, the sequences of answers to the questions will be the same, i.e., it will not be possible to determine the number uniquely.

## Answer

17 questions.