Олимпиадная задача про рыцарей и лжецов на острове — Мурашкин М. В., логика, 8–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 пар.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь