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