Олимпиадная задача с Лёшей и Гришей: сколько попыток нужно для угадывания числа?

  в) Запишем двузначные числа в таблицу 9·10 так, что первая цифра – номер строки, а вторая – номер столбца (см. рис.).

  Гриша должен последовательно называть числа, отмеченные в таблице номерами (номером 1 отмечено число 22, номером 2 – 34 и т.д.) до тех пор, пока не услышит ответ "тепло". Заметим, что если на вопрос "34" Лёша ответит "холодно", то мы точно знаем, что искомого числа нет в кресте с центром 34 (на рис. крест № 2). Поэтому, если на первые 15 вопросов Леша ответит "холодно", а на 16-й – "тепло", то Гриша будет точно знать, что загадано одно из чисел 79, 69, 89 (78 не может быть, так как на 5-м шаге на вопрос "77" был ответ "холодно"). Это объясняет происхождение "неполноценных" крестов на рисунке. Допустим теперь, что на очередном шаге мы услышали ответ "тепло". Тогда мы знаем, в каком именно кресте находится загаданное число. Если, например, это случилось на 5-м шаге, то мы сможем угадать его за три вопроса ("76", "67", "78"). Если же наше число попало в "неполноценный" крест, то мы обойдемся меньшим числом вопросов.   Пусть Гриша услышал ответ "тепло" первый раз наn-м вопросе. Если  n≤ 19,  то еще за три (или два) вопроса мы точно узнаем число; если  n= 20,  то мы узнаем число еще за два вопроса; при  n= 21  – за один вопрос, a при  n= 22  это число 13. Если же на все вопросы Лёша ответил "холодно", то задуманное число – 30.   а) Так как один вопрос – это один крест, достаточно доказать, что любые 18 крестов оставят в таблице минимум две непокрытые клетки. Действительно, тогда, получив на 18 вопросов ответ "холодно", Гриша не сможет определить, какая из непокрытых клеток загадана.

  Допустим, что осталось максимум одна непокрытая клетка. Тогда из четырёх угловых клеток покрыты, по крайней мере, три. Но угловая клетка может быть покрыта только "неполноценным" крестом. Следовательно, общее число покрытых клеток не превосходит  5·18 – 3 = 87.  Противоречие.

в) Получится.