Задача:
На острове живут рыцари, которые всегда говорят правду, и лжецы, которые всегда лгут. По кругу стоят 1713 островитян, каждую секунду все они одновременно говорят одному из своих соседей «Ты рыцарь!» или «Ты лжец!», после чего на доске записывается количество фраз «Ты лжец!». Спустя 1712 секунд оказалось, что на доске записаны все числа от 1 до 1712. Какое наименьшее количество рыцарей может быть в кругу?
Ответ:
Поскольку в кругу 1713 человек, и каждый человек говорит одному из своих соседей, то в любой момент времени будет сказано 1713 утверждений.
Посмотрим на экстремальные ситуации:
- Если бы все были рыцарями, то каждый рыцарь говорил бы правду. В этом случае на доске было бы 0 утверждений «Ты лжец!», потому что каждый бы считал своего соседа рыцарем.
- Если бы все были лжецами, то каждый из них говорил бы, что его сосед — рыцарь (вручив таким образом), и на доске также было бы 0 утверждений «Ты лжец!».
По условию задачи на доске записаны все числа от 1 до 1712. Таким образом, было 1 момент, когда было сказано только одно утверждение «Ты лжец!», 2 момента, когда было сказано два утверждения «Ты лжец!» и так далее до 1712 утверждений «Ты лжец!».
Для того чтобы было сказано только одно утверждение «Ты лжец!», нужно, чтобы только один лжец стоял между двумя рыцарями (таким образом, только этот лжец скажет своему рыцарю-соседу «Ты лжец!»).
Для минимизации количества рыцарей давайте представим, что каждая пара рыцарей разделена одним лжецом. Таким образом, каждый раз, когда добавляется один рыцарь, добавляется и один лжец. Если бы у нас было 856 рыцарей, то между ними было бы 855 лжецов. Но также нужен еще один лжец для 1712 утверждений «Ты лжец!» (так как каждый лжец скажет обоим своим соседям «Ты лжец!»).
Итак, чтобы были все числа от 1 до 1712, нам понадобится 856 рыцарей и 857 лжецов. Таким образом, наименьшее количество рыцарей в кругу — 856.