Иногда задачи из старых олимпиад по математике неожиданно снова начинают гулять по интернету. Они кажутся нерешаемыми, но мы так не считаем: давайте справимся с этой головоломкой вместе.
Кажется, что на решение такой задачи потребуются десятки попыток. Но математики утверждают: если задавать правильные вопросы, хватит всего десяти. Как такое возможно? Попробуйте разобраться, но запаситесь терпением: это непростая задача.
Условие
Друг задумал некоторое целое число от 1 до 1000. Ваша задача — угадать его, задавая вопросы. Но есть одно строгое правило: на каждый вопрос ваш друг может отвечать только «да» или «нет».
Эта задача не столько про угадывание, сколько про стратегию поиска. Каждый вопрос должен максимально сокращать количество возможных вариантов. Если действовать правильно, после каждого ответа число возможных вариантов уменьшается примерно вдвое. Вот какой путь решения мы предлагаем.
Принцип решения
Всего 10 вопросов достаточно, чтобы гарантированно угадать любое целое число от 1 до 1000. Это классическая задача на бинарный поиск, где каждый вопрос делит возможный диапазон пополам. Используйте вопросы типа: «Задуманное число не больше X?», где X — середина текущего интервала. Начните с диапазона [1; 1000].
Если ответ «да», новый диапазон — [низ; X].
Если «нет», новый диапазон — [X+1; высок].
То есть каждый вопрос исключает примерно половину возможных вариантов. После 10 вопросов диапазон сведется к одному числу.
Пошаговый алгоритм
Вот точная последовательность вопросов для любого исхода (адаптируйте X по ответам):
Источник: hi-tech.mail.ru