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