ВСОШ 2024, 9 класс, задача 3
( баллов) На острове живут рыцари, которые всегда говорят правду, и лжецы, которые всегда лгут. Для игры в настольный теннис навылет всех жителей острова разделили на две команды и , причём в жителей было больше, чем в . Начали игру два игрока разных команд; после каждой партии проигравший игрок навсегда выходил из игры, и его заменял другой (ещё не игравший) член его команды. Проиграла команда, все члены которой вышли из игры. После турнира каждого члена команды спросили: «Правда ли, что в какой-то игре ты проиграл лжецу?», а каждого члена команды спросили: «Правда ли, что ты выиграл хотя бы у двух рыцарей?». Все ответы оказались утвердительными. Какая команда победила — или ?
(М. Дидин)
Ответ
Ответ. Победила .
Решение. Пусть в есть хотя бы один рыцарь . Тогда выиграл хотя бы у двоих рыцарей из , пусть — один из них. Поскольку — рыцарь, он правдиво ответил на заданный ему вопрос, то есть он проиграл лжецу. Но из правил следует, что каждый игрок проигрывает не более одного раза, а проиграл и рыцарю , и лжецу. Это противоречие показывает, что состоит лишь из лжецов.
Предположим, что состоит только из рыцарей. В этом случае каждый из них проиграл какому-то лжецу из команды , однако каждый лжец в выиграл не более, чем у одного рыцаря из , так как он солгал, отвечая на вопрос. Следовательно, разным рыцарям из соответствуют разные лжецы из , поэтому в людей не меньше, чем в ; противоречие.
Таким образом, в команде есть хотя бы один лжец; обозначим одного из них через . Тогда солгал, то есть он не проиграл ни одному лжецу из — а значит, ни одному игроку из . Это значит, что либо выиграл все свои партии, либо до него не дошла очередь. В любом из этих случаев команда выиграла.
Верное доказательство того, что состоит из лжецов.
Верное доказательство того, что в есть хотя бы один лжец.
Указанные баллы суммируются.