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