Одна задача с XIII Кубка памяти Колмлгорова

[nnosipov]

Хотелось бы видеть оригинальное решение следующей задачи.

Множество значений многочлена $Q(x)$ в целых точках содержит все числа Фибоначчи $F_n$, а все его коэффициенты являются целыми. Найдите все такие многочлены $Q(x)$.

[Xenia1996]

nnosipov в сообщении #435388 писал(а):

Хотелось бы видеть оригинальное решение следующей задачи.

Множество значений многочлена $Q(x)$ в целых точках содержит все числа Фибоначчи $F_n$, а все его коэффициенты являются целыми. Найдите все такие многочлены $Q(x)$.

По-моему, та же идея, что и в этой задаче.

[Sonic86]

Кажется, такого многочлена нет, кроме тривиального $Q(x)=x$, а жаль.
Пусть $Q(x):Q(x_n)=F_n$, причем $Q(0)=1=F_1=F_2$. Тогда свободный член многочлена равен 1 и поскольку все коэффициенты целые, то $Q(x_n)=F_n \Leftrightarrow x_nR(x_n)=F_n-1$, где $R(x)=\frac{Q(x)-1}{x}$. Нетрудно найти, что $x_3=1$, откуда поскольку $x_4>x_3$ будет $x_4=2$. Докажем по индукции, что $x_n=F_n-1$. Для $n=3;4$ - верно. $Q(x_{n+1}) = F_{n+1} \Leftrightarrow x_{n+1}R(x_{n+1})=F_{n+1}-1=F_n+F_{n-1}-1<2(F_n-1)$, а поскольку $x_n=F_n-1$ и $x_{n+1}|F_{n+1}-1$, то $x_{n+1}=F_{n+1}-1$.
Таким образом $Q(F_n-1)=F_n$, откуда вывод, что $Q(x)=x$.

Можно было бы числа Фибоначчи заменить на более быстрорастущую рекуррентную последовательность 2-го порядка В этом случае мое доказательство не проходит.

[nnosipov]

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

По-моему, та же идея, что и в этой задаче.

Не вижу как можно использовать эту идею здесь. Всё-таки $F_n$ экспоненциально зависят от $n$. Есть аналогичная задача, где вместо последовательности $F_n$ фигурирует геометрическая прогрессия, но и она решается не слишком просто. (А может быть, я не вижу каких-то простых подходов?)

-- Сб апр 16, 2011 18:05:06 --

Sonic86 в сообщении #435459 писал(а):

Кажется, такого многочлена нет, кроме тривиального $Q(x)=x$, а жаль.
Пусть $Q(x):Q(x_n)=F_n$, причем $Q(0)=1=F_1=F_2$. Тогда свободный член многочлена равен 1 и поскольку все коэффициенты целые, то $Q(x_n)=F_n \Leftrightarrow x_nR(x_n)=F_n-1$, где $R(x)=\frac{Q(x)-1}{x}$. Нетрудно найти, что $x_3=1$, откуда поскольку $x_4>x_3$ будет $x_4=2$. Докажем по индукции, что $x_n=F_n-1$. Для $n=3;4$ - верно. $Q(x_{n+1}) = F_{n+1} \Leftrightarrow x_{n+1}R(x_{n+1})=F_{n+1}-1=F_n+F_{n-1}-1<2(F_n-1)$, а поскольку $x_n=F_n-1$ и $x_{n+1}|F_{n+1}-1$, то $x_{n+1}=F_{n+1}-1$.
Таким образом $Q(F_n-1)=F_n$, откуда вывод, что $Q(x)=x$.

Можно было бы числа Фибоначчи заменить на более быстрорастущую рекуррентную последовательность 2-го порядка В этом случае мое доказательство не проходит.

Да, похоже, это оно и есть, спасибо. Но для произвольной рекурренции 2-го порядка нужно что-то более сложное придумывать.

[Null]

Почему $x_3$ не может равняться -1?

[nnosipov]

Null в сообщении #435530 писал(а):

Почему $x_3$ не может равняться -1?

Да может, но, по-моему, это не принципиально. Хотя, конечно, предложенное решение стоило бы подчистить.

[Sonic86]

Null писал(а):

Почему $x_3$ не может равняться -1?

Я предполагал, что последовательность аргументов возрастает (это я доказательство с квадратного трехчлена так криво обобщал ). В общем случае, видимо, надо рассматривать $x>x_0$ и начинать не с 1-го числа Фибоначчи, а с какого-нибудь $r_0$-го.