В клетках доски стоят рыцари и лжецы - по одному человеку в каждой клетке. Лжецы всегда лгут, а рыцари всегда говорят правду. Каждый из них заявил, что одним из его соседей является лжец. Соседями считаются люди, клетки которых граничат по стороне или по

Добавлена: 29.04.2026
Обновлена: 29.04.2026
Предмет: Геометрия
Автор: Кэмп

#Дискретная математика
#Теория графов

В клетках доски стоят рыцари и лжецы - по одному человеку в каждой клетке. Лжецы всегда лгут, а рыцари всегда говорят правду. Каждый из них заявил, что одним из его соседей является лжец. Соседями считаются люди, клетки которых граничат по стороне или по

Условие:

В клетках доски $32 \times 92$ стоят рыцари и лжецы - по одному человеку в каждой клетке. Лжецы всегда лгут, а рыцари всегда говорят правду. Каждый из них заявил, что одним из его соседей является лжец. Соседями считаются люди, клетки которых граничат по стороне или по вершине. Какое наибольшее число рыцарей может стоять на доске?

Решение:

Рассмотрим доску 32×92. В каждой клетке стоит человек – либо рыцарь (говорит правду), либо лжец (всегда лжёт). Каждый заявил: «одним из моих соседей является лжец». Соседями считаются клетки, имеющие общую сторону или вершину (то есть все 8 направлений, если клетка не на границе).

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

Таким образом получаем усл...