Последние новости
03.04.24
Предварительные результаты финального тура
05.03.24
Проведение финального тура
01.01.24
Предварительные результаты
25.12.23
Отборочный этап завершён.
18.12.23
Отборочный этап продлён по 24 декабря включительно
За круглым столом сидит n>2 человек. Каждый из них либо рыцарь, либо лжец. Рыцари всегда говорят только правду, а лжецы всегда лгут. Опишите способ построения логической схемы c n входами, которая принимает значение истина тогда и только тогда, когда каждый из сидящих за столом может произнести фразу «Оба моих соседа лжецы».
На логической схеме входы соответствуют людям: нули обозначают лжецов, а единицы рыцарей. Разрешается использовать логические элементы AND (и), OR (или), NOT (не) и XOR (исключающее или). Соседние входы соответствуют соседним людям, кроме того, поскольку стол круглый, самый верхний вход будем считать соседним с самым нижним.
Для иллюстрации Вашего решения Вы можете использовать манипулятор с тремя входами. Однако, оцениваться будет в первую очередь текст решения, автоматической проверки не производится.
Если Лжец говорит фразу «Оба моих соседа лжецы», значит неверно, что его соседи -- оба лжецы. Значит нет трёх подряд идущих лжецов. Если Рыцарь говорит фразу «Оба моих соседа лжецы», то оба его соседа -- лжецы, значит рыцарь не может быть рядом с другим рыцарем. Таким образом нам достаточно проверить, что нет трёх подряд стоящих лжецов и двух подряд стоящих рыцарей. Тогда каждый сможет сказать фразу «Оба моих соседа лжецы». Как это проверить? Очень просто! Для каждый трёх подряд идущих с помощью двух блоков "OR" проверяем, что хотя бы один из них рыцарь, и для каждых двух соседних с помощью одного блока "AND" и одного блока "NOT" проверяем, что неверно, что они оба рыцари. На схеме я показал, как проверить трёх подряд идущих, что они не все лжецы, а также для верхних двух людей я показал, как проверить, что они не оба рыцари. Так мы проверяем для каждой тройки подряд идущих и для каждой пары соседних. Всего у нас n троек и n пар соседних. С помощью (2n-1) блока "AND" проверим, что каждый из 2n выходов истинный.