Р 6. По кругу стоят N человек, пронумерованных по часовой стрелке от 1 до N. Первый, третий, пятый и так далее до конца нумерации сказали: «Мой сосед слева — рыцарь». Второй,…
Р 6. По кругу стоят N человек, пронумерованных по часовой стрелке от 1 до N. Первый, третий, пятый и так далее до конца нумерации сказали: «Мой сосед слева — рыцарь». Второй, четвёртый, шестой и так далее до конца нумерации сказали: «Мой сосед слева — лжец». Чему может быть равно число N? Соседом слева называется следующий по часовой стрелке человек. Выберите все возможные варианты: 21 43 32 54
Итак, обозначим K(i) — является ли i рыцарем (истинно говорящим).
Условия дают взаимные зависимости для соседей слева:
- для нечетного i: K(i-1) = K(i)
- для четного i: K(i-1) = не K(i)
Перенося по кругу от i=1, получаем последовательность (для произвольного x = K(1)): K(1) = x K(2) = ¬x K(3) = ¬x K(4) = x K(5) = x K(6) = ¬x K(7) = ¬x K(8) = x ... то есть период 4: x, ¬x, ¬x, x.
Условия замыкаются: если N чётное, K(N) должно равняться K(1); если N нечётное — K(N) должно быть ≠ K(1).
По нашей последовательности:
- N ≡ 0 mod 4: K(N) = x, тогда K(N) = K(1) — возможно.
- N ≡ 2 mod 4: K(N) = ¬x, несовпадение с K(1) — невозможно.
- N ≡ 1 mod 4: K(N) = x, требуется K(N) = ¬K(1) — невозможно.
- N ≡ 3 mod 4: K(N) = ¬x, требуется K(N) = ¬K(1) — возможно.
Следовательно, допускаются N ≡ 0 или N ≡ 3 (mod 4).
Теперь проверим варианты:
- 21 ≡ 1 mod 4 — нет
- 43 ≡ 3 mod 4 — да
- 32 ≡ 0 mod 4 — да
- 54 ≡ 2 mod 4 — нет
Ответ: 43 и 32.
