4. Talented boy Petya Tort has thought of a natural number from 1 to 1000. You can ask him questions of the form “Does your number belong to the set $X$?”. He will definitely answer correctly to the first question; but at some point, his mood might worsen, and he will start lying. His mood will not improve once it has worsened. What is the minimum number of questions needed to guarantee finding the guessed number?
Solution. We will prove that no less than 14 questions are required. Suppose we have some algorithm that requires $n$ questions. If in some cases fewer questions are needed, we will ask the last question several more times to ensure that exactly $n$ questions are always asked. Then, as a result of the algorithm's operation, we will learn the guessed number, and thus the correct answers to all questions, and thus the moment when the mood spoiled. Thus, we have $1000 n$ different "outcomes": 1000 possible numbers and the mood could have spoiled after any of the $n$ questions. Each outcome must correspond to its own set of answers to the questions, of which there are $2^{n}$ in this case. Therefore, the inequality $2^{n} \geqslant 1000 n$ must hold. For $n<10$, the left side is simply less than 1000, and the first number for which the inequality holds is $n=14$.

We will show how to determine the number in 14 questions. In the binary representation of numbers from 1 to 1000, there are no more than 10 digits. Let $Q_{i}$ be the question "Is the $i$-th digit from the end in the guessed number a one?" To uniquely identify the number, we need to know the true answers to the questions $Q_{1}, \ldots, Q_{10}$.

We will ask the questions $Q_{1}, Q_{2}, Q_{3}, Q_{4}, Q_{5}, Q_{6}, Q_{1}$. If the answers to $Q_{1}$ are different, then the mood has already spoiled. We will ask the question $Q_{4}$ again. This way, we will learn a definitely false answer to it (and by inverting, we will learn the correct one) and we will learn whether the mood spoiled before $Q_{4}$ or after. If before, we need to ask the questions $Q_{2}$ and $Q_{3}$ again, and the answers to $Q_{5}$ and $Q_{6}$ are already known to us, as Petya was lying when answering them. If after, then, on the contrary, we need to ask $Q_{5}$ and $Q_{6}$ again, and the answers to $Q_{2}$ and $Q_{3}$ were true. Thus, we have already asked 10 questions. Now we will ask $Q_{7}, Q_{8}, Q_{9}, Q_{10}$ - Petya will definitely lie, and thus we will learn the correct answers to them.

If the answers to $Q_{1}$ were the same, then the mood has not yet spoiled, that is, we know the correct answers to the questions $Q_{1}-Q_{6}$. We will ask the questions $Q_{7}, Q_{8}, Q_{9}, Q_{1}$. If the answer to $Q_{1}$ has changed, then the mood has already spoiled. We will ask the question $Q_{8}$ again. This way, we will learn a definitely false answer to it (and by inverting, we will learn the correct one) and we will learn whether the mood spoiled before $Q_{8}$ or after. If before, it is enough to ask $Q_{7}$ again. If after, it is enough to ask $Q_{9}$ again. We have already asked 13 questions, now we will ask $Q_{10}$ - we will get a definitely false answer, which is sufficient for us.

If the answers to $Q_{1}$ are the same again, then the mood has not yet spoiled, that is, we know the answers to $Q_{1}-Q_{9}$. We will ask the questions $Q_{10}, Q_{1}, Q_{10}$. If the answer to $Q_{1}$ is still the same, then the first answer to $Q_{10}$ is true, and if the answer to $Q_{1}$ is different, then the second answer to $Q_{10}$ is definitely false.

Answer. 14.