Question

На далеком острове живут вегетарианцы (В), которые всегда говорят правду, и каннибалы (К), которые всегда лгут. Как то раз вегетарианец и еще несколько жителей острова выстроились в ряд и каждый сказал: "Все вегетарианцы стоят от меня через простое число человек". Сколько жителей острова могло выстроиться в ряд?

Answer 1

А к.........................................................

Answer 2

Предположим, что в ряд выстроилось N жителей острова. Пусть первый человек в ряду обозначен как A.

Если A - вегетарианец (В), то он говорит правду. Поэтому все люди, находящиеся на простом расстоянии от A (2, 3, 5, 7, ...) также должны быть вегетарианцами. Всего таких людей будет pi(N), где pi(N) - функция, возвращающая количество простых чисел, не превышающих N.

Если A - каннибал (К), то он всегда лжет. Это означает, что никакой человек на расстоянии 1 от A не может быть вегетарианцем, так как A лгал бы. Следовательно, A+1 - каннибал, и он также лжет о том, что все вегетарианцы стоят от него через простое число человек. Таким образом, ни один человек на расстоянии 1 или 2 от A не может быть вегетарианцем.

Обобщая, можно сказать, что четные позиции от A (4, 6, 8, ...) содержат каннибалов (К), а нечетные позиции (3, 5, 7, ...) содержат вегетарианцев (В).

Теперь рассмотрим случай, когда A - вегетарианец. Мы знаем, что все люди на простом расстоянии от A также вегетарианцы. Расстояние между соседними вегетарианцами будет 2, 4, 6, 8, ..., и так далее. Если N - четное число, то сам A находится на нечетной позиции, и количество вегетарианцев будет равно N/2. Если N - нечетное число, то сам A находится на четной позиции, и количество вегетарианцев будет равно (N-1)/2.

Теперь рассмотрим случай, когда A - каннибал. Мы знаем, что никакой человек на расстоянии 1 или 2 от A не может быть вегетарианцем. Таким образом, первый вегетарианец будет находиться на позиции 3 или 4 в ряду, в зависимости от того, является ли A-каннибалом на четной или нечетной позиции. Количество вегетарианцев в этом случае будет равно (N-1)/2.

Итак, общая формула для количества вег