Палиндромные суммы числа 26

Где может находиться середина палиндрома: между слагаемыми или на одном из них? Чем отличаются эти два случая?

Если отдельного центра нет, какую сумму даёт левая половина? Если центр есть, может ли там стоять 1 при чётной общей сумме?

1. Сначала увидим два вида симметрии

Для иллюстрации возьмём меньшую сумму — $8$, а не $26$.

В сумме $1+2+1+1+2+1$ середина проходит между двумя единицами. Слева стоят $1,2,1$, справа — те же числа в обратном порядке. Отдельного центрального слагаемого нет.

В сумме $1+2+2+2+1$ есть центральная двойка. Слева от неё стоят $1,2$, справа — $2,1$.

В обоих случаях достаточно выбрать левую половину: правая после этого определяется однозначно, потому что должна зеркально её повторить. Теперь применим это к сумме $26$.

2. Два случая для суммы 26

Без центрального слагаемого. Обе половины имеют одинаковую сумму, поэтому на левую приходится

$$\frac{26}{2}=13.$$

Любую упорядоченную сумму $13$ из единиц и двоек можно дописать справа в обратном порядке. Получится ровно один палиндром с чётным числом слагаемых.

С центральным слагаемым. Все слагаемые вне центра образуют равные пары, поэтому их общая сумма чётна. Центральная единица дала бы нечётную полную сумму, а у нас $26$. Значит, в центре обязательно стоит $2$; на левую половину приходится

$$\frac{26-2}{2}=12.$$

Любая упорядоченная сумма $12$ после центральной двойки и зеркального повторения даёт ровно один палиндром с нечётным числом слагаемых.

Обратно, у каждого палиндрома левая половина выделяется однозначно. Два случая не пересекаются: число слагаемых в них разной чётности. Значит, осталось сложить количества упорядоченных сумм $13$ и $12$.

3. Как считать упорядоченные суммы

Каждая сумма из единиц и двоек заканчивается либо единицей, либо двойкой. Если убрать последнюю единицу, останется сумма на $1$ меньше. Если убрать последнюю двойку — на $2$ меньше. Обратно, к любой из таких более коротких сумм можно дописать соответствующее последнее слагаемое. Эти две группы не пересекаются и охватывают все варианты.

Теперь обозначим число упорядоченных сумм $n$ через $A_n$. Рассуждение даёт при $n\ge2$ рекуррентную формулу:

$$A_n=A_{n-1}+A_{n-2}.$$

Для суммы 1 есть только запись $1$, поэтому $A_1=1$. Для суммы 2 есть записи $1+1$ и $2$, поэтому $A_2=2$.

Чтобы формула учитывала и запись из одной двойки, положим $A_0=1$: после удаления этой двойки остаётся пустая запись. Не записать ни одного слагаемого — единственный способ получить сумму 0. Теперь равенство $A_2=A_1+A_0$ совпадает с прямым перечислением.

Каждое следующее число — сумма двух предыдущих. Например, $A_2=1+1=2$, $A_3=2+1=3$. Продолжаем до $13$.

4. Складываем два случая

Без центрального слагаемого получаем $A_{13}=377$ палиндромов, с центральной двойкой — $A_{12}=233$. Искомое число равно

$$377+233=610.$$

Центральная двойка не является парой двоек: эти варианты имеют разное число слагаемых и уже учтены в разных случаях.

$610$

Палиндром однозначно задаётся левой половиной и, при нечётной длине, центральным слагаемым.

В задачах о симметричной последовательности сначала определите свободную половину и отдельно проверьте ограничения на центр.

Считать только зеркальное удвоение суммы $13$ — значит пропустить палиндромы с нечётным числом слагаемых и центральной двойкой.

Для палиндромной суммы другого чётного числа $2m$ действует тот же разбор: левая половина имеет сумму $m$ без центра и $m-1$ при центральной двойке. Для нечётной общей суммы сначала заново определите допустимый центр.