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