|
|
 |
Условие
В стране рыцарей (всегда говорят правду) и лжецов (всегда лгут) за круглым столом сидят в вершинах правильного десятиугольника 10 человек, среди которых есть лжецы. Путешественник может встать куда-то и спросить сидящих: "Каково расстояние от меня до ближайшего лжеца из вас?" После этого каждый отвечает ему. Какое минимальное количество вопросов должен задать путешественник так, чтобы гарантированно узнать, кто за столом лжецы? (Посторонних рядом нет, на стол вставать нельзя. Людей считайте точками. Все, включая путешественника, могут точно измерить любое расстояние.)
Решение
Пример. Первый вопрос зададим из произвольной точки. Если все ответы на него одинаковы, то все сидящие за столом – лжецы, поскольку рыцарь и лжец дают разные ответы.
В противном случае найдутся соседи, ответившие по разному. Встанем в середину дуги между ними. Так как хотя бы один из двоих – лжец, то до ближайшего лжеца расстояние известно. Тогда те, кто его назовёт – рыцари, а остальные – лжецы.
Оценка. Пусть был задан только один вопрос. Разобьём людей на группы находящихся на одинаковом расстоянии от путешественника. Будет больше одной группы, поскольку нельзя вставать в центр стола. Пусть ближайшая группа указала на следующую за ней, а остальные – на первую. Легко видеть, что первая группа могла оказаться рыцарями, а остальные – лжецами, но могло быть и наоборот.
Ответ
Два вопроса.
Замечания
10 баллов
