На гирлянде несколько лампочек расположены в ряд. Гирлянду запрограммировали менять состояние лампочек каждую секунду следующим образом: лампочка на гирлянде горит в следующую…

Ответ: 30 лампочек.

Пошаговое решение

• Обозначения. Пусть на гирлянде N лампочек в ряд. Обозначим состояние i-й лампочки в текущий момент как a_i ∈ {0,1} (1 — горит, 0 — не горит).

• Правило обновления. В следующую секунду лампочка горит (a_i' = 1), если среди соседей i (для interior: i-1 и i+1; для крайних — единственный сосед) было 0 или 2 горящих, в противном случае она гаснет (a_i' = 0). При этом изменение идёт независимо от текущего состояния самой лампочки.

• Найдём стационарное состояние (фиксированную конфигурацию), для которой a_i' = a_i для всех i.

• Границы:

  • для левой границы (i = 1) у неё есть один сосед: a_2. Чтобы a_1 = a_1', требуется: • если a_1 = 1, то сосед a_2 = 0; • если a_1 = 0, то сосед a_2 = 1. Отсюда выплывает отношение: a_2 = 1 − a_1.

• Далее для внутренних лампочек (2 ≤ i ≤ N−1) выполняется правило: a_i' = 1 тогда, когда a_{i-1} = a_{i+1}. Чтобы a_i' = a_i, имеем:

  • если a_i = 1, то a_{i-1} = a_{i+1};
  • если a_i = 0, то a_{i-1} ≠ a_{i+1}.

• Применяя это к i = 2 и зная a_2 = 1 − a_1, получаем последовательно:

  • a_3 = 0;
  • a_4 = a_1;
  • a_5 = 1 − a_1;
  • a_6 = 0;
  • a_7 = a_1;
  • a_8 = 1 − a_1;
  • … То выходит общая формула: конфигурация повторяется с периодом 3: a_i = a_1, если i ≡ 1 (mod 3); 1 − a_1, если i ≡ 2 (mod 3); 0, если i ≡ 0 (mod 3).

• Правдивость правой границы. Правила дают дополнительное условие: a_{N−1} = 1 − a_N. В зависимости от N mod 3 это приводит к ограничениям на a_1:

  • если N ≡ 1 (mod 3), тогда a_1 = 1;
  • если N ≡ 0 (mod 3), тогда a_1 = 0;
  • если N ≡ 2 (mod 3), допустимы оба значения a_1.

• Число горящих лампочек (число единиц) в такой конфигурации:

  • если a_1 = 1 (то конфигурация на позиции i ≡ 1 (mod 3) горит): число единиц равно ceil(N/3);
  • если a_1 = 0 (то конфигурация на позициях i ≡ 2 (mod 3) горит): число единиц равно floor((N+1)/3).

• Требование: можно зажечь ровно 10 лампочек. Нужно найти максимум N, для которого существует такая фиксированная конфигурация с ровно 10 единиц.

  • для N ≡ 1 (mod 3): ceil(N/3) = 10 дает N ∈ {28, 29, 30}, но по условию границы для N ≡ 1 (mod 3 допускается a_1 = 1, и максимальное допустимое здесь N = 28 с a_1 = 1}.
  • для N ≡ 2 (mod 3): оба a_1 допустимы. возм. N = 29 даёт 10 единиц.
  • для N ≡ 0 (mod 3): floor((N+1)/3) = 10 дает N = 30 (и далее N = 33 даст 11).

  Из всех вариантов наибольшее N равно 30. При N = 30 допустима фиксированная конфигурация с a_1 = 0, которая имеет exactly 10 горящих лампочек.

• Пример конфигурации для N = 30 (a_1 = 0):

  • паттерн: [0, 1, 0] повторяется.
  • горящие лампочки на позициях: 2, 5, 8, 11, 14, 17, 20, 23, 26, 29 (то есть i ≡ 2 (mod 3)).
  • Это действительно фиксированная конфигурация: крайние лампочки соблюдают границы, interior соблюдают правило.

Итог: максимальное возможное количество лампочек на гирлянде, при котором можно изначально зажечь ровно 10 лампочек и все лампочки будут этих же состояний при описанной программе, равно 30.