|
|
 |
Условие
Лёша задумал двузначное число (от 10 до 99). Гриша пытается его отгадать,
называя двузначные числа. Если Гриша правильно называет число, или же одну
цифру называет правильно, а в другой ошибается не более чем на единицу,
то Лёша отвечает "тепло"; в остальных случаях Лёша отвечает "холодно".
(Например, если задумано число 65, то назвав 65, 64, 66, 55 или 75, Гриша
услышит в ответ "тепло", а в остальных случаях услышит "холодно".)
а) Покажите, что нет способа, при котором Гриша гарантированно узнает число, истратив 18 попыток.
б) Придумайте способ, при котором Гриша гарантированно узнает число, истратив 24 попытки (какое бы число ни задумал Лёша).
в) А за 22 попытки получится?
Решение
в) Запишем двузначные числа в таблицу 9·10 так, что первая цифра – номер строки, а вторая – номер столбца (см. рис.).
Пусть Гриша услышал ответ "тепло" первый раз на n-м вопросе. Если n ≤ 19, то еще за три (или два) вопроса мы точно узнаем число; если n = 20, то мы узнаем число еще за два вопроса; при n = 21 – за один вопрос, a при n = 22 это число 13. Если же на все вопросы Лёша ответил "холодно", то задуманное число – 30.
а) Так как один вопрос – это один крест, достаточно доказать, что любые 18 крестов оставят в таблице минимум две непокрытые клетки. Действительно, тогда, получив на 18 вопросов ответ "холодно", Гриша не сможет определить, какая из непокрытых клеток загадана.
Допустим, что осталось максимум одна непокрытая клетка. Тогда из четырёх угловых клеток покрыты, по крайней мере, три. Но угловая клетка может быть покрыта только "неполноценным" крестом. Следовательно, общее число покрытых клеток не превосходит 5·18 – 3 = 87. Противоречие.
Ответ
в) Получится.
Замечания
1. Можно доказать, что даже 19 вопросов недостаточно.
2. Баллы: 2 + 3 + 3.
