Задача по алгебре Сто рыцарей, сто лжецов и сто болванов
сидят за круглым столом в каком-то
порядке. Рыцари всегда говорят правду,
лжецы всегда лгут, а болваны всегда
повторяют последнюю услышанную фразу.
Каждый сказал одну из фраз: «Мой сосед
справа - рыцарь», «Мой сосед справа -
лжец» или «Мой сосед справа - болван»,
причём каждую следующую фразу говорил
сидящий справа от того, кто сказал
предыдущую фразу. Какое наибольшее
количество фраз «Мой сосед справа -
рыцарь» могло быть произнесено?

Предыдущий
вопрос Следующий
вопрос

Для решения этой задачи рассмотрим поведение каждого типа участников:

Рыцари: всегда говорят правду. Если рыцарь говорит «Мой сосед справа - рыцарь», то сосед справа действительно рыцарь. Если он говорит, что сосед лжец или болван, то это тоже правда.

Лжецы: всегда лгут. Если лжец говорит «Мой сосед справа - рыцарь», то тот сосед на самом деле не рыцарь.

Болваны: повторяют последнюю услышанную фразу. Если болван слышит какую-либо из трех фраз, он повторяет эту фразу следующим.

Наша цель — максимизировать количество фраз «Мой сосед справа - рыцарь». Рассмотрим конструкцию:

Допустим, у нас есть последовательность из 100 участников, которые чередуются следующим образом: рыцарь, рыцарь, рыцарь, болван, болван, болван. Это будет выглядеть как:

Если начать с рыцаря и он скажет, что сосед справа — рыцарь, следующий будет еще один рыцарь, который также скажет, что сосед справа — рыцарь, и наконец, последний, кто будет болваном, который просто повторит «Мой сосед справа — рыцарь».

Таким образом, поведение участников можно выставить так, чтобы на каждый третий участник в среднем приходилось два рыцаря, каждые два из которых отвечают на вопрос, что их сосед — рыцарь. Позволив болванам повторять предполагаемую правду, мы окажемся с аккуратным числом произнесенных фраз «Мой сосед справа — рыцарь».

Если у нас будет 100 участников, из которых 66 будут рыцарями, 34 будут болванами, то болваны будут повторять фразы рыцарей. Таким образом, максимальное число произнесенных фраз «Мой сосед справа — рыцарь» будет равно 66. Поэтому итогом задачи является 66.