Задача 4.
На острове живут 200 аборигенов: 100 рыцарей, которые говорят исключительно правду, и 100 лжецов, которые всегда лгут. У каждого из жителей острова есть хотя бы один друг. Как-то 100 жителей острова одновременно сказали: «Каждый мой друг — рыцарь». В этот же момент остальные 100 жителей сказали: «Каждый мой друг — лжец». Какое наименьшее количество пар, состоящих из рыцаря и лжеца, которые дружат между собой, может быть на острове? Один и тот же абориген может входить в несколько разных пар.
Ответ на Задачу 4.
Меньше 50 таких пар быть не может. Действительно, среди тех 100 аборигенов, кто сказал, что все их друзья – лжецы, есть или хотя бы 50 рыцарей, или по крайней мере 50 лжецов. В первом случае у каждого из 50 рыцарей действительно есть хотя бы по одному другу-лгуну, образующих с ними по крайней мере 50 пар. Во втором случае каждый из 50 лжецов имеет хотя бы одного друга-рыцаря, поскольку на самом деле не все его друзья является лжецами. И здесь есть не менее 50 пар.
Количество пар может быть 50. Такой она будет, если, например, рыцарь 1 дружит с лжецом 1, рыцарь 2 дружит с лжецом 2, . . . , рыцарь 50 дружит с лжецом 50, рыцари 51-100 дружат между собой, лжецы 51-100 дружат между собой и больше никто ни с кем не дружит. В таком случае фразу «Каждый мой друг – лжец» скажут первые 50 рыцарей и первые 50 лжецов, а фразу «Каждый мой друг – рыцарь» – остальные аборигены.
