Задача по алгебре Сто рыцарей, сто лжецов и сто болванов сидят за круглым столом в каком-то порядке. Рыцари всегда говорят правду, лжецы всегда лгут, а болваны всегда повторяют последнюю услышанную фразу. Каждый сказал одну из фраз: «Мой сосед справа - рыцарь», «Мой сосед справа - лжец» или «Мой сосед справа - болван», причём каждую следующую фразу говорил сидящий справа от того, кто сказал предыдущую фразу. Какое наибольшее количество фраз «Мой сосед справа - рыцарь» могло быть произнесено?
Для решения этой задачи рассмотрим поведение каждого типа участников:
Рыцари: всегда говорят правду. Если рыцарь говорит «Мой сосед справа - рыцарь», то сосед справа действительно рыцарь. Если он говорит, что сосед лжец или болван, то это тоже правда.
Лжецы: всегда лгут. Если лжец говорит «Мой сосед справа - рыцарь», то тот сосед на самом деле не рыцарь.
Болваны: повторяют последнюю услышанную фразу. Если болван слышит какую-либо из трех фраз, он повторяет эту фразу следующим.
Наша цель — максимизировать количество фраз «Мой сосед справа - рыцарь». Рассмотрим конструкцию:
Допустим, у нас есть последовательность из 100 участников, которые чередуются следующим образом: рыцарь, рыцарь, рыцарь, болван, болван, болван. Это будет выглядеть как:
Если начать с рыцаря и он скажет, что сосед справа — рыцарь, следующий будет еще один рыцарь, который также скажет, что сосед справа — рыцарь, и наконец, последний, кто будет болваном, который просто повторит «Мой сосед справа — рыцарь».
Таким образом, поведение участников можно выставить так, чтобы на каждый третий участник в среднем приходилось два рыцаря, каждые два из которых отвечают на вопрос, что их сосед — рыцарь. Позволив болванам повторять предполагаемую правду, мы окажемся с аккуратным числом произнесенных фраз «Мой сосед справа — рыцарь».
Если у нас будет 100 участников, из которых 66 будут рыцарями, 34 будут болванами, то болваны будут повторять фразы рыцарей. Таким образом, максимальное число произнесенных фраз «Мой сосед справа — рыцарь» будет равно 66. Поэтому итогом задачи является 66.
Для решения этой задачи рассмотрим поведение каждого типа участников:
Рыцари: всегда говорят правду. Если рыцарь говорит «Мой сосед справа - рыцарь», то сосед справа действительно рыцарь. Если он говорит, что сосед лжец или болван, то это тоже правда.
Лжецы: всегда лгут. Если лжец говорит «Мой сосед справа - рыцарь», то тот сосед на самом деле не рыцарь.
Болваны: повторяют последнюю услышанную фразу. Если болван слышит какую-либо из трех фраз, он повторяет эту фразу следующим.
Наша цель — максимизировать количество фраз «Мой сосед справа - рыцарь». Рассмотрим конструкцию:
Допустим, у нас есть последовательность из 100 участников, которые чередуются следующим образом: рыцарь, рыцарь, рыцарь, болван, болван, болван. Это будет выглядеть как:
Рыцарь (г.)Рыцарь (г.)Рыцарь (г.)Болван (р.)Болван (р.)Болван (р.)Рыцарь (г.)Если начать с рыцаря и он скажет, что сосед справа — рыцарь, следующий будет еще один рыцарь, который также скажет, что сосед справа — рыцарь, и наконец, последний, кто будет болваном, который просто повторит «Мой сосед справа — рыцарь».
Таким образом, поведение участников можно выставить так, чтобы на каждый третий участник в среднем приходилось два рыцаря, каждые два из которых отвечают на вопрос, что их сосед — рыцарь. Позволив болванам повторять предполагаемую правду, мы окажемся с аккуратным числом произнесенных фраз «Мой сосед справа — рыцарь».
Если у нас будет 100 участников, из которых 66 будут рыцарями, 34 будут болванами, то болваны будут повторять фразы рыцарей. Таким образом, максимальное число произнесенных фраз «Мой сосед справа — рыцарь» будет равно 66. Поэтому итогом задачи является 66.
Гена, читай условие. За столом не 100 человек.
Правильный ответ 299, решение после дурака писать не буду.