Задача 102997

Темы:    [ Теория алгоритмов ] [ Двоичная система счисления ]

Сложность: 3- Классы: 5,6,7

Условие

Миша загадал число не меньше 1 и не больше 1000. Васе разрешено задавать только такие вопросы, на которые Миша может ответить «да» или «нет» (Миша всегда говорит правду). Может ли Вася за 10 вопросов определить загаданное число?

Подсказка

Как ни странно, у этой задачи есть нечто общее с задачей 102982.

Решение

Вася сначала спросит, больше ли число, чем 500. Затем, больше ли 730 или меньше ли 250, в зависимости от ответа Миши на 1-й вопрос, и т.д. (каждый раз расстояние от числа в старом вопросе до числа в новом вопросе уменьшается в два раза. Пример. Пусть Миша загадал число 183. Вопросы Васи: 1) >500? 2) <250? 3) <125? 4) > 187? 5) <155? 6) >171? 7) >179? 8) >183? 9) <181? 9) >182? Ответ: 183.

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

кружок
Место проведения	МЦНМО
класс
Класс	5
год
Год	2004/2005
занятие
Номер	9
задача
Номер	9.9