В комнате находятся 100 человек, каждый из которых либо рыцарь, который всегда говорит правду, либо лжец, который всегда лжёт, причём все они разного роста. Каждый из находящихся в комнате сказал ровно одну из двух фраз: <<Хотя бы 5 лжецов ниже меня>>; <<Хотя бы 5 лжецов выше меня>>. Какое наименьшее число рыцарей может быть в комнате?
Answers & Comments
Verified answer
Пусть вкомнате 1 рыцарь и, соответственно, 99 лжецов.Пусть лжецы выстроены в порядке возрастания роста:
z₁, z₂, z₃, ..., z₉₉.
Рассмотрим, для каких лжецов какая фраза будет истинной или ложной.
<<Не менее 5 лжецов ниже меня>>:
Для первых пяти лжецов z₁-z₅ эта фраза действительно ложь, так как слева отних стоит меньше 5 человек. Для остальных лжецов слева стоит хотя бы 5лжецов, и соврать таким образом они не могут.
<<Не менее 5 лжецов выше меня>>:
Напротив, эта фраза ложна для последних пяти лжецов z₉₅-z₉₉, так как справаот них стоит меньше 5 человек. Для остальных лжецов справа стоит хотя бы 5лжецов, и, сказав эту фразу, они не соврут.
Таким образом, соврать смогли лишь 10 лжецов: первые пять человек ипоследние пять человек (с наименьшим и наибольшим ростом). Это наибольшеечисло лжецов, которое может быть в этой ситуации. Именно оно обеспечиваетнаименьшее число рыцарей, которых будет 100-10=90.
Ответ: 90