Угадать число за семь вопросов — разбор задачи

Условие

Загадано целое число от $1$ до $100$ включительно. Разрешено задавать вопросы, на которые отвечают только «да» или «нет». Как гарантированно определить число не более чем за $7$ вопросов?

О задаче · 6–9 классы

Тема: Алгоритмы
Для кого: 6–9 классы и взрослые
Уровень библиотеки: Следующий шаг · ориентир

Записать идею

Личный черновик для заметок и расчётов. Он никуда не отправляется и не проверяется.

Подсказка 1

Первый вопрос: число не больше пятидесяти?

Подсказка 2

Каждый раз делите оставшийся диапазон на две части, различающиеся не более чем на один вариант.

Разобрать решение по шагам

Первое деление

Ответ на «число не больше $50$ » оставляет $50$ вариантов: от $1$ до $50$ либо от $51$ до $100$

Повторим тот же выбор

Делим текущий диапазон как можно поровну и спрашиваем про нижнюю половину. В худшем случае числа кандидатов таковы:

100\to50\to25\to13\to7\to4\to2\to1.

Это семь вопросов.

Почему шести недостаточно

Шесть ответов «да/нет» имеют не более $2^6=64$ разных последовательностей. Чтобы отличить $100$ чисел, каждому нужен отдельный результат. Значит, гарантированно уложиться в шесть нельзя.

Ответ

$7$ вопросов достаточно; $6$ не гарантируют ответ.

Главная идея

Двоичный поиск на каждом шаге уменьшает число кандидатов примерно вдвое. Чтобы он работал, вопрос должен надёжно определять нужную половину.

Как заметить эту идею в другой задаче

Есть упорядоченные варианты и надёжные вопросы про половину диапазона. Деление пополам даёт короткую стратегию даже в худшем случае.

Возможная ошибка

Оценивать стратегию только по удачному случаю. Гарантированное число вопросов определяется самым длинным возможным путём.

Источник и примечания

Источник и редакция

Учебный разбор Popov Academy · Алгоритмы и двоичный поиск. Не вариант конкретной олимпиады или экзамена.

Проверь себя

Сколько вопросов «да/нет» необходимо и достаточно, чтобы гарантированно определить число от $1$ до $1000$

Ответ к дополнительной задаче

$10$ вопросов: $2^9=512<1000\le1024=2^{10}$ . Девяти недостаточно, а последовательное деление пополам даёт десять.

Продолжить тему: Поиск и алгоритмы →

Тема, знания и приёмы

Поиск и алгоритмы · Начальный вход

Деление диапазона пополам. Код писать не потребуется.

Приёмы решения: Разделение пространства поиска

Задать вопрос по задаче →

Условие

Первое деление

Повторим тот же выбор

Почему шести недостаточно

Источник и редакция

Условие

Дополнительная задача