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

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

Условие

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


Решение

  a) Зададим каждому вопрос, ответ на который нам известен (например, "Верно ли, что сегодня четверг?"). Пусть получен только один правдивый ответ. Тогда давший его – правдивый. Спросив его про одного из двух других "Верно ли, что он хитрец?", мы все узнаем.
  Если на первые три вопроса получен ровно один ложный ответ, то давший его – лжец, и четвёртый вопрос надо задать ему.

  б) Обозначим участников: врун – В, правдивый – П, хитрецы – ХВ и ХП. Поставим их лицом друг против друга, так что ХП как бы служит отражением П, а ХВ – отражением В, и наоборот. Пусть хитрецы договорятся отвечать так, как будто вопрос адресован их отражению, и все упомянутые в вопросе лица тоже заменены на их отражения. Тогда невозможно отличить, кто стоит "перед зеркалом", а кто "за зеркалом" – ответы отражений всегда совпадают.

Замечания

1. Баллы – 1 + 3.

2. Задача также опубликована в Задачнике "Кванта" ("Квант", 2007, №1, задача М2028).

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

олимпиада
Название Турнир городов
Турнир
Номер 28
Дата 2006/2007
вариант
Вариант осенний тур, тренировочный вариант, 8-9 класс
задача
Номер 2

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

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