[recovery mode] Задача про рыцарей и лжецов
Задачи про рыцарей и лжецов — это классические математические задачи на комбинаторику.
Жили-были на одном небольшом островке в океане два племени — рыцари и лжецы. Рыцари были настолько горды и благородны, что не могли говорить ничего, кроме правды, правды и только правды. А лжецы не различали истину и вымысел.
На острове живут 50 человек. Из которых 35 — лжецы, 15 — рыцари. Какое наименьшее количество человек нужно выбрать, чтобы спросив потом у каждого, кто именно лжецы, по ответам вычислить хотя бы 1 лжеца?
Сразу поясню, что все жители острова знают, кто есть кто. И что отобрать людей для опроса нужно сразу, а не в зависимости от ответов, которые они дают.
Теперь начинаем рассуждать.
Когда мы спрашиваем жителя, кто рыцари, а кто лжецы, он указывает на 15 потенциальных рыцарей и 35 лжецов. Если спросить того, кого он назвал рыцарем, кто есть кто. То возможны 2 варианта:
второй человек подтверждает версию первого (назовем их Команда 1)
или его показания не сходятся с 1, а тогда значит, что врет либо второй (но первый назвал его рыцарем, а значит тоже соврал), либо первый. В любом случае мы идентифицируем 1 лжеца (первый). Ч и тд.
Допустим мы опросили 15 первых человек и все они — Команда 1. То есть абсолютно идентично называют себя рыцарями, а остальных — лжецами. Дает ли это право сказать, что мы решили задачу?
Не совсем. Они все могут оказаться лжецами, которые сговорились.
Теперь предположим что опросили 31 человека. Сепарировались Команда 1 (зеленые), Команда 2 (красные) и у нас 31-ый синий игрок, который называет рыцарем себя, а предыдущих 30 — лжецами. Кому довериться?
Могут быть правы, как первые, так и вторые, и даже 31-ый.
Опросим еще 5 человек. Если кто-то из новеньких 5 назовет рыцарями кого-то из красных или зеленых, то мы автоматически найдем 1 лжеца (тк красные и зеленые называют рыцарями только себя, а остальных — лжецами, а значит не может кто-то из 5 новеньких назвать рыцарем красно-зеленых).
Итак, все новенькие 5 называют рыцарями — синих.
Опросим 46 человек. И у нас будет 3 команды по 15 (зеленые, красные, синие) и 1 человек, который вроде как должен решить, кто же тут прав. Все 45 человек называли этого 46-го лжецом, значит он лжец, тк не собрал на свою сторону 15 человек.
А теперь развернемся. Вспомним, что ищем не того, кто прав. А ищем хотя бы одного лжеца. А значит, можно было остановить поиск намного раньше. Вот у нас 30 человек (красных и зеленых), которые ополчились друг против друга. Вот у нас 31-ый синий. Должно получиться, что все 3 команды обзывают коричневых — лжецами. А коричневым будем не с кем объединиться, чтобы назвать своих 15 человек — рыцарями.
Но вдруг мы опросим еще 5 синих человек и выяснится, что первые 5 синих — говорят одно, а шестой синий назвался желтым и сказал, что все люди до него — врали.
Зеленые, красные, синие или жёлтые? Кто врет и где наш лжец?
Отгадка — в переметнувшемся синем. Остальные 5 синих назвали его своим, а он их предал, что означает, что синие — точно не рыцари. Иначе бы они знали, что переметнувшийся — лжец. И не называли бы его рыцарем. Мы всё еще не знаем, кто рыцарь — зеленые, красные или желтые, но синие — точно врут.
Вроде решили. Вот и я так подумала и отправила ответ.
Но нет.
Важным и ложным допущением было то, что мы делили группы на15 человек. А могло же быть по-другому. Команда 1 — 11 человек, команда 2 — 11, команда 3 — 11. итого 33 человека. Которые называют рыцарями себя и еще четверых, которые не вошли в первоначальную выборку для допроса.
Потом берем еще 11 человек — и они делают тоже самое (желтые).
Из оставшихся 6 коричневых есть 4 — которых все называют рыцарями. Кто врет — неизвестно. Продолжаем опрос.
Берем еще 2 человека. Они должны будут присоединиться к одной из 4 фракций (зеленые, красные, синие, желтые). Допустим они выбрали желтых.
Тогда достаточно будет спросить 47 человека, которого все называют рыцарем (коричневый) и мы узнаем, где лжец. Даже сразу, где все лжецы. Тк 47ой человек — точно рыцарь.
Бонусом: немного другое толкование изначальных условий могло быть дать куда более интересное решение. Если бы можно было опрашивать островитян по очереди. То достаточно было бы спросить у пятерых, кто есть кто, и найти лжеца. То есть первый показывает на 15 рыцарей и 35 лжецов. Идем к лжецу. Он указывает 15 своих рыцарей и обзывает лжецом первого и тд.
Но нет, нужно сразу взять рандомных людей и потом их опрашивать.
Также существуют целые классы задач того же типа, но с другими персонажами — задачи о пациентах и врачах, собранные в частности в книгах математика Рэймонда М. Смаллиана.
