2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Одна задача с XIII Кубка памяти Колмлгорова
Сообщение16.04.2011, 10:18 
Заслуженный участник


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

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

 Профиль  
                  
 
 Re: Одна задача с XIII Кубка памяти Колмлгорова
Сообщение16.04.2011, 13:27 


01/10/10

2116
Израиль (племянница БизиБивера)
nnosipov в сообщении #435388 писал(а):
Хотелось бы видеть оригинальное решение следующей задачи.

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

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

 Профиль  
                  
 
 Re: Одна задача с XIII Кубка памяти Колмлгорова
Сообщение16.04.2011, 13:29 
Заслуженный участник


08/04/08
8562
Кажется, такого многочлена нет, кроме тривиального $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-го порядка :roll: В этом случае мое доказательство не проходит.

 Профиль  
                  
 
 Re: Одна задача с XIII Кубка памяти Колмлгорова
Сообщение16.04.2011, 13:43 
Заслуженный участник


20/12/10
9110
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-го порядка :roll: В этом случае мое доказательство не проходит.


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

 Профиль  
                  
 
 Re: Одна задача с XIII Кубка памяти Колмлгорова
Сообщение16.04.2011, 16:29 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Одна задача с XIII Кубка памяти Колмлгорова
Сообщение16.04.2011, 17:15 
Заслуженный участник


20/12/10
9110
Null в сообщении #435530 писал(а):
Почему $x_3$ не может равняться -1?


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

 Профиль  
                  
 
 Re: Одна задача с XIII Кубка памяти Колмлгорова
Сообщение17.04.2011, 06:56 
Заслуженный участник


08/04/08
8562
Null писал(а):
Почему $x_3$ не может равняться -1?

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 7 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group