Question

По кругу стоят 181 человек, каждый из которых либо рыцарь, либо лжец (лжецы всегда лгут, а рыцари всегда говорят правду). Каждый из стоявших сказал: «Через одного человека от меня есть лжец». Найдите минимальное возможное число лжецов среди этих 181 человек. (с объяснением пожалуйста)

Answer 1

Разобьем всю группу из 181 человек на подгруппы из шести человек в каждой. Так как 181 = 6*30 + 1, то всего таких подгрупп будет шесть плюс еще один человек. Обозначим лжецов заглавной буквой Л, а рыцарей - заглавной Р. Рассмотрим одну из подгрупп из шести человек. Расположим их в ряд. Ясно, что минимум один из этой шестерки лжец. Предположим вначале, что он единственный, пусть он для определенности идет вторым в подгруппе и рассмотрим ряд РЛРРРР. Если второй лжец, то четвертый член ряда рыцарь, так как единственный лжец находится через одного от него. Но, тогда в подгруппе должен присутствовать как минимум еще один лжец. Расположим его под номером три. Получаем ряд РЛЛРРР. Тогда пятый член ряда рыцарь, так как третий, через одного от него лжец. Первый и шестой в ряду тоже оказываются рыцарями, так как следом идет очередная шестерка РЛЛРРР  РЛЛРРР. Следовательно в каждой шестерке человек минимум два лжеца. Таких подгрупп из шести человек у нас 30, плюс еще один человек, то есть получаем ряд по кругу РЛЛРРР  РЛЛРРР  ......  РЛЛРРЛ  Р. В последней шестерке присутствует еще один лжец на шестой позиции. Последний также оказывается рыцарем, так как все стоят по кругу. В итоге общее минимальное количество лжецов будет равно 2*30 + 1 = 61.

Ответ: 61

Answer 2

Рассмотрим два случая: когда первый человек в кругу - рыцарь, и когда он - лжец.

1. Первый человек в кругу - рыцарь

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

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

Итого получаем, что минимальное число лжецов в этом случае равно 91 (половина от 181).

2. Первый человек в кругу - лжец

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

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

Итого получаем, что минимальное число лжецов в этом случае также равно 91.

Таким образом, минимальное возможное число лжецов среди этих 181 человек равно 91.