Так исторически сложилось, что математики любят селить на остров рыцарей и лжецов, при этом считая, что рыцари ребята благородные и всегда говорят правду. На этом удобном обобщении строятся сотни логических задач разной сложности. Предыдущая задача по теме: Задача 13.
Условие:
На некотором острове живут только рыцари (всегда говорят правду) и лжецы (всегда врут). На выборах мэра n кандидатов. Каждый из них сделал заявление. А именно k-й (1≤ k≤ n) сказал "Не считая меня, среди претендентов лжецов на k больше чем рыцарей". Сколько всего человек претендует на пост мэра?
Решение:
Очевидно, что рыцарей не может быть больше одного, иначе два противоречащих утверждения должны быть правдивыми. Действительно для i-го рыцаря помимо него a лжецов и n-a-1 рыцарей и для j-го рыцаря тоже a лжецов и n-a-1 рыцарей, при этом они оба утверждают, что число лжецов на i (на j) больше чем рыцарей, что не возможно так как i не равно j.
Рыцарь всегда должен быть, иначе n-й лжец говорит правду.
Таким образом может быть только один рыцарь и легко проверить, что он занимает n-1 позицию.
Покажем, что не может быть больше 3 претендентов. Если претендентов больше трех, то (n-3)-й претендент — лжец, но помимо него остается n-2 лжеца и 1 рыцарь, то есть лжецов на n-3 больше чем рыцарей, а это утверждение должно быть ложным.
Легко показать, что случаи с 2 и 3 претендентами реализуются: рыцарь, лжец; лжец, рыцарь, лжец.
Всем кто дочитал, спасибо за внимание! Удачных вам вычислений!
Немного попрошайничества. Если вам понравилось ставьте большой палец вверх, если хотите еще - подписывайтесь.