Задание №176867: Турнир городов

2. [4] Существует ли натуральное число, которое можно представить в виде
произведения двух палиндромов более чем 100 способами? (Палиндромом называется
натуральное число, которое одинаково читается как слева направо, так и справа

налево.)
(Е. Бакаев)
Ответ: существует. Рассмотрим палиндром 1 n = 1  ...1.
n
Способ 1. Если n кратно k, то 1 делится на палиндром 1 , причём частное – тоже
n k
палиндром, состоящий из единиц, разделённых группами из k – 1 нуля. Осталось
выбрать число n, имеющее более 100 собственных делителей. Например, 2101.
Замечание. Число 6 делится не только на 1 , но и на 2 , 3 и 6 . Это позволяет
n k k k k
уменьшить n до числа, имеющего более 25 собственных делителей, например, годится
n = 720 = 24325.
Идея способа 2. Заметим, что если при умножении палиндромов не происходит
переносов из одного разряда в другой, то произведение – тоже палиндром. Рассмотрим
произведение 1110110  ...0110  ...0110  ...0110  ...0110  ...0110  ...01 = 1 256 . Можно доказать, что
3 7 15 31 63 127
при умножении любого числа этих сомножителей переносов не происходит и
получается палиндром из нулей и единиц. Поскольку 8 множителей можно 27 = 128
способами разбить на две группы, можно получить 128 различных (поскольку
множители взаимно просты) представлений числа 1 в виде произведения двух
256
палиндромов.
Замечание 2. Соображения из замечания к способу 1 показывают, что годится
число 6 . Можно показать, что подходит даже число
64
11 ⋅ 101 ⋅ 1001 ⋅ 10⏟.. .01 ⋅ 10⏟. ..0 1 ⋅ 10⏟...01 ⋅ 10⏟.. .01 ⋅ 1 0⏟.. .01.
3 4 5 6 7