Многочлен с целыми коэффициентами

[Edward_Tur]

Некоторый многочлен с целыми коэффициентами принимает в $k$ целых точках значения среди чисел от $1$ до $k-1$. Докажите, что если $k \ge 6$, то эти значения равны.

Источник ММО-2008

[Профессор Снэйп]

Вроде несложно.

Лемма: Пусть $z_1 < \ldots < z_k$ --- $k$ различных целых чисел, $k \geqslant 6$ и $I$ --- подмножество $\{ 1, \ldots, k \}$, не равное всему $\{ 1, \ldots, k \}$ и содержащее не менее двух элементов. Тогда найдётся $i_0 \in \{ 1, \ldots, k \} \setminus I$, такое что

$$ \left| \prod_{i \in I} (z_{i_0} - z_i) \right| > k-2 $$

Доказательство. Так как числа $z_1, \ldots, z_k$ целые, то для любых $j \in \{ 1, \ldots, k \} \setminus I$ и $i \in I$ справедливо $|z_j-z_i| \geqslant |j-i|$. Значит, достаточно показать, что для некоторого $i_0 \in \{ 1, \ldots, k \} \setminus I$ справедливо неравенство

$$ \prod_{i \in I} |i_0 - i| > k-2 $$

Это неравенство, в свою очередь, довольно несложно, хотя и муторно. Надо аккуратно рассматривать все возможные случаи и оценивать произведения. Если кому-то интересно, могу расписать полностью. Идеи там на уровне 5-го класса средней школы, но писанины много.

Теперь, после леммы, всё становится совсем просто. Пусть $z_1, \ldots, z_k$ --- $k$ различных целых чисел и многочлен $f(x) \in \mathbb{Z}[x]$ таков, что $f(z_i) \in [1,k-1]$ для всякого $i$ от $1$ до $k$. По принципу Дирихле найдётся целое $a \in [1,k-1]$, такое что множество

$$ I = \{ i : 1 \leqslant i \leqslant k,\, f(z_i) = a \} $$

содержит более одного элемента. Пусть $g(x) = f(x)-a$. Имеем

$$ g(x) = h(x) \cdot \prod_{i \in I} (x-z_i), $$

где $h(x)$ --- многочлен с целыми коэффициентами. Если предположить, что $I \neq \{ 1, \ldots, k \}$, то по доказанной лемме для некоторого $i_0 \in \{ 1, \ldots, k \} \setminus I$ справедливо

$$ |g(z_{i_0})| = |h(z_{i_0})| \cdot \left| \prod_{i \in I} (z_{i_0} - z_i) \right| > k-2, $$

так как $h(z_{i_0})$ --- целое число, отличное от нуля. Однако $f(z_{i_0}) \in [1,k-1]$ и $g(z_{i_0}) = f(z_{i_0}) - a \in [-(k-2), (k-2)]$. Противоречие.

[TOTAL]

Профессор Снэйп писал(а):

Это неравенство, в свою очередь, довольно несложно, хотя и муторно. Надо аккуратно рассматривать все возможные случаи и оценивать произведения.

Так как

$$f(z_1) = f(z_k)$$

, можно считать, что м-во

$$I$$

состоит из

$$z_1, z_k$$

и возможно еще чего-то.
Доказывать лемму для этого случая не муторно.

[Профессор Снэйп]

TOTAL писал(а):

Так как

$$f(z_1) = f(z_k)$$

, можно считать, что м-во

$$I$$

состоит из

$$z_1, z_k$$

и возможно еще чего-то.

Обоснуйте своё утверждение. Только, если можно, без кривляния и очередной порции загадочных умолчаний. Считайте, что тупому пятикласснику объясняете.

[TOTAL]

Профессор Снэйп писал(а):

TOTAL писал(а):

Так как

$$f(z_1) = f(z_k)$$

, можно считать, что м-во

$$I$$

состоит из

$$z_1, z_k$$

и возможно еще чего-то.

Обоснуйте своё утверждение. Только, если можно, без кривляния и очередной порции загадочных умолчаний. Считайте, что тупому пятикласснику объясняете.

На вопрос, заданный с кривляньем, отвечаю без кривлянья.

$$f(z_1)- f(z_k)=a_0(z_1^n-z_k^n)+ ... + a_{n-1}(z_1-z_k)= (z_1-z_k)*M$$

$$\left| z_1-z_k \right | > k-2$$

$$\left| f(z_1)-f(z_k) \right | \le k-2$$

поэтому

$$f(z_1) = f(z_k)$$

[Профессор Снэйп]

TOTAL писал(а):

$$f(z_1)- f(z_k)=a_0(z_1^n-z_k^n)+ ... + a_{n-1}(z_1-z_k)= (z_1-z_k)*M$$

$$\left| z_1-z_k \right | > k-2$$

$$\left| f(z_1)-f(z_k) \right | \le k-2$$

поэтому

$$f(z_1) = f(z_k)$$

Сие рассуждение мне понятно.

Надо признать, оно действительно сокращает выкладки. Впрочем, лемма верна и без допущения $1,k \in I$. Если рассматривать её как утверждение, имеющее самостоятельную ценность, то доказывать, конечно, нужно общий случай.

[TOTAL]

Профессор Снэйп писал(а):

TOTAL писал(а):

$$f(z_1)- f(z_k)=a_0(z_1^n-z_k^n)+ ... + a_{n-1}(z_1-z_k)= (z_1-z_k)*M$$

$$\left| z_1-z_k \right | > k-2$$

$$\left| f(z_1)-f(z_k) \right | \le k-2$$

поэтому

$$f(z_1) = f(z_k)$$

Сие рассуждение мне понятно.

Надо признать, оно действительно сокращает выкладки. Впрочем, лемма верна и без допущения $1,k \in I$. Если рассматривать её как утверждение, имеющее самостоятельную ценность, то доказывать, конечно, нужно общий случай.

Я бы сократил так.
Обозначим

$$D(z)=f(z)-f(z_1)=g_1(z)*(z-z_1)$$

. Очевидно,

$$\left| D(z_i) \right|<k-1$$

.

$$D(z_k)=g_1(z_k)*(z_k-z_1)=0$$

(иначе

$$\left| D(z_k) \right| \ge k-1$$

)
Поэтому

$$D(z)=g_2(z)*(z-z_1)*(z-z_k)$$

При

$$i=3,...,k-2$$

:

$$D(z_i)=g_2(z_i)*(z_i-z_1)*(z_i-z_k)=0$$

(иначе

$$\left| D(z_i) \right| \ge k-1$$

)

$$D(z_2)=g_3(z_2)*(z_2-z_{k-2})*(z_2-z_k)=0$$

(иначе

$$\left| D(z_2) \right| \ge k-1$$

)

$$D(z_{k-1})=g_4(z_{k-1})*(z_{k-1}-z_1})*(z_{k-1}-z_3)=0$$

(иначе

$$\left| D(z_{k-1}) \right| \ge k-1$$

)

[TOTAL]

Профессор Снэйп писал(а):

Впрочем, лемма верна и без допущения $1,k \in I$. Если рассматривать её как утверждение, имеющее самостоятельную ценность, то доказывать, конечно, нужно общий случай.

Как доказать лемму для $2,k-1 \in I$?
(Т.е. $I$ состоит только из вторых элементов с каждого конца.)

[Профессор Снэйп]

Да, я был не прав. Похоже что лемма на самом деле верна лишь при $k \geqslant 9$. Для $k=6,7,8$ приходится использовать тот факт, что $1,k \in I$.