Назад
Задача

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

Ответ

Ответ задачи отсутствует

Чтобы оставлять комментарии, войдите или зарегистрируйтесь

Комментариев нет