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

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

Условие

На острове 100 рыцарей и 100 лжецов. У каждого из них есть хотя бы один друг. Однажды ровно 100 человек сказали: "Все мои друзья – рыцари", и ровно 100 человек сказали: "Все мои друзья – лжецы". Каково наименьшее возможное количество пар друзей, один из которых рыцарь, а другой лжец?


Решение

  Рассмотрим какого-нибудь жителя А острова, утверждающего: "Все мои друзья – лжецы". Если А – рыцарь, то его друг – лжец. Если А – лжец, то его друг – рыцарь. В любом случае А входит в пару друзей "разного" сорта. Так как такое высказывание сделали 100 человек, то количество таких пар не может быть меньше, чем  100 : 2 = 50.
  Пример: пусть 50 рыцарей дружат между собой, 50 лжецов дружат между собой, и есть 50 пар друзей вида "рыцарь – лжец", причём других друзей у жителей из этих пар нет. Тогда каждыйиз первых двух групп вправе сказать: "Все мои друзья – рыцари", а каждый из третьей группы: "Все мои друзья – лжецы".


Ответ

50 пар.

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

олимпиада
Название Московская математическая регата
год
Год 2013/14
класс
Класс 9
задача
Номер 9.3.3

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

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