|
|
 |
Условие
На острове живут 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 пар.
