В замке 16 одинаковых квадратных комнат, образующих квадрат 4×4. В эти комнаты по одному человеку поселилось 16 человек — лжецы и рыцари (лжецы всегда лгут, рыцари всегда говорят правду). Каждый из этих 16 человек сказал: «По крайней мере в одной из соседних комнат живёт лжец». Какое наибольшее количество рыцарей могло быть среди этих 16 человек? Комнаты считаются соседними, если у них общая стена.

Наибольшее количество рыцарей — 12.

Если человек — рыцарь, его фраза правдива: рядом с ним есть хотя бы один лжец. Значит, каждый рыцарь должен соседствовать хотя бы с одним лжецом.

Если человек — лжец, его фраза ложна. Он сказал: «Рядом есть хотя бы один лжец». Значит, на самом деле рядом с ним нет лжецов, то есть все его соседи — рыцари. Поэтому два лжеца не могут стоять в соседних комнатах.

Нужно расставить как можно меньше лжецов так, чтобы каждый рыцарь имел рядом хотя бы одного лжеца, а лжецы не соседствовали друг с другом. В квадрате \(4 \times 4\) достаточно поставить 4 лжецов, например в клетках \((1,2)\), \((2,4)\), \((3,1)\), \((4,3)\). Тогда все остальные 12 клеток имеют соседа-лжеца.

Меньше 4 лжецов быть не может: один лжец «покрывает» соседством не больше 4 комнат, а нужно, чтобы все рыцари были рядом с лжецом. Для \(15\), \(14\) или \(13\) рыцарей лжецов было бы слишком мало.

Значит, максимум рыцарей: \(16 - 4 = 12\).

0 0 Пожаловаться