Петя и Вася играют в игру "Угадай число".
Правила игры весьма просты. Петя загадывает число от 1 до 18000. Вася должен Петя и Вася играют в игру "Угадай число".

Правила игры весьма просты. Петя загадывает число от 1 до 18000. Вася должен отгадать число, которое загадал Петя. Для этого Вася может задавать Пете вопросы, на которые Петя может ответить либо "Да", либо "Нет".

Сколько вопросов должен задать Вася в худшем случае при оптимальной стратегии?

Предыдущий
вопрос Следующий
вопрос

Для того чтобы угадать число от 1 до 18000, Васе нужно задать минимум 15 вопросов, чтобы гарантированно угадать число в худшем случае при оптимальной стратегии.

Это следует из того, что 2^14=16384, что означает, что Vasya может задать 14 вопросов, чтобы узнать число в интервале от 1 до 16384. Далее, если ответ на последний заданный вопрос будет "Да", то число будет в промежутке от 8193 до 12288, иначе от 4097 до 8192. Таким образом, ему потребуется дополнительно 1-2 вопроса для угадывания точного числа.

Таким образом, минимальное количество вопросов, которое Васе нужно задать, равно 15.