Метод спуска, индукция и последовательное конструирование в ТЧ

Для и цифр нетрудно придумать примеры Для большего количества цифр индукцией по покажем, что число вида ( девяток) подходит. В справедливости базы убедиться несложно. Предположим, что это верно для такого числа с . Это означает, что при прибавлении к девяткам на следующий разряд после последней переходит Но тогда если в числе девятка, то единица перейдёт в последнюю девятку, от которой в следующий разряд с перейдёт и будет число вида ( ноль).

Покажем, что трёх цифр быть не могло. Предположим, что нашлось такое число что — палиндром. Ясно, что последняя цифра равна значит и первая равна Если число трёхзначное, то такого быть не может, потому что цифра сотен будет явно больше Предположим, что — четырёхзначное. Предположим, что при сложении и не было переноса с второго разряда на третий. В этом случае число будет четырёхзначным только если но тогда оно точно не палиндром. Предположим, что с второго разряда на третий перенесли тогда будет четырёхзначным, если В обоих случаях не палиндром.