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

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

Условие

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

Решение

Покажем, что можно найти не менее 50 пар друзей, один из которых рыцарь, а другой – лжец. Если фразу "Все мои друзья – лжецы" произнесло не менее 50 рыцарей, то каждый из них знает хотя бы одного лжеца, и 50 требуемых пар нашлись. В противном случае фразу "Все мои друзья – лжецы" произнесло не менее 50 лжецов. Но так как лжецы лгут, каждый из них знает хотя бы одного рыцаря, и 50 требуемых пар также нашлись. Покажем, что возможна ситуация, в которой пар друзей рыцарь-лжец ровно 50. Обозначим рыцарей k1, k2, .., k100 , а лжецов– l1, l2, .., l100 . Пусть рыцарь k1 дружит только со лжецом l1 , рыцарь k2 – только со лжецом l2 , рыцарь k50 – только со лжецом l50 (и при этом лжецы l1, l2, .., l50 больше ни с кем не дружат). Рыцари k51, k52, .., k100 пусть дружат только друг с другом, и лжецы l51, l52, .., l100 – тоже только друг с другом. Тогда пар рыцарь-лжец ровно 50, 100 человек k1, k2, .., k50, l1, l2, .., l50 произносят фразу "Все мои друзья – лжецы", а остальные 100 человек произносят фразу "Все мои друзья – рыцари".

Ответ

50 пар.

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

олимпиада
Название Всероссийская олимпиада по математике
год
Год 2008
Этап
Вариант 4
Класс
Класс 11
задача
Номер 08.4.11.5
олимпиада
Название Всероссийская олимпиада по математике
год
Год 2008
Этап
Вариант 4
Класс
Класс 10
задача
Номер 08.4.10.5

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

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