На гирлянде несколько лампочек расположены в ряд. Гирлянду запрограммировали менять состояние лампочек каждую секунду следующим образом: лампочка на гирлянде горит в следующую секунду, если до этого горели 0 или 2 из соседних с ней лампочек, в противном случае лампочка в следующую секунду не горит. На гирлянде можно изначально зажечь 10 лампочек таким образом, чтобы все лампочки не меняли своего состояния, следуя описанной программе. Сколько всего лампочек может быть быть на на гирлянде?.

Ответ: 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.