Деревня рыцарей и лжецов на карте имеет вид клетчатого квадрата 9×9, в каждой клетке живет один человек – рыцарь или лжец. Рыцари всегда говорят правду, а лжецы всегда врут. Соседними считаются клетки, примыкающие друг к другу по стороне или углу. Каждый житель сказал: Среди моих соседей нечётное число лжецов. Чётно или нечётно количество лжецов в деревне?
Ответы
Разобьем доску на девять квадратов 3×3. Докажем, что в каждом таком квадрате нечетное количество лжецов. Рассмотрим жителя из центральной клетки. Если он рыцарь, то среди его соседей нечётное число лжецов и значит и во всём квадрате их нечётное число. Если он лжец, то среди его соседей - чётное число лжецов, да еще он сам и в итоге в квадрате - нечётное число лжецов.
Так как сумма девяти нечётных чисел нечётна, значит нечётно и общее число лжецов.