Задача 111806

Темы:    [ Математическая логика (прочее) ] [ Разбиения на пары и группы; биекции ] [ Оценка + пример ]

Сложность: 4+ Классы: 8,9,10,11

Условие

Автор: Мурашкин М.В.

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

Решение

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

Ответ

50 пар.

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

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