Задача
Существует ли натуральное число, которое можно представить в виде произведения двух палиндромов более чем 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. $$
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь