Дано поле 4x4, на котором могут стоять только рыцари и лжецы. Условия задачи гласят, что все рыцари всегда говорят правду, а лжецы всегда врут. Также известно, что каждый рыцарь стоит рядом с лжецами, и каждый лжец должен иметь хотя бы одного рыцаря рядом с собой. Необходимо расставить рыцарей и лжецов на поле, используя как можно меньше рыцарей. Разберемся сначала с клетками, у которых нет соседних. На таких клетках может находиться только рыцарь, так как если бы был лжец, он бы врал о том, что рядом с ним находится рыцарь, что было бы ложью. Таким образом, на клетках, у которых нет соседей, должны стоять рыцари. Теперь рассмотрим клетки, у которых есть соседи. У каждой клетки может быть от 2 до 4 соседей. Если клетка имеет 2 соседа, то она может быть либо рыцарем, либо лжецом. Мы же хотим использовать как можно меньше рыцарей, поэтому на такой клетке будет стоять лжец. Для клеток с тремя соседями мы также можем использовать лжецов, так как они должны иметь хотя бы одного рыцаря рядом с собой. Если бы на такой клетке стоял рыцарь, он бы соврал о том, что все его соседи - лжецы, что противоречит условиям задачи. Таким образом, на клетках с тремя соседями будут стоять лжецы. Остается рассмотреть клетки с четырьмя соседями. Они могут быть заняты только рыцарем, так как лжец на такой клетке сказал бы правду о своих соседях, а это противоречит условиям задачи. Расставим рыцарей и лжецов на поле соответственно этим правилам: | Р | Л | Р | Л | | Л | Л | Р | Л | | Р | Л | Р | Л | | Л | Л | Р | Л | Здесь "Р" обозначает рыцаря, а "Л" - лжеца. На этом поле выполнены все условия задачи, используя только 5 рыцарей.