Иногда задачи из старых олимпиад по математике неожиданно снова начинают гулять по интернету. Они кажутся нерешаемыми, но мы так не считаем: давайте справимся с этой головоломкой вместе.
Кажется, что на решение такой задачи потребуются десятки попыток. Но математики утверждают: если задавать правильные вопросы, хватит всего десяти. Как такое возможно? Попробуйте разобраться, но запаситесь терпением: это непростая задача.
Друг задумал некоторое целое число от 1 до 1000. Ваша задача — угадать его, задавая вопросы. Но есть одно строгое правило: на каждый вопрос ваш друг может отвечать только «да» или «нет».
Эта задача не столько про угадывание, сколько про стратегию поиска. Каждый вопрос должен максимально сокращать количество возможных вариантов. Если действовать правильно, после каждого ответа число возможных вариантов уменьшается примерно вдвое. Вот какой путь решения мы предлагаем.
Всего 10 вопросов достаточно, чтобы гарантированно угадать любое целое число от 1 до 1000. Это классическая задача на бинарный поиск, где каждый вопрос делит возможный диапазон пополам. Используйте вопросы типа: «Задуманное число не больше X?», где X — середина текущего интервала. Начните с диапазона [1; 1000].
Если ответ «да», новый диапазон — [низ; X].
Если «нет», новый диапазон — [X+1; высок].
То есть каждый вопрос исключает примерно половину возможных вариантов. После 10 вопросов диапазон сведется к одному числу.
Вот точная последовательность вопросов для любого исхода (адаптируйте X по ответам):
Не больше 500?
Не больше 250? (или 750, если предыдущий ответ «нет»)
Не больше 125? (или 375/625/875 по ситуации)
Не больше 62? (и так далее, пересчитывая середину)
Не больше 31?
Не больше 15?
Не больше 7?
Не больше 3?
Не больше 1?
Равно 1? (или финальное уточнение).
Давайте используем стратегию вопросов типа «Задуманное число не больше X?», деля диапазон пополам на каждом шаге.
Начальный диапазон: 1–1000.Вопрос: «Число не больше 500?»Ответ: Да → новый диапазон: 1–500
Диапазон: 1–500Вопрос: «Число не больше 250?»Ответ: Да → новый диапазон: 1–250
Диапазон: 1–250Вопрос: «Число не больше 125?»Ответ: Да → новый диапазон: 1–125
Диапазон: 1–125Вопрос: «Число не больше 62?»Ответ: Нет → новый диапазон: 63–125
Диапазон: 63–125Вопрос: «Число не больше 93?»Ответ: Да → новый диапазон: 63–93
Диапазон: 63–93Вопрос: «Число не больше 77?»Ответ: Нет → новый диапазон: 78–93
Диапазон: 78–93Вопрос: «Число не больше 85?»Ответ: Нет → новый диапазон: 86–93
Диапазон: 86–93Вопрос: «Число не больше 89?»Ответ: Нет → новый диапазон: 90–93
Диапазон: 90–93Вопрос: «Число не больше 91?»Ответ: Нет → новый диапазон: 92–93
Диапазон: 92–93Вопрос: «Число не больше 92?»Ответ: Да → задуманное число: 92
Итог:После 10 вопросов диапазон сужается до одного числа, и мы точно угадываем задуманное число. Так бинарный поиск гарантирует успех за минимальное количество шагов.
