$:$ Folklore

Lёsha thought of a two-digit number (from 10 to 99). Grisha tries to guess it by naming two-digit numbers. If Grisha correctly names the number, or one digit is correct and the other is off by no more than one, Lёsha responds with "warm"; in all other cases, Lёsha responds with "cold". (For example, if the number 65 is thought of, then by naming 65, 64, 66, 55, or 75, Grisha will hear "warm," and in all other cases, "cold.")

a) Show that there is no way for Grisha to guarantee finding the number using 18 attempts.

b) Come up with a way for Grisha to guarantee finding the number using 24 attempts (regardless of which number Lёsha thinks of).

c) Can it be done in 22 attempts?
b) Let's write two-digit numbers in a $9 \cdot 10$ table such that the first digit is the row number and the second digit is the column number (see figure).

|  | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: |
| 1 | 20 |  |  | 22 |  | 12 |  |  |  | 21 |
| 2 |  |  | 1 |  |  |  |  | 11 |  |  |
| 3 | 23 |  |  |  | 2 |  |  |  |  | 13 |
| 4 |  | 8 |  |  |  |  | 3 |  |  |  |
| 5 |  |  |  | 7 |  |  |  |  | 4 |  |
| 6 | 19 |  |  |  |  | 6 |  |  |  |  |
| 7 |  |  | 9 |  |  |  |  | 5 |  | 16 |
| 8 | 15 |  |  |  | 10 |  |  |  |  |  |
| 9 |  |  | 18 |  |  |  | 14 |  | 17 |  |

Grisha must sequentially call out the numbers marked in the table (number 1 marks the number 22, number 2 marks 34, etc.) until he hears the response "warm." Note that if the question "34" receives a "cold" response from Lesh, we know for sure that the desired number is not in the cross centered at 34 (see cross #2 in the figure). Therefore, if Lesh answers "cold" to the first 15 questions and "warm" to the 16th, Grisha will know for sure that the guessed number is one of 79, 69, 89 (78 cannot be, as the 5th step question "77" received a "cold" response). This explains the origin of the "imperfect" crosses in the figure. Suppose now that on a certain step, we hear the response "warm." Then we know in which exact cross the guessed number is. For example, if this happens on the 5th step, we can guess the number in three more questions ("76", "67", "78"). If the number falls into an "imperfect" cross, we will manage with fewer questions.

Suppose Grisha hears the response "warm" for the first time on the $n$-th question. If $n \leq 19$, we can determine the number in three (or two) more questions; if $n=20$, we can determine the number in two more questions; if $n=21$, in one more question; and if $n=22$, the number is 13. If Lesh answers "cold" to all questions, the guessed number is 30.

a) Since one question is one cross, it is sufficient to prove that any 18 crosses will leave at least two uncovered cells in the table. Indeed, then, after receiving "cold" responses to 18 questions, Grisha will not be able to determine which of the uncovered cells is guessed.

Suppose that at most one uncovered cell remains. Then, out of the four corner cells, at least three are covered. But a corner cell can only be covered by an "imperfect" cross. Therefore, the total number of covered cells does not exceed $5 \cdot 18 - 3 = 87$. Contradiction.

## Answer

b) It will work.