Вопрос школьника
Толя согласен отвечать на наши вопросы только «да» или «нет». За сколько вопросов мы можем узнать у Толи, в каком месяце он родился? Каким может быть первый вопрос?
Ответ от учителя
Если мы задаем вопросы только с ответами «да» или «нет», то мы можем использовать стратегию бинарного поиска, где каждый вопрос сужает диапазон возможных ответов в два раза.
Предположим, что Толя родился в одном из 12 месяцев года. Первый вопрос, который мы можем задать, должен сужать диапазон ответов в два раза. Мы можем спросить: «Ты родился в первой половине года?» Если ответ «да», то мы можем исключить вторую половину года и продолжить задавать вопросы о первой половине. Если ответ «нет», то мы можем исключить первую половину года и продолжить задавать вопросы о второй половине.
Следующий вопрос должен сужать диапазон ответов в два раза, и он должен быть задан на основе текущего диапазона возможных ответов. Например, если мы узнали, что Толя родился в первых шести месяцах года, то следующий вопрос может быть: «Ты родился в первых трех месяцах года?» Если ответ «да», то мы можем исключить последние три месяца и продолжить задавать вопросы о первых трех месяцах. Если ответ «нет», то мы можем исключить первые три месяца и продолжить задавать вопросы о последних трех месяцах.
Продолжая эту стратегию, мы можем сужать диапазон ответов в два раза на каждом шаге, пока не останется только один месяц. Таким образом, мы можем узнать месяц рождения Толи за максимум 4 вопроса.
Первый вопрос, который мы можем задать, чтобы сужать диапазон ответов в два раза, может быть: «Ты родился в первой половине года?»
