В городе М живут только рыцари и лжецы. Рыцари всегда говорят правду, а лжецы всегда врут. Каждый год у них проходит фестиваль. На фестивале есть квадратное поле, в каждую клетку которого встал либо рыцарь, либо лжец. Все они одновременно сказали, что во всех соседних по стороне клетках стоят лжецы. Это значит, что рядом с каждым рыцарем стоят только лжецы, а с каждым лжецом должен соседствовать хотя бы 1 рыцарь. Расставьте рыцарей и лжецов на поле 4 × 4, выполнив условия задачи и используя как можно меньше рыцарей.
Ответ
Для решения задачи нам необходимо использовать хотя бы одного рыцаря, так как иначе все клетки будут заняты лжецами и условие о соседях не будет выполнено.
Минимальная конфигурация, удовлетворяющая всем условиям, состоит из 1 лжец и 4 рыцаря.
1 строка 2 столбец,
2 строка 4 столбец,
3 строка 1 столбец,
4 строка 3 столбец
Ответ: 4 рыцаря