Question

В поселке некоторые дома соединены проводами. Соседями называются двое,
дома которых связаны проводом. Всегда ли удастся поселить в каждый дом по
одному человеку – лжецу или рыцарю (лжецы всегда лгут, рыцари всегда говорят
правду) – так, чтобы каждый на вопрос: “Есть ли среди ваших соседей лжецы?”
ответил “Да” ? (Каждый житель поселка знает про каждого из своих соседей,
лжец он или рыцарь).

Answer 1

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