Олимпиада имени Леонарда Эйлера 2019-2020 учебный год, II тур дистанционного этапа

Петя задумал натуральное число, не большее 4. Вася может указать любое натуральное число или несколько чисел и спросить Петю, есть ли задуманное число среди них (например: «Верно ли, что задуманное число равно 2?» или «Верно ли, что задуманное число равно 2 или 3?»). Петя должен ответить «Да» или «Нет». Как Васе за 11 вопросов узнать задуманное число, если Петя в ответ может и соврать, но не больше трех раз? ( И. Рубанов )

Комментарий/решение

Комментарии от администратора Комментарии от администратора №1.     Пусть Вася сначала задает вопрос: «Задуманное число равно 3 или 4?» до тех пор, пока не получит четыре одинаковых ответа. Очевидно, эти четыре ответа могут быть только правдивыми. Если они положительны, то дальше Вася может задавать вопрос: «Это число 3?», пока не получит четыре одинаковых ответа. Если они положительны, задумано число 3, если отрицательны — число 4. Случай, когда верный ответ на первый вопрос отрицателен, разбирается аналогично (Вася может задавать вопрос: «Это число 2?»). Вася задал не более 11 вопросов, потому что он получил ровно 8 верных ответов, а неверных — не больше трёх.