Логика → .09 Рыцари и лжецы

Индукция по количеству городов:

База для одного города: сделаем лжеца мэром города, тогда он ответит удовлетворительно, потому что у него вообще нет соседей.

Переход: рассмотрим город и забудем про один из них. По предположению президент может назначить мэров в оставшиеся города так, как нужно. Если среди соседей забытого города есть лжецы, будем считать сделаем его мэром рыцаря, тогда переход выполнен. Если все его соседи рыцари, сделаем лжеца его мэром.

Рассмотрим любую четвёрку подряд идущих людей. Если бы в ней было хотя бы 3 рыцаря, то самый первый из рыцарей точно сказал бы неправду, что невозможно. Если бы в ней было хотя бы 3 лжеца, то самый первый из лжецов точно сказал бы правду, что тоже невозможно. Значит, в каждой четвёрке подряд идущих людей ровно 2 рыцаря и ровно 2 лжеца. Разбив всех людей на 15 таких четвёрок, получаем, что рыщарей .

Оценка: Рассмотрим людей, сказавших первую фразу. Среди них не более одного рыцаря (в ином случае рыцарь с наименьшим номером среди них соврал бы). Таким образом, всего рыцарей не больше 6. Также среди всех присутствующих есть хотя бы 1 рыцарь (в ином случая все лжецы, говорившие первую фразу, говорили бы правду).

Пример: Пусть люди говорят фразы в порядке их номеров футболок. Запишем в ряд номера произнесенных ими фраз:

• 2, 2, 2, 2, 2, 1, 1, 1, 1, 1: всего 6 рыцарей с номерами 1—5 и 10.
• 2, 2, 2, 2, 1, 2, 1, 1, 1, 1: всего 5 рыцарей с номерами 1—4 и 10.
• 2, 2, 2, 1, 2, 2, 1, 1, 1, 1: всего 4 рыцаря с номерами 1—3 и 10.
• 2, 2, 1, 2, 2, 2, 1, 1, 1, 1: всего 3 рыцаря с номерами 1—2 и 10.
• 2, 1, 2, 2, 2, 2, 1, 1, 1, 1: всего 2 рыцаря с номерами 1 и 10.
• 1, 2, 2, 2, 2, 2, 1, 1, 1, 1: всего 1 рыцарь с номером 10.

Обозначим рыцаря Р, лжеца - Л. Заметим, что каждый рыцарь стоит между рыцарем и лжецом, иначе он сказал бы неправду. Значит, рыцари стоят группами по двое.

Лжецы не могут стоять группами более чем из одного человека, так как в таком случае лжец, стоящий с краю групшы сказал бы правду. Значит, чередуются групшы из двух рыцарей и одного лжеца: РРЛРРЛРРЛ

Так как рыцарей 48, то лжецов 24. Таким образом, всего 72 человека.

Заметим, что ученики на местах — хулиганы, так как между каждым из них и Владом меньше 6 человек. Значит, ученик с номером 6 — отличник. То же самое можно сказать про ученика на 5-м месте, затем про 4-е, про 3-е, про 2-е и про 1-е.

Получается, что первые шесть мест занимают отличники, следующие шесть мест занимают хулиганы, а уже на месте 13 стоит Влад. Аналогичное рассуждение можно провести для учеников на местах . Таким образом, в шеренге ровно хулиганов.

Заметим, что подходит. В этом случае бельчонок всего один. Раз по условию среди бельчат есть хотя бы один рыцарь, то этот единственный бельчонок является рыцарем. А его фраза, что рыцарь всего один, верна.

Теперь предположим, что В этом случае бельчат хотя бы трое. Заметим, что слова бельчат с номерами одинаковой чётности противоречат друг другу, потому что они называют разные числа рыцарей (лжецов). Значит, может быть лишь один рыцарь с чётным номером и лишь один рыцарь с нечётным номером. Всего рыцарей, таким образом, не больше двух.

Бельчата с нечётными номерами говорят, что количество рыцарей нечётно. А бельчата с чётными номерами говорят, что количество лжецов чётно, соответственно количество рыцарей по мнению каждого из них тоже нечётно.

По условию на полянке был хотя бы один рыцарь. Значит, хотя бы одно высказывание верно и рыцарей должно быть нечётное число. А если рыцарей не больше двух, то рыцарь может быть только один.

Предположим, что первый является рыцарем. Тогда все остальные — лжецы, а их ровно Значит, бельчонок под номером сказал правду, а должен быть лжецом. Противоречие. Значит, первый соврал.

Если первый соврал, то на полянке не один рыцарь. Но мы поняли, что больше одного рыцаря быть не может. В итоге случай невозможен.

Рассмотрим граф, каждая вершина — рыцарь либо лжец. Ребро — дружба. По условию из вершин-рыцарей и из вершин-лжецов исходит нечетное количество ребер. Предположим, что в графе 2021 вершина. Получаем противоречие с леммой о рукопожатиях — количество вершин нечетной степени нечетно.

Если за столом больше двух рыцарей, то какие-то два из них не соседи и ни один из них не может сказать, что все за столом, кроме, может быть, него и его соседей, лжецы, ибо это будет ложью. Если за столом один рыцарь, то для любого лжеца, соседнего с ним, эта же фраза будет правдой, которую ему говорить не положено. Тоже самое будет верно для любого лжеца, если за столом вообще нет рыцарей.

Назовём первой группой всех людей, сказавших первую фразу, и второй груипой всех людей, сказавших вторую фразу. Рассмотрим два случая.

• Пусть во второй группе есть хотя бы отличник, выберем любого из них. Среди 24 остальных людей хулиганов в три раза больше, чем отличников, поэтому всего хулиганов ровно 18 , а отличников ровно .

  Заметим, что такая ситуация возможна: в первой группе было 5 отличников, сказавших правду (ведь ), а во второй группе было 2 отличника, сказавших правду (ведь ), а также 18 хулиганов, сказавших неправду (ведь ).

• Пусть во второй группе вообще нет отличников, тогда всего хулиганов хотя бы 20. Тогда любой человек из первой группы сказал правду (ведь и 19, и 20 составляют больше половины от 24), поэтому все 5 человек в первой группе — отличники, и отличников в классе ровно 5 .

  Заметим, что такая ситуация возможна: в первой группе было 5 отличников, сказавших правду (ведь ), а во второй группе было 20 хулиганов, сказавших неправду (ведь ).

Заметим, что на поляне может быть рыцарей, если все остальные там — лжецы.

Если на поляне хотя бы один рыцарь, то из его слов следует, что на ней есть ещё рыцарь, лжец и хитрец. Если на поляне будет второй лжец, то он скажет правду, поскольку рыцарь, хитрец и второй лжец для него найдутся. Но лжец не может говорить правду. Потому лжец ровно один.

Пусть на поляне хотя бы два хитреца. Тогда каждый из них скажет правду. Значит, до них стояли лжецы. А лжец всего один. Противоречие.

Потому на поляне ровно один хитрец и рыцаря, а хитрец говорит неправду после какого-то из них. Это единственная подходящая нам расстановка при наличии на поляне рыцарей.

Заметим, что 2-й и 3-й высказываются о текущей остановке по-разному, а о предыдущей одинаково. Это означает, что среди них нет ни одного рыцаря, т.е. 2-й и 3-й — лжецы. Но 3-й и 1-й говорят о текущей остановке одинаково, значит, 1-й тоже лжец.

Рассмотрим произвольного рыцаря. Из его фразы следует, что на собрании рыцарей и лжецов. Построим двудольный граф знакомств рыцарей и лжецов, в первой доле вершины — рыцари, во второй — лжецы. Из каждой из хотя бы вершин первой доли исходит минимум ребер, следовательно, ребер в графе C другой стороны, лжец знаком не более, чем с рыцарями, а значит, если лжецов то имеем

Приведем пример на рыцарей и лжецов: пронумеруем рыцарей и лжецов. Рассмотрим первых рыцарей. Пусть среди них рыцари и лжецы с одинаковыми номерами будут не знакомы. А также со сдвигом на один: второй рыцарь не знаком с первым лжецом, третий рыцарь со вторым и так далее. Все остальные знакомы, рыцари попарно знакомы между собой, а лжецы попарно не знакомы. Такая ситуация подходит, так как каждый лжец не знаком хотя бы с двумя рыцарями, и каждый рыцарь знаком хотя бы с лжецами.

Докажем, что правильная расстановка по кругу возможна тогда и только тогда, когда рыцарей, по крайней мере, в два раза больше, чем лжецов.

Действительно, из условия задачи следует, что в такой расстановке соседями каждого лжеца являются два рыцаря, а среди соседей любого рыцаря есть хотя бы один рыцарь. Тогда правильная расстановка должна выглядеть так: группа рыцарей, лжец, группа рыцарей, лжец, и так далее (в каждой группе не менее двух рыцарей). Значит, при такой расстановке рыцарей хотя бы в два раза больше, чем лжецов.

В обратную сторону: если рыцарей в два раза больше, чем лжецов, то делаем расстановку вида РРЛРРЛ…, а оставшихся рыцарей (если они есть) помещаем между любыми двумя рыцарями. Таким образом, если выполняется такое условие, то правильная расстановка возможна.

Пусть в правильной расстановке, указанной в условии, стоят Р рыцарей и Л лжецов, тогда . Подошедший лжец сказал неправду, поэтому вместе с ним правильная расстановка невозможна, следовательно, Таким, образом или . В первом случае, в исходной расстановке 2019. рыцарей, а второй случай невозможен, так как число не будет целым.

Если Гоша сказал правду, то Кеша лжец. Противоречия нет — ведь тогда он действительно соврал. При этом Рома также соврал, поэтому он должен быть хитрецом. Гоша, соответственно, рыцарь.

Если Гоша соврал, то Кеша хитрец или рыцарь. Из его фразы мы можем сделать вывод, что он хитрец, потому что рыцарь бы назвался собой. Тогда Рома лжец, ведь место хитреца уже занято, а он солгал. Но Гоша также соврал, назвав хитреца Кешу лжецом, поэтому среди попугаев не может быть рыцаря. Получаем противоречие.

Рассмотрим произвольного убежавшего:

В первом случае он — рыцарь. Заметим, что после рыцаря может убежать как и рыцарь, так и лжец, ведь если убежал рыцарь, то кол-во лжецов не изменилось, а если убежал лжец, то их число стало четным и лжец соврал.

Во втором случае он — лжец. Тогда он соврал и после него осталось четное число лжецов. Заметим, что после лжеца рыцарь убежать не может, ведь лжецов останется четное число. Может ли лжец убежать следом за лжецом? Нет, так как без него останется нечетное кол-во лжецов и лжец скажет правду. Итого, после лжеца никто не может убежать. Значит, только последний убежавший мог быть лжецом(все убежавшие, кроме, может быть, последнего, рыцари). Следовательно, всего на поляне не больше лжецов и их количество нечетно. Приведем примеры на пусть последний убежавший — лжец, и среди оставшихся на поляне бельчат лжецов соответственно.

Заметим, что у каждого рыцаря больше друзей рыцарей, а у каждого лжеца друзей лжецов хотя бы столько же, сколько и друзей рыцарей. Тогда в соответствующем графе (вершины первого цвета — рыцари, второго цвета — лжецы, ребро проводится, если два жителя дружат) у каждой вершины одноцветных рёбер не меньше, чем разноцветных. Значит, если их все просуммировать, то и всего одноцветных рёбер не меньше, чем разноцветных.

В одном селе не могут жить хотя бы два рыцаря, так как иначе бы рыцари солгали. Также в селе не могут все быть лжецами, поскольку тогда бы эти лжецы сказали правду.

Значит, в каждом селе ровно один рыцарь, и всего рыцарей 10, а лжецов — 990.

Рассмотрим высказывание первого. Оно точно неверно, значит, первый либо лжец, либо хитрец. Если он хитрец, то высказывание третьего верно, а значит он точно рыцарь. Остается второй, и он должен быть лжецом, при этом второй сказал правду. Такой случай невозможен.

Значит, первый лжец. Тогда третий не может быть рыцарем, ведь он говорит неправду. Поэтому он хитрец, а оставшийся, второй, — рыцарь, и он говорит правду.

Предположим, что среди людей есть как рыцари, так и лжецы. Тогда для рыцаря фраза должна быть верной, значит, всего рыцарей не больше тогда лжецов хотя бы Значит, для лжеца часть фразы “... не меньше десяти лжецов” верна, поэтому не верна должна быть часть “не больше пяти рыцарей”, откуда рыцарей ровно и такой случай действительно возможен.

Если нет рыцарей, то лжецов больше и все они говорят правду. Если нет лжецов, то рыцарей больше и все они говорят неправду, оба этих случая невозможны.

Оценка. Рассмотрим четырех подряд стоящих человек. Если среди двух средних нет лжеца, то один их них рыцарь, а значит один из крайних людей этой четверки обязательно лжец. Поэтому в каждой четверке подряд идущих человек есть лжец. Разобьем человека на одну тройку и четверок подряд идущих людей, причем выберем тройку так, чтобы в ней был лжец. Тогда лжецов хотя бы

Пример. Будем ставить людей такими четверками: (Р-Л-Р-Х)-(Р-Л-Р-Х)-... Закончим круг такой тройкой: (Р-Л-Р-Х)-(Р-Л-Р). Тогда рядом с каждым рыцарем будет стоять лжец, а рядом с каждым лжецом рыцарей не будет. Значит, условие выполняется, а лжецов ровно