Задано натуральное число $%n$%. Доказать, что существует многочлен $%P(x)$% с целыми коэффициентами, для которого $%P(1),P(2),...,P(n)$% - различные степени двойки.

задан 15 Ноя '18 23:39

@EdwardTurJ: я располагаю решением, но сегодня оформить уже не успеваю. Там доказывается несколько более общий факт, из которого следует заключение про степени двойки.

(17 Ноя '18 5:32) falcao
1

@falcao , пропустил я этот момент) подумать надо еще)

(17 Ноя '18 11:57) Sergic Primazon
10|600 символов нужно символов осталось
2

Изложу, наконец, своё решение -- по ходу дела оно существенно упростилось.

Пусть $%a_1$%, ... , $%a_n$% -- целые числа. Рассмотрим интерполяционный многочлен Лагранжа для узлов $%1$%, ... , $%n$%. Он задаётся известной формулой $%f(x)=\sum\limits_{k=1}^na_k\frac{g_k(x)}{g_k(k)}$%, где для любого $%1\le k\le n$% многочлен $%g_k(x)$% имеет степень $%n-1$%, и он равен $%\prod\limits_{i\ne k}{(x-i)}$%. Ясно, что все знаменатели дробей в формуле делят $%n!^2$% (оценка довольно грубая). Отсюда следует, что существует многочлен $%P(x)$% с целыми коэффициентами, для которого $%P(k)=n!^2a_k$% для всех $%1\le k\le n$%.

Ясно, что если ко всем значениям многочлена прибавить целочисленную константу, то снова получится многочлен с целыми коэффициентами. Поэтому, если числа $%a_1$%, ... , $%a_n$% попарно сравнимы по модулю $%n!^2$%, то это даёт достаточное условие существования многочлена над $%\mathbb Z$% с заданными значениями в точках от $%1$% до $%n$%.

Положим $%n!^2=2^tM$%, где $%M$% нечётно. Из принципа Дирихле следует существование натурального $%d$% такого, что $%2^d-1$% делится на $%M$%. Тогда берём различные степени двойки вида $%2^t$%, $%2^{t+d}$%, $%2^{t+2d}$%, ... , $%2^{t+(n-1)d}$%. Они попарно сравнимы по модулю $%n!^2$%, то есть для них искомый многочлен найдётся.

Заметим, что $%n!^2$% здесь можно было бы заменить на $%(n-1)!$%, так как все числа $%|g_k(k)|$% имеют вид $%a!b!$%, где $%a+b=n-1$%.

В заключение отметим, что есть удобный в использовании критерий того, могут ли целые числа $%a_1$%, ... , $%a_n$% быть значениями многочлена с целыми коэффициентами в $%n$% последовательных целых точках. При $%n=2$% это всегда так. Пусть $%n > 2$%. Допустим, что нашёлся многочлен $%P(x)$% с требуемыми свойствами. Представим его в виде $%P(x)=P(1)+(x-1)Q(x)$%. Тогда все числа вида $%\frac{a_k-a_1}{k-1}=Q(k)$% при $%2\le k\le n$% окажутся целыми. И обратно: если от имеющегося списка $%n$% целых чисел перейти к списку из $%n-1$% числа $%a_2-a_1$%, $%\frac{a_3-a_1}2$%, ... , $%\frac{a_k-a_1}{k-1}$%, ... , $%\frac{a_n-a_1}{n-1}$%, то эти числа, во-первых, должны быть целыми, а во-вторых, для них должен найтись многочлен с целыми коэффициентами, что проверяется по рекурсии.

Примеры: числа 2,4,8,16 дают 2,3,14/3, то есть они не годятся. Числа 2,4,8,32 дают 2,3,10, после чего идут целые числа 1,4, то есть целочисленный многочлен с такими значениями имеется. Для конкретных значений это даёт очень быстрый алгоритм проверки. Причём нетрудно привести примеры, когда первые шаги алгоритма осуществляются успешно, а "отказ" следует где-то ближе к концу.

ссылка

отвечен 17 Ноя '18 14:20

10|600 символов нужно символов осталось
2

$%n=2: \ \ \ p_2(x)=2x$%

Многочлены будем строить индукцией по степеням:

$%p_3(x)=2^{m_3}(p_2(x))^{k_3}+A_3(x-1)(x-2)$%

$%p_3(1)= 2^{m_3}(p_2(1))^{k_3}\ , \ p_3(2)= 2^{m_3}(p_2(2))^{k_3}$%

$% p_3(3)= 2^{m_3}(p_2(3))^{k_3}+A_3\cdot 2!=2^{r_3} \ \ ,\ m_3=0\ ,\ k_3=1\ ,\ A_3=1\ , r_3=3$%

$%p_3(x)=p_2(x)+(x-1)(x-2)\ , \ p_3(1)=2\ ,\ p_3(2)=4\ , \ p_3(3)=8$%

Далее все строится аналогично:

$$p_n(x)=2^{m_n}(p_{n-1}(x))^{k_n}+A_{n}(x-1)(x-2)\cdot\ . \ .\ . (x-n+1)$$

$$p_n(i)= 2^{m_n}( p_{n-1}(i))^{k_n}\ ,\ i \in[1,n-1]$$

$$p_n(n)= 2^{m_n}(p_{n-1}(n))^{k_n}+A_n(n-1)!=2^{\gamma}$$

$%(\ p_{n-1}(n)\ ,\ (n-1)!\ )= 2^{ l}\ ,$% т.к. $%p_{n-1}(i)=2^{r_i} \ \ i \in [0,n-1] $%

$%p_{n-1}(n)=2^{\alpha}\cdot Z_1\ ,\ (n-1)!=2^{\beta}\cdot Z_2\ \ (Z_1,Z_2)=1 \ \ \ Z_1,Z_2 -$% нечетные.

$$p_n(n)=2^{\alpha k_n+m_n}\cdot Z_1^{k_n}+A_n2^{\beta}\cdot Z_2=2^\gamma$$

Подбираем $%k_n:\ Z_1^{k_n}=1 \ mod \ Z_2\ \ \ (Z_1^{k_n}=1+B\cdot Z_2)\ $%

$% A_n=A\cdot2^{\delta}$% , выравниваем степени двойки :$% \ \alpha k_n+ m_n=\delta+\beta$%

Получаем: $%2^{\delta+\beta}(1+(A+B)Z_2)=2^\gamma$% (подбираем $%A$% )

ссылка

отвечен 18 Ноя '18 23:34

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×364
×146

задан
15 Ноя '18 23:39

показан
1973 раза

обновлен
18 Ноя '18 23:34

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

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

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru