Олимпиада имени Леонарда Эйлера 2017-2018 учебный год, II тур заключительного этапа

Среди десяти человек ровно один лжец и 9 рыцарей. Рыцари всегда говорят правду, лжецы всегда лгут. Каждому из них дали карточку с натуральным числом от 1 до 10, причем все числа на карточках различны. Любому можно задать вопрос: «Верно ли, что на твоей карточке написано число $M$?» ($M$ может быть только натуральным числом от 1 до 10). Верно ли, что за 17 таких вопросов можно гарантированно найти лжеца? ( О. Подлипский )

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

Комментарии от администратора Комментарии от администратора №1.     Ответ. Верно.
Решение. Зададим одному человеку 9 вопросов — про числа от 1 до 9. Если он лжец, мы получим не меньше восьми положительных ответов и тем самым найдем его. В противном случае он рыцарь, и мы узнаем, что написано на его карточке: если число от 1 до 9, то мы получим утвердительный ответ на соответствующий вопрос, а если число 10, то все ответы будут отрицательными. Узнав, какое число $M$ написано на карточке у первого, зададим восьмерым из остальных вопрос про это число. Если кто-то ответит утвердительно — лжец он, если все ответят отрицательно — лжец тот, кому мы не задавали вопросов.