В комнате за круглым столом сидят 9 человек: рыцари, говорящие всегда правду, и лжецы, лгущие всегда. Каждый из них сказал: «Мои соседи – лжец и рыцарь». Сколько всего рыцарей за столом?
В комнате за круглым столом сидят 9 человек: рыцари, говорящие всегда правду, и лжецы, лгущие всегда. Каждый из них сказал: «Мои соседи – лжец и рыцарь». Сколько всего рыцарей за столом?
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки в течение 1 года
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Поможем написать учебную работу
Варианты: (0) или (6).
Краткое обоснование. Обозначим рыцаря как (1), лжеца как (0). Условие каждого: если (ai=1), то (a{i-1}) и (a_{i+1}) различны; если (ai=0), то они равны. Значит
[
a{i+1}=a_{i-1}\oplus ai,
]
или в арифметике по модулю (2): (a{i+1}+ai+a{i-1}=0). Это линейное рекуррентное соотношение над (\mathbb F_2) даёт период (3) для ненулевых начальных данных, поэтому последовательность по кругу разбивается на три одинаковых блока длины (3). Для любых ненулевых ((a_1,a_2)) в блоке ((a_1,a_2,a_1\oplus a_2)) ровно два единицы, значит при (9) людях будет (2\cdot3=6) рыцарей. Ещё возможен тривиальный случай все нули (все лжецы) — (0) рыцарей. Если известно, что есть хотя бы один рыцарь, то количество равно (6).