В поселке некоторые дома соединены проводами. Соседями называются двое,

дома которых связаны проводом. Всегда ли удастся поселить в каждый дом по

одному человеку - лжецу или рыцарю (лжецы всегда лгут, рыцари всегда говорят

правду) - так, чтобы каждый на вопрос: "Есть ли среди ваших соседей лжецы?"

ответил "Да"? (Каждый житель поселка знает про каждого из своих соседей,

лжец он или рыцарь).

Question

Математика

Германик

30 октября, 17:57

В поселке некоторые дома соединены проводами. Соседями называются двое,

дома которых связаны проводом. Всегда ли удастся поселить в каждый дом по

одному человеку - лжецу или рыцарю (лжецы всегда лгут, рыцари всегда говорят

правду) - так, чтобы каждый на вопрос: "Есть ли среди ваших соседей лжецы?"

ответил "Да"? (Каждый житель поселка знает про каждого из своих соседей,

лжец он или рыцарь).

+5

Ответы (1)

Знаете ответ?

Филюха · Answer 1

Да.

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