Question

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

Answer 1

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

Answer 2

Давайте рассмотрим возможные варианты расположения лжецов и рыцарей в кругу.

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

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

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

Таким образом, минимальное возможное число лжецов среди этих 181 человек будет равно половине от общего числа, то есть 90.5. Однако, так как количество людей должно быть целым числом, то минимальное число лжецов будет 91.