|
|
 |
Условие
Существует ли натуральное число, которое можно представить в виде произведения двух палиндромов более чем 100 способами? (Палиндромом называется натуральное число, которое одинаково читается как слева направо, так и справа налево.)Решение
Существует. Рассмотрим палиндром из $n$ единиц $1_n = 1...1$.Способ 1. Если $n$ кратно $k$, то $1_n$ делится на палиндром $1_k$, причём частное — тоже палиндром, состоящий из единиц, разделённых группами из $k-1$ нуля. Осталось выбрать число $n$, имеющее более 100 собственных делителей. Например, $2^{101}$.
Замечание. Число $6^n$ делится не только на $1_k$, но и на $2_k$, $3_k$ и $6_k$. Это позволяет уменьшить $n$ до числа, имеющего более 25 собственных делителей, например, годится $n = 720 = 2^4\cdot 3^2\cdot 5$.
Идея способа 2. Заметим, что если при умножении палиндромов не происходит переносов из одного разряда в другой, то произведение – тоже палиндром. Рассмотрим произведение $$11 \cdot 101 \cdot 1\underbrace{0...0}_{3}1 \cdot 1\underbrace{0...0}_{7}1 \cdot 1\underbrace{0...0}_{15}1 \cdot 1\underbrace{0...0}_{31}1 \cdot 1\underbrace{0...0}_{63}1 \cdot 1\underbrace{0...0}_{127}1 = 1_{256}.$$ Можно доказать, что при умножении любого числа этих сомножителей переносов не происходит и получается палиндром из нулей и единиц. Поскольку 8 множителей можно $2^7 = 128$ способами разбить на две группы, можно получить 128 различных (поскольку множители взаимно просты) представлений числа $1_{256}$ в виде произведения двух палиндромов.
Замечание 2. Соображения из замечания к способу 1 показывают, что годится число $6_{64}$. Можно показать, что подходит даже число $$ 11\cdot 101\cdot 1001 \cdot 1\underbrace{0...0}_{3}1 \cdot 1\underbrace{0...0}_{4}1 \cdot 1\underbrace{0...0}_{5}1 \cdot 1\underbrace{0...0}_{6}1 \cdot 1\underbrace{0...0}_{7}1. $$
