ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 66705
Темы:    [ Логика и теория множеств (прочее) ]
[ Оценка + пример ]
Сложность: 4
Классы: 8,9,10,11
В корзину
Прислать комментарий

Условие

Автор: Дидин М.

В стране рыцарей (всегда говорят правду) и лжецов (всегда лгут) за круглым столом сидят в вершинах правильного десятиугольника 10 человек, среди которых есть лжецы. Путешественник может встать куда-то и спросить сидящих: "Каково расстояние от меня до ближайшего лжеца из вас?" После этого каждый отвечает ему. Какое минимальное количество вопросов должен задать путешественник так, чтобы гарантированно узнать, кто за столом лжецы? (Посторонних рядом нет, на стол вставать нельзя. Людей считайте точками. Все, включая путешественника, могут точно измерить любое расстояние.)


Решение

  Пример. Первый вопрос зададим из произвольной точки. Если все ответы на него одинаковы, то все сидящие за столом – лжецы, поскольку рыцарь и лжец дают разные ответы.
  В противном случае найдутся соседи, ответившие по разному. Встанем в середину дуги между ними. Так как хотя бы один из двоих – лжец, то до ближайшего лжеца расстояние известно. Тогда те, кто его назовёт – рыцари, а остальные – лжецы.

  Оценка. Пусть был задан только один вопрос. Разобьём людей на группы находящихся на одинаковом расстоянии от путешественника. Будет больше одной группы, поскольку нельзя вставать в центр стола. Пусть ближайшая группа указала на следующую за ней, а остальные – на первую. Легко видеть, что первая группа могла оказаться рыцарями, а остальные – лжецами, но могло быть и наоборот.


Ответ

Два вопроса.

Замечания

10 баллов

Источники и прецеденты использования

олимпиада
Название Турнир городов
номер/год
Номер 39
Дата 2017/18
вариант
Вариант весенний тур, сложный вариант, 8-9 классы
задача
Номер 6

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .