Question

Можно ли на доске 4*4 поставить 8 рыцарей и 8 лжецов, чтобы каждый мог сказатт: "Рядом со мной стоит два рыцаря"? (Лжецы всегда врут, а рыцари говорят правду). Ответ обоснуйте.

Answer 1

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

Answer 2

Да, возможно такое размещение на доске 4x4, чтобы каждый из 8 рыцарей и 8 лжецов мог сказать: "Рядом со мной стоит два рыцаря". Вот один из способов организации такого размещения:

Предположим, что буква "Р" представляет рыцаря, а буква "Л" - лжеца. Тогда одно из возможных решений будет выглядеть так:

Copy code
Р Л Р Л
Л Р Л Р
Р Л Р Л
Л Р Л Р

Теперь докажем, что все утверждения верны:

1. Первый рыцарь (Р) утверждает, что рядом с ним два рыцаря (действительно, слева и справа от него стоят рыцари).
2. Первый лжец (Л) утверждает, что рядом с ним два рыцаря (действительно, слева и справа от него стоят рыцари).
3. Второй рыцарь (Р) утверждает, что рядом с ним два рыцаря (действительно, слева и справа от него стоят рыцари).
4. Второй лжец (Л) утверждает, что рядом с ним два рыцаря (действительно, слева и справа от него стоят рыцари).
5. Третий рыцарь (Р) утверждает то же самое.
6. Третий лжец (Л) утверждает то же самое.
7. Четвертый рыцарь (Р) утверждает, что рядом с ним два рыцаря (действительно, слева и справа от него стоят рыцари).
8. Четвертый лжец (Л) утверждает, что рядом с ним два рыцаря (действительно, слева и справа от него стоят рыцари).

Таким образом, все условия выполнены, и каждый из рыцарей и лжецов может сказать: "Рядом со мной стоит два рыцаря".