Question

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

Answer 1

Максимальное количество правдивых гоблинов - 56.

По одному с каждого края и далее - через одного.

По условию, справа и слева от каждого правдивого должны стоять лжецы.

Иначе правдивые солгут.

Справа и слева от каждого лжеца должны стоять правдивые.

Иначе лжецы скажут правду.

Возможно чередование, когда вначале и в конце стоят лжецы. Условие будет соблюдено, однако, в этом случае лжецов будет на 1 больше, чем правдивых. 

То есть максимальное количество правдивых:

             111 = 110 + 1 = 55*2 + 1 = 56 + 55

56 правдивых гоблинов и 55 лжецов.  

Answer 2

Давайте рассмотрим два случая: один, когда гоблины, находящиеся на краях, говорят правду, и другой, когда гоблины на краях лгут.

1. Первый случай: Краевые гоблины говорят правду.

Если крайние гоблины говорят правду, то у них нет лживых соседей. Значит, два крайних гоблина всегда говорят правду. Остается 109 гоблинов внутри шеренги. Теперь давайте рассмотрим гоблинов внутри шеренги:

• Внутри шеренги каждый гоблин имеет двух соседей.
• Поскольку крайние гоблины говорят правду, значит, их соседи внутри шеренги оба лгут.

Теперь представим, что внутри шеренги есть N гоблинов, которые говорят правду. Тогда оставшиеся (109 - N) гоблинов будут лгать. Из условия известно, что каждый гоблин имеет двух соседей. Поскольку гоблины, говорящие правду, не могут иметь соседей, которые также говорят правду, то (109 - N) гоблинов, которые лгут, должны иметь двух соседей, говорящих правду.

Таким образом, у нас есть следующее уравнение:

2 * (109 - N) = N

Решая его, мы получаем:

218 - 2N = N

218 = 3N

N = 218 / 3

N = 72.6667

Поскольку количество гоблинов должно быть целым числом, наибольшее количество гоблинов, говорящих правду в данном случае, составляет 72.

2. Второй случай: Краевые гоблины лгут.

Если крайние гоблины лгут, то у них оба соседа говорят правду. Это означает, что крайние гоблины не могут быть правдивыми.

Таким образом, в этом случае наибольшее количество гоблинов, говорящих правду, составляет 0.

Итак, наибольшее количество правдивых гоблинов в шеренге равно 72 в первом случае, когда крайние гоблины говорят правду.