A number is guessed from 1 to 144. You are allowed to select one subset of the set of numbers from 1 to 144 and ask whether the guessed number belongs to it. For an answer of "yes," you have to pay 2 rubles, and for an answer of "no" - 1 ruble. What is the smallest amount of money needed to surely guess the number?

#
Let $a_{1}=2, a_{2}=3, a_{i}=a_{i-1}+a_{i-2}$ for $i \geq 2$. Then $a_{10}=144$. We will prove by induction that among no fewer than $a_{i}$ numbers, the guessed number cannot be found by paying less than $i+1$ rubles.

For $i=1$ and $i=2$, this is true.

Suppose there are no fewer than $a_{i}$ numbers. Then either the set $M$ of numbers highlighted in the first question contains no fewer than $a_{i-2}$ numbers (first case), or the set of numbers not in $M$ contains no fewer than $a_{i-1}$ numbers (second case). In the first case, if the guessed number is in $M$, then 2 rubles need to be paid for the answer, and by the induction hypothesis, at least $(i-2)+1$ rubles are needed to guess the number, i.e., a total of at least $i+1$ rubles.

In the second case, if the guessed number is not in $M$, then 1 ruble needs to be paid for the answer and at least $(i-1)+1$ rubles for guessing the number, i.e., again a total of at least $i+1$ rubles.

The algorithm for guessing the number is clear from the previous reasoning: at each step, the set $M$ of $a_{i}$ numbers containing the guessed number should be divided into sets $M_{1}$ of $a_{i-2}$ numbers and $M_{2}$ of $a_{i-1}$ numbers, and ask whether the number belongs to the set $M_{1}$.

## Answer

11 rubles.