С какой открытой проблемой связана данная задача?

[Xenia1996]

Задача:
Назовём палиндромом по основанию $b$ натуральное число, являющееся палиндромом в $b$- ричной системе счисления (в дальнейшем буду писать "в базе $b$" (калькой с инглиша), так просто короче).
Докажите, что для каждого натурального числа $n$ существует натуральное число $m$, являющееся трёхзначным палиндромом по крайней мере по $n$ различным основаниям.

Источник задачи: Putnam Competition, 2002, problem B5 (во как!).

Оригинальный текст задачи:
[Putnam 2002:B5] A palindrome in base b is a positive integer whose base b-digits read the same backwards and forwards; for example, 2002 is a 4-digit palindrome in base 10. Note that 200 is not a palindrome in base 10, but it is the 3-digit palindrome 242 in base 9, and 404 in base 7. Prove that there is an integer which is a 3-digit palindrome in base b for at least 2002 different values of b.

Ссылка на задачу: http://www.math.harvard.edu/putnam/2002/index.html

Моя первая идея решения (основанная на том, что если число равно 121 по основанию $b$, то это число - квадрат, так как равно $b^2+2b+1=(b+1)^2$ ):
Рассмотрим квадраты факториалов натуральных чисел, как они себя ведут.
Скажем, $(3!)^2=36$ будет выгладеть так:
121 в базе 5, 484 в базе 2...Так, стоп-машина! В базе 2 нет четвёрок и восьмёрок! Зато есть хорошая новость: начиная с $n=6$ эта проблема перестанет нас тревожить, ибо $119>72$ и в дальнейшем это свойство имеет свойство сохраняться.
Так что покамест можно помечтать о том, что в базе 2 таки-есть 4-ки и 8-ки. Можно ведь залезть в коробку и представить, что ты в танке.

$(4!)^2=576$ будет выгладеть так:
121 в базе 23, 484 в базе 11, 9[18]9 в базе 7 (опять в танке ).

$(5!)^2=14400$ будет выгладеть так:
121 в базе 119, 484 в базе 59, 9[18]9 в базе 39, [16][32][16] в базе 29 (последний раз в танке ).

$(6!)^2=518400$ будет выгладеть так:
121 в базе 719, 484 в базе 359, 9[18]9 в базе 239, [16][32][16] в базе 179, [25][50][25] в базе 143 и [36][72][36] в базе 119 (ура! танки больше не нужны! да здравствует пацифизм! Легко доказать по индукции, что для любого натурального $n>5$ выполняется $(n-1)!-1>2n^2$).

Таким образом, начиная с $n=6$, $(n!)^2$ будет выглядеть следующим образом:
121 в базе $n!-1$, 484 в базе $n!/2-1$, 9[18]9 в базе $n!/3-1$, ..., $[n^2][2n^2][n^2]$ в базе $(n-1)!-1$
Следовательно, квадрат факториала натурального числа $n$ (большего 5), является трёхзначним палиндромом хотя бы в $n$ различных базах.

Моя вторая идея решения (но мне не удалось довести её до ума):
Я хотела взять такое натуральное число, которое будет 101 в какой-нибудь базе, 202 в другой базе, 303 в ещё какой-нибудь и т.д.
Для этого я попыталась найти такое $n$, что $n-1$ будет квадратом, $n-2$ - удвоенным квадратом, $n-3$ - утроенным квадратом, ...
Но не смогла

А теперь - вопрос: с какой открытой проблемой связана данная задача?
Где-то когда-то я вычитала, что существует некая открытая проблема с палиндромами, очень похожая на представленную только что здесь. Хотелось бы знать.

[Хорхе]

Нагуглил такую гипотезу (которая, впрочем, не имеет никакого отношения к данной задаче):

Стартуют с произвольного числа, например 196. Переворачивают и складывают: 196+691 = 887. Переворачивают и складывают: 887+788 = 1665. И так далее.

Гипотеза состоит в том, что в этой последовательности обязательно встретится палиндром. Ну и 196 -- как раз наименьшее число, для которого палиндром не нашли, дойдя до многомиллиардоцифровых чисел (там забросили, потому что дальше мало смысла).

Короче, гипотеза, которая (как по мне) очевидно неверна, но которую очень сложно опровергнуть (и еще сложнее доказать). Ну это как нормальность числа $\pi$, к примеру. Понятно, что она имеет место, но как доказать, никто не знает.

[Xenia1996]

(Оффтоп)

Хорхе в сообщении #383129 писал(а):

Нагуглил такую гипотезу

Я её тоже нагуглила. Но никакая идея на ум не приходит. А так хочется какую-нибудь открытую проблему решить!
Месяц назад я и не помышляла о том, чтобы Патнэмы решать. Но 24 ноября сего года таки-решила Патнэм (правда, он был очень изи). А вот сегодня - совсем не изи (целых B5!!!)...

(Оффтоп)

А как Вам моя попытка решения?

[VAL]

С первой задачкой - все верно.
(Единстевнное, чего я не понял: причем там танк )

Xenia1996 в сообщении #383113 писал(а):

Моя вторая идея решения (но мне не удалось довести её до ума):
Я хотела взять такое натуральное число, которое будет 101 в какой-нибудь базе, 202 в другой базе, 303 в ещё какой-нибудь и т.д.
Для этого я попыталась найти такое $n$, что $n-1$ будет квадратом, $n-2$ - удвоенным квадратом, $n-3$ - утроенным квадратом, ...
Но не смогла

А теперь - вопрос: с какой открытой проблемой связана данная задача?
Где-то когда-то я вычитала, что существует некая открытая проблема с палиндромами, очень похожая на представленную только что здесь. Хотелось бы знать.

А какая тут проблема?
Нету таких чисел. Даже без многоточия.
Пусть $n-1=x^2, \ n-2 = 2y^2, \ n-3 = 3z^2 $. Тогда $(x, y)$ - решение уравнение Пелля $x^2-2y^2=1$ (куда ж без него?) и $(x, z)$ - решение обобщенного уравнение Пелля $x^2-3y^2=2$. Первое уравнение, как известно, имеет бесконечно много решений. А вот второе, увы, не разрешимо :(

[Xenia1996]

VAL в сообщении #383248 писал(а):

С первой задачкой - все верно.
(Единстевнное, чего я не понял: причем там танк )


А какая тут проблема?
Нету таких чисел. Даже без многоточия.
Пусть $n-1=x^2, \ n-2 = 2y^2, \ n-3 = 3z^2 $. Тогда $(x, y)$ - решение уравнение Пелля $x^2-2y^2=1$ (куда ж без него?) и $(x, z)$ - решение обобщенного уравнение Пелля $x^2-3y^2=2$. Первое уравнение, как известно, имеет бесконечно много решений. А вот второе, увы, не разрешимо :(

Танк - это по Жванецкому (если память мне не изменяет).
А насчёт Пелля - и вправду не дотумкала (вроде "не" перед глаголом пишется отдельно (с другой стороны, а как же слово "недоспать"?)).
Когда я спрашивала "с какой открытой проблемой связана данная задача", под "данной задачей" я подразумевала именно этот самый Патнэм, а не только вторую идею его решения.

[Хорхе]

(Оффтоп)

Xenia1996 в сообщении #383302 писал(а):

А насчёт Пелля - и вправду не дотумкала (вроде "не" перед глаголом пишется отдельно (с другой стороны, а как же слово "недоспать"?)).

В "недоспать" приставка "недо-", а не частица "не" и приставка "до-", как в "не дотумкала".