Можно ли на дощечке 4*4 поставить 8 рыцарей и 8 обманщиков,

Рядом с каждым лгуном обязан быть хоть один рыцарь, а рыцарей друг с ином рядом быть не может. Четырёх рыцарей можно легко расставить в квадрате так, чтобы остальное заполнилось лжецами (к примеру, поставив рыцарей по углам). Тогда обманщиков будет 4x4 - 4 = 12. Мы привели пример, что такое количество лжецов может быть. Докажем, что это ответ, то есть что больше нельзя. Обманщиков можно было бы сделать больше только за счёт убавления количества рыцарей. Разобьём квадрат 4x4 на 4 квадратика 2x2. Докажем, что в любом из них должен обязательно быть рыцарь. Вправду, в неприятном случае весь квадратик 2x2 заполнен лжецами, а лгун, находящийся в углу великого квадрата, не будет соседствовать ни с каким рыцарем, что невозможно. Так как квадратиков 2x2 4 штуки, то и рыцарей меньше 4 быть никак не может.