№ 4. В детской игре «Угадай число» первый участник загадывает целое число от 1 до 32. Второй участник задает вопросы: «Загаданное число больше числа ___?». Какое количество вопросов при правильной стратегии гарантирует угадывание?

Чтобы решить эту задачу, нужно подумать о стратегии бинарного поиска.

Игра работает так: первый участник загадывает число от 1 до 32, а второй может задавать вопросы вида: «Загаданное число больше числа ___?» — то есть ответ «Да» или «Нет». Такой формат идеально подходит для деления диапазона пополам на каждом шаге.

Шаги рассуждения:

1. Диапазон чисел: 1…32
   Всего 32 числа.

2. Стратегия: всегда делим оставшийся диапазон пополам. Например, сначала спрашиваем: «Больше ли число 16?»

   • Если ответ «Да», остаются числа 17…32

   • Если «Нет», остаются числа 1…16

3. Количество шагов:
   Каждый вопрос делит количество возможных чисел примерно на 2. Чтобы гарантированно угадать число, нужно найти минимальное количество вопросов $k$, которое удовлетворяет условию:

   $$2^k \ge 32$$

4. Вычисление:

   • $2^1 = 2$

   • $2^2 = 4$

   • $2^3 = 8$

   • $2^4 = 16$

   • $2^5 = 32$ ✅

   Значит, 5 вопросов достаточно, чтобы при любом исходе точно определить загаданное число.

Вывод:

При правильной стратегии бинарного поиска нужно 5 вопросов, чтобы гарантированно угадать число от 1 до 32.

Хотите, я покажу пример последовательности вопросов?