Question

Путешественник посетил деревню, каждый житель которой либо рыцарь (всегда говорит правду), либо лжец (всегда лжёт). Всего в деревне живёт 26 человек. Все жители деревни стали в круг лицом к центру, и каждый сказал путешественнику про соседа справа, рыцарь ли он. На основании этих сообщений путешественник смог однозначно определить количество лжецов и рыцарей в деревне. Сколько лжецов живёт в этой деревне?

Answer 1

13 т.к. если каждый лжец сказал каждому рыцарю что он лжец (тоесть 13) и каждый рыцарь сказал правду на лжецов (еще 13) и выходит что все лжецы тоесть 26:2=13

Answer 2

Пусть $R$ обозначает количество рыцарей, а $L$ - количество лжецов в деревне. Тогда $R+L=26$, так как в деревне 26 человек.

Каждый житель говорит про своего соседа справа, что он либо рыцарь, либо лжец. Обозначим через $r_i$ и $l_i$ соответственно, правдиво либо ложно сказал $i$-й человек о своем соседе справа.

Так как рыцари всегда говорят правду, то для каждого рыцаря $i$, его сосед справа либо рыцарь, либо лжец. Это означает, что $r_i$ равно либо 1, если сосед справа рыцарь, или 0, если сосед справа лжец. Аналогично, для каждого лжеца $j$ его сосед справа либо рыцарь, либо лжец, и поэтому $l_j$ равно либо 0, если сосед справа рыцарь, или 1, если сосед справа лжец.

Так как каждый человек может быть только либо рыцарем, либо лжецом, то $r_i+l_i=1$ для всех $i$. Это означает, что количество лжецов в деревне равно сумме всех значений $l_i$, так как каждый лжец $j$ даёт вклад 1 в эту сумму, а каждый рыцарь $i$ даёт вклад 0 в эту сумму.

Теперь нам нужно найти количество лжецов $L$. Заметим, что каждый житель говорит про своего соседа справа, поэтому мы можем просуммировать все значения $l_i$ и поделить на 2 (так как каждый лжец вносит в эту сумму свой вклад дважды - через ложное утверждение о своем соседе справа и через правдивое утверждение его соседа слева). Таким образом, мы получим:

$L=\frac{1}{2}\sum_{i=1}^{26}l_i=\frac{1}{2}\sum_{i=1}^{26}(1-r_i)=\frac{1}{2}(26-\sum_{i=1}^{26}r_i)$

Нам осталось только найти количество рыцарей $R$ в деревне. Общее количество рыцарей и лжецов в деревне равно 26, и мы знаем, что количество лжецов равно $\frac{1}{2}(26-\sum_{i=1}^{26}