Задание олимпиады: рыцари и лжецы на острове
Задача
На острове рыцарей и лжецов каждый дружит с десятью другими жителями (рыцари всегда говорят правду, лжецы всегда лгут). Каждый житель острова заявил, что среди его друзей больше лжецов, чем рыцарей. Может ли количество рыцарей быть вдвое больше, чем количество лжецов?
Решение
Пусть на острове живут x рыцарей и y лжецов, а количество пар друзей вида рыцарь – лжец равно D. Рыцари говорит правду, поэтому каждый из них входит хотя бы в 6 таких пар. Каждый лжец имеет не более 10 друзей – рыцарей, поэтому входит не более, чем в 10 таких пар. Следовательно, 6x ≤ D ≤ 10y, откуда x ≤ 5y/3 < 2y, так как какие-то аборигены на острове есть (значит, обязательно есть и лжецы). Таким образом, рыцарей не может быть вдвое больше, чем лжецов.
Ответ
Не может.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь