ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 98524
Темы:    [ Теория игр (прочее) ]
[ Таблицы и турниры (прочее) ]
[ Замощения костями домино и плитками ]
[ Десятичная система счисления ]
[ Доказательство от противного ]
Сложность: 4
Классы: 10,11
В корзину
Прислать комментарий

Условие

Автор: Фольклор

Лёша задумал двузначное число (от 10 до 99). Гриша пытается его отгадать, называя двузначные числа. Если Гриша правильно называет число, или же одну цифру называет правильно, а в другой ошибается не более чем на единицу, то Лёша отвечает "тепло"; в остальных случаях Лёша отвечает "холодно". (Например, если задумано число 65, то назвав 65, 64, 66, 55 или 75, Гриша услышит в ответ "тепло", а в остальных случаях услышит "холодно".)
  а) Покажите, что нет способа, при котором Гриша гарантированно узнает число, истратив 18 попыток.
  б) Придумайте способ, при котором Гриша гарантированно узнает число, истратив 24 попытки (какое бы число ни задумал Лёша).
  в) А за 22 попытки получится?


Решение

  в) Запишем двузначные числа в таблицу 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.  Противоречие.


Ответ

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

Замечания

баллы: 2 + 3 + 3

Источники и прецеденты использования

олимпиада
Название Турнир городов
Турнир
Дата 2000/2001
Номер 22
вариант
Вариант весенний тур, основной вариант, 8-9 класс
Задача
Номер 7

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .