Question

Лжецы и рыцари На острове живут рыцари и лжецы. Некоторые из них дружат. В круг встала компания из 2021 островитянина, после чего каждый из них заявил: «У меня в этой компании больше друзей, чем у обоих моих соседей». Какое максимальное количество рыцарей может быть в этой компании?​

Answer 1

Ответ:

tПошаговое объяснение:

1. Все лжецами быть немогут, т.к. это противоречит условию задачи. Значит на острове есть как минимум 1 рыцарь. Из его заявления вытекает, что лжецов больше, чем (2021-1):2=1010.

2.Теперь заявление любого лжеца ложно, т.е. не считая его, не более половины на острове- лжецы. Следовательно, если убрать одного лжеца, то оставшихся будет не больше, чем 1010, т.е. всего лжецов не больше 1011, Единственное целое число больше 1010, но не более 1011 - это 1011.

3. Значит максимальное число рыцарей 2021-1011=1010.

Answer 2

Предположим, что в компании оказалось n человек. Тогда каждый из них заявил, что у него больше друзей, чем у обоих его соседей.

Рассмотрим первого человека в компании. Поскольку у него больше друзей, чем у обоих его соседей, значит, он не может быть лжецом, так как лжец может иметь только одного друга (рыцарь может иметь двух).

Это означает, что первый человек в компании — рыцарь. Теперь рассмотрим его двух соседей. Оба из них заявили, что у них меньше друзей, чем у их обоих соседей. Опять же, это возможно только в случае, если они оба лжецы.

Таким образом, первый человек в компании — рыцарь, его соседи — лжецы. Это означает, что в компании есть как минимум один рыцарь и два лжеца.

Рассмотрим следующего человека в компании. Если он заявит, что у него больше друзей, чем у обоих его соседей, это будет значить, что он рыцарь. Тогда у него будет два друга (первый человек в компании и второй человек, который является его соседом).

Если следующий человек заявит, что у него меньше друзей, чем у обоих его соседей, это будет значить, что он лжец. Тогда у него будет 0 друзей (рицарь первый в списке не может быть его другом, так как рыцарь может иметь только двух друзей).

Таким образом, каждый следующий человек в цепочке будет чередоваться между рыцарем и лжецом. Число рыцарей будет увеличиваться по мере продвижения в цепочке.

Итак, максимальное количество рыцарей в компании будет равно количеству людей в компании, которые стоят на нечетных позициях. Например, если в компании 2021 человек, то максимальное количество рыцарей будет 1010 (половина от 2021).

В общем случае, если в компании четное количество людей n, то максимальное количество рыцарей будет n/2, а если нечетное количество, то (n+1)/2.