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