В сети обсуждают старую олимпиадную задачу: можно ли угадать число всего за 10 вопросов?

Иногда задачи из старых олимпиад по математике неожиданно снова начинают гулять по интернету. Они кажутся нерешаемыми, но мы так не считаем: давайте справимся с этой головоломкой вместе.

Мария ЛогиноваАвтор Hi-Tech Mail

Кажется, что на решение такой задачи потребуются десятки попыток. Но математики утверждают: если задавать правильные вопросы, хватит всего десяти. Как такое возможно? Попробуйте разобраться, но запаситесь терпением: это непростая задача. 

Условие

Друг задумал некоторое целое число от 1 до 1000. Ваша задача — угадать его, задавая вопросы. Но есть одно строгое правило: на каждый вопрос ваш друг может отвечать только «да» или «нет».

Эта задача не столько про угадывание, сколько про стратегию поиска. Каждый вопрос должен максимально сокращать количество возможных вариантов. Если действовать правильно, после каждого ответа число возможных вариантов уменьшается примерно вдвое. Вот какой путь решения мы предлагаем.

 Принцип решения

Всего 10 вопросов достаточно, чтобы гарантированно угадать любое целое число от 1 до 1000. Это классическая задача на бинарный поиск, где каждый вопрос делит возможный диапазон пополам. Используйте вопросы типа: «Задуманное число не больше X?», где X — середина текущего интервала. Начните с диапазона [1; 1000].

• Если ответ «да», новый диапазон — [низ; X].

• Если «нет», новый диапазон — [X+1; высок].

То есть каждый вопрос исключает примерно половину возможных вариантов. После 10 вопросов диапазон сведется к одному числу.

Пошаговый алгоритм

Вот точная последовательность вопросов для любого исхода (адаптируйте X по ответам):

1. Не больше 500?

2. Не больше 250? (или 750, если предыдущий ответ «нет»)

3. Не больше 125? (или 375/625/875 по ситуации)

4. Не больше 62? (и так далее, пересчитывая середину)

5. Не больше 31?

6. Не больше 15?

7. Не больше 7?

8. Не больше 3?

9. Не больше 1?

10. Равно 1? (или финальное уточнение). 

Попробуем угадать число 92 с помощью бинарного поиска

Давайте используем стратегию вопросов типа «Задуманное число не больше X?», деля диапазон пополам на каждом шаге.

1. Начальный диапазон: 1–1000.
   Вопрос: «Число не больше 500?»
   Ответ: Да → новый диапазон: 1–500

2. Диапазон: 1–500
   Вопрос: «Число не больше 250?»
   Ответ: Да → новый диапазон: 1–250

3. Диапазон: 1–250
   Вопрос: «Число не больше 125?»
   Ответ: Да → новый диапазон: 1–125

4. Диапазон: 1–125
   Вопрос: «Число не больше 62?»
   Ответ: Нет → новый диапазон: 63–125

5. Диапазон: 63–125
   Вопрос: «Число не больше 93?»
   Ответ: Да → новый диапазон: 63–93

6. Диапазон: 63–93
   Вопрос: «Число не больше 77?»
   Ответ: Нет → новый диапазон: 78–93

7. Диапазон: 78–93
   Вопрос: «Число не больше 85?»
   Ответ: Нет → новый диапазон: 86–93

8. Диапазон: 86–93
   Вопрос: «Число не больше 89?»
   Ответ: Нет → новый диапазон: 90–93

9. Диапазон: 90–93
   Вопрос: «Число не больше 91?»
   Ответ: Нет → новый диапазон: 92–93

10. Диапазон: 92–93
    Вопрос: «Число не больше 92?»
    Ответ: Да → задуманное число: 92

Итог:
После 10 вопросов диапазон сужается до одного числа, и мы точно угадываем задуманное число. Так бинарный поиск гарантирует успех за минимальное количество шагов.

Фух! Это было сложно. Давайте теперь решим более простую задачу. 

• Головоломки

Поделиться