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

0 голосов
51 просмотров

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


Математика | 51 просмотров
Дан 1 ответ
0 голосов
Правильный ответ

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

0

Спасибо!

0

Правда, один есть случй, когда такое множество пустое...

0

Например, все жители - соседи

0

Ну тогда нужно в один дом - лжеца, в остальные - рыцарей.