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

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

Условие

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


Решение

  а) Пусть все царевны назовут царевнами Кощеевых дочек (рис. слева). Тогда Кощеевых дочек назовут не менее трёх раз, а царевен – не более чем дважды. Так Иван их и отличит.

             

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


Ответ

Может.

Замечания

Любое из решений пункта б), конечно, годится и для пункта а).

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

олимпиада
Название Математический праздник
год
Дата 2007
класс
Класс 6
задача
Номер 6

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

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