Выбрана 1 задача 
Убрать все задачи
100 пиратов сыграли в карты на золотой песок, а потом каждый посчитал, сколько он в сумме выиграл либо проиграл. У каждого проигравшего хватает золота, чтобы расплатиться. За одну операцию пират может либо раздать всем поровну золота, либо получить с каждого поровну золота. Докажите, что можно за несколько таких операций добиться того, чтобы каждый получил (в сумме) свой выигрыш либо выплатил проигрыш. (Разумеется, общая сумма выигрышей равна сумме проигрышей.)
Решение
|
|
 |
Условие
Дан многочлен степени $n \geqslant 1$ с целыми ненулевыми коэффициентами, каждый из которых является его корнем. Докажите, что модули коэффициентов этого многочлена не превосходят 2.Решение
Пусть $P(x)=a_n x^n+a_{n-1}x^{n-1}+\ldots+a_1 x+a_0$ – данный в условии многочлен. По условию числа $a_k$, $k=0$, $1,\ldots, n$, являются его корнями: $$P(a_k)=a_n a_k^n+a_{n-1}a_k^{n-1}+\ldots+a_1 a_k+a_0=0.$$ Тогда $a_0$ делится на $a_k$ при любом $k=1$, $2,\ldots, n$. Поэтому достаточно доказать, что $|a_0|\leqslant 2$.Имеем $$ 0=P(a_0)=a_n a_0^n+a_{n-1}a_0^{n-1}+\ldots+a_1 a_0+a_0= $$ $$ = a_0(a_n a_0^{n-1}+a_{n-1}a_0^{n-2}+\ldots+a_2a_0+a_1+1),$$ значит, $a_1+1$ делится на $a_0$. Как показано выше, $a_0$ делится на $a_1$. Значит, $a_1+1$ делится на $a_1$. Поскольку эти числа взаимно просты, это возможно только в случае, если $a_1=\pm1$.
Если $a_1=1$, то $a_1+1=2$ делится на $a_0$, и утверждение доказано.
Пусть теперь $a_1=-1$. Докажем индукцией по $m$, что $a_0a_{2m-1}+a_{2m-2}=0$ и $a_{2m-1}=\pm1$ при всех $m=1$, $2,\ldots, \Bigl[\frac{n+1}{2}\Bigr]$.
База ($m=1$) уже доказана: $a_0a_1+a_0=a_0(a_1+1)=0$, $a_1=-1$.
Пусть равенство $a_0a_{2m-1}+a_{2m-2}=0$ выполнено при всех $m=1$, $2,\ldots, k$. Тогда многочлен $P(x)$ имеет вид $$ P(x)=a_n x^n+a_{n-1} x^{n-1} +\ldots+a_{2k+1}x^{2k+1}+a_{2k}x^{2k} \pm(x^{2k-1}-a_0x^{2k-2})\pm(x^{2k-3}-a_0x^{2k-4})\pm\ldots \pm (x-a_0). $$ При $x=a_0$ получаем $$ 0=P(a_0)=a_n a_0^n+a_{n-1} a_0^{n-1} + \ldots +a_{2k+1}a_0^{2k+1} + a_{2k}a_0^{2k} =$$ $$= a_0^{2k}(a_n a_0^{n-2k}+a_{n-1} a_0^{n-2k-1} +\ldots+a_{2k+1}a_0+a_{2k}).$$ Следовательно, $a_{2k}$ делится на $a_0$. Как показано выше, $a_0$ делится на $a_{2k}$, поэтому $a_{2k}=\varepsilon a_0$, где $\varepsilon=\pm1$. Тогда $$ 0=a_n a_0^{n-2k}+a_{n-1} a_0^{n-2k-1} +\ldots+a_{2k+1}a_0+a_{2k}=$$ $$ =a_0(a_n a_0^{n-2k-1}+a_{n-1} a_0^{n-2k-2} +\ldots+a_{2k+1}+\varepsilon). $$ Значит, $a_{2k+1}+\varepsilon$ делится на $a_0$. Как показано выше, $a_0$ делится на $a_{2k+1}$. Значит, $a_{2k+1}+\varepsilon$ делится на $a_{2k+1}$. Поскольку эти числа взаимно просты, это возможно только в случае, если $a_{2k+1}=\pm1$.
Если $a_{2k+1}=\varepsilon$, то $a_{2k+1}+\varepsilon=2\varepsilon=\pm 2$ делится на $a_0$, и утверждение доказано.
Если $a_{2k+1}=-\varepsilon$, то $a_0a_{2k+1}+a_{2k}=a_0(-\varepsilon+\varepsilon)=0$ и $a_{2k+1}=-\varepsilon=\pm1$ – переход доказан.
Если $n=2s$ чётно, то из доказанного утверждения следует, что многочлен $P(x)$ имеет вид $$ P(x)=a_{2s} x^{2s}\pm(x^{2s-1}-a_0x^{2s-2})\pm(x^{2s-3}-a_0x^{2s4}) \pm \ldots \pm (x-a_0).$$ При $x=a_0$ получаем $0=P(a_0)=a_{2s}a_0^{2s}$, что по условию невозможно.
Если $n = 2s+1$ нечётно, то из доказанного утверждения следует, что многочлен $P(x)$ имеет вид $$P(x)=\varepsilon_{s+1}(x^{2s+1}-a_0x^{2s})+\varepsilon_{s}(x^{2s-1}-a_0x^{2s-2})+ \ldots + \varepsilon_1(x-a_0),$$ где $\varepsilon_k$ – целые числа, по модулю равные $1$, при всех $k=1$, $2, \ldots, s+1$.
Как было показано выше, $\varepsilon_1 = -1$, поэтому из условия следует, что число $-1$ является корнем многочлена $P(x)$. Тогда $$ 0 = P(-1) = \varepsilon_{s+1}((-1)^{2s+1}-a_0(-1)^{2s}) + \varepsilon_{s}((-1)^{2s-1}-a_0(-1)^{2s-2})+\ldots +\varepsilon_1(-1-a_0) =$$ $$= (\varepsilon_{s+1}+\varepsilon_s+\ldots+\varepsilon_1)(-1-a_0) = 0.$$ Если значение первой скобки отлично от нуля, то из этого равенства следует, что $a_0 = -1$, и утверждение доказано.
Предположим, что $\varepsilon_{s+1}+\ldots+\varepsilon_1 = 0$. Тогда поскольку $\varepsilon_1 = -1$, то найдётся такое $k$ от $2$ до $s+1$, что $\varepsilon_k = 1$. Значит, $a_{2k-2}=-a_0$, т. е. число $-a_0$ является коэффициентом многочлена $P(x)$. Тогда по условию $$ 0 = P(-a_0) = \varepsilon_{s+1}((-a_0)^{2s+1}-a_0(-a_0)^{2s})+\varepsilon_{s}((-a_0)^{2s-1}-a_0(-a_0)^{2s-2})+\ldots +\varepsilon_1(-a_0-a_0) =$$ $$ = -2\varepsilon_{s+1}a_0^{2s+1}-2\varepsilon_sa_0^{2s-1}-\ldots-2\varepsilon_2a_0^3 - 2\varepsilon_1 a_0 = $$ $$= -2a_0(\varepsilon_{s+1}a_0^{2s} + \varepsilon_sa_0^{2s-2}+\ldots+\varepsilon_2a_0^2 + \varepsilon_1). $$ Отсюда следует, что $\varepsilon_1 = -1$ делится на $a_0$, поэтому $|a_0|\leqslant 1$, что завершает доказательство.
