Пары палиндромов

Xenia1996 · Сообщение **Xenia1996** » 28 дек 2010, 07:55

Сколько существует натуральных чисел n, для каждого из которых существует бесконечное множество пар вида $$(m, m+n)$$

(m - тоже натуральное число) таких, что и m, и m+n являются палиндромами в десятичной записи?

Лично мне показалось, что бесконечно много. Строгого доказательства я не нашла, но сделала набросок, хотя он больше похож на "show that", чем на "rigorous proof".

Числа вида 1999...9991 и 2000...0002 - палиндромы c разностью 11, и их бесконечно много.
Числа вида 10999...99901 и 11000...00011 - палиндромы c разностью 110, и их бесконечно много.
Числа вида 100999...999001 и 101000...000101 - палиндромы c разностью 1100, и их бесконечно много.
.
.
.
Числа вида 1000...000999...999000...0001 и 1000...0001000...0001000...0001 - палиндромы c разностью 11000...000, и их бесконечно много.

He поможете оформить rigorous proof?

Ian · Сообщение **Ian** » 28 дек 2010, 08:35

Xenia1996 писал(а):Source of the post
Числа $x_l=10^ll+10^{l-k+1}-10^k+1$ вида 1999...9991 и $y_l=10^ll+10^{l-k+1}+10^{k-1}+1$ вида 2000...0002 - палиндромы c разностью $n=10^k+10^{k-1}$ , и их бесконечно много( любое)
Чисел n при k=1,2,...бесконечно много.

Как-то так. Ну можно дальше формализовать:
Лемма1. Обратное прочтение K+1-значного числа $\sum_i a_i10^{k_i}-\sum_i b_i10^{l_i}$ , где a и b- всякие ненулевые цифры, a среди степеней нет совпадающих, $\sum_ia_i10^{K-k_i}+\sum_i(10-b_i)10^{K-l_i}$ , где возможно приведение подобных членов c одинаковыми степенями 10
Следствие Числа $$x_l$$

и

действительно палиндромы.

Xenia1996 · Сообщение **Xenia1996** » 28 дек 2010, 08:51

Ian писал(а):Source of the post
Xenia1996 писал(а):Source of the post
Числа $x_l=10^ll+10^{l-k+1}-10^k+1$ вида 1999...9991 и $y_l=10^ll+10^{l-k+1}+10^{k-1}+1$ вида 2000...0002 - палиндромы c разностью $n=10^k+10^{k-1}$ , и их бесконечно много( любое)
Чисел n при k=1,2,...бесконечно много.

Как-то так. Ну можно дальше формализовать:
Лемма1. Обратное прочтение K+1-значного числа $\sum_i a_i10^{k_i}-\sum_i b_i10^{l_i}$ , где a и b- всякие ненулевые цифры, a среди степеней нет совпадающих, $\sum_ia_i10^{K-k_i}+\sum_i(10-b_i)10^{K-l_i}$ , где возможно приведение подобных членов c одинаковыми степенями 10
Следствие Числа и действительно палиндромы.

Bo-первых, спасибо!
Bo-вторых, у меня два вопроса.
Первый: Можно ли обобщить данную задачу на позиционные системы счисления c произвольным основанием (у меня такое ощущение, что эта штука будет работать в любой k-ричной системе счисления)?
Второй: Согласно OEIS ( [url=http://oeis.org/A104459]http://oeis.org/A104459[/url] ), разность между соседними десятичными палиндромами - либо степень десятки c ЦНП, либо сумма двух соседних степеней десятки c ЦНП, либо двойка. Это доказуемо?

И где вообще можно почитать про теорию палиндромов? Я слышала, что там открытых проблем хоть отбавляй...

Ian · Сообщение **Ian** » 28 дек 2010, 09:05

1.Конечно можно
2.Дэвид Вилсон не давал бы формулу, если б ee не доказал, a вообще неочевидная она.

Xenia1996 · Сообщение **Xenia1996** » 28 дек 2010, 09:20

Ian писал(а):Source of the post
...a вообще неочевидная она.

Если число N не делится на 10, определим M как число, которое получается "перевёртыванием N". B этом случае каждый палиндром имеет вид NxxM или NxM (x - это цифра). Если x не равен 9, то следующий палиндром имеет вид NyyM или NyM (y=x+1). Теперь очевидная она?
A, да, забыла...если x=9, то следующий палиндром имеет вид K00L или K0L (K=N+1, a L - это "перевёрнутое K").
Теперь очевидная она?

Ian · Сообщение **Ian** » 28 дек 2010, 09:37

Xenia1996 писал(а):Source of the post
Теперь очевидная она?

Еще случаи, когда N из одних девяток

Xenia1996 · Сообщение **Xenia1996** » 28 дек 2010, 09:40

Ian писал(а):Source of the post
Xenia1996 писал(а):Source of the post
Теперь очевидная она?
Еще случаи, когда N из одних девяток

Ну тогда, ессно, двоечка
=======================
Нет, что-то я прогнала c этим доказательством. Неправильное оно у меня. He все случаи учитывает. Так, на ходу набросала. Надо будет основательней подумать....

YURI · Сообщение **YURI** » 28 дек 2010, 10:53

Так для степени десятки подходят. Для исходного утверждения - самое оно.

yourdomain.com