|
|
 |
Условие
Дан многочлен $$*x^n+*x^{n-1}+\ldots+*x+*,$$ вместо каждого из $n+1$ его коэффициентов записана звёздочка. Играют двое, ходят по очереди, за ход выбирают любую звёздочку и заменяют её на любое целое ненулевое число. Когда звёздочек не останется, игрок, сделавший последний ход, выиграет, если у получившегося многочлена есть целый корень, иначе выиграет другой игрок. При каждом натуральном $n$ выясните, кто из игроков может гарантировать себе победу, как бы ни играл его соперник.
Решение
Разберём два случая.
1) $n$ нечётно. Тогда последний ход делает второй игрок. Его стратегия: после хода первого игрока заменять любую из оставшихся звёздочек на противоположное число. При этом после каждого хода второго, в том числе и в конце, сумма $S$ проставленных коэффициентов равна $0$. В итоге получится многочлен $f(x)$, для которого $f(1) = S = 0$, то есть он имеет целый корень 1.
2) $n$ чётно. Тогда последний ход делает первый игрок. Докажем, что он может действовать так, чтобы своим последним ходом получить многочлен, имеющий корнем число 1 или $-1$.
Для этого сначала выясним, что могло бы помешать первому сделать выигрышный последний ход, если все коэффициенты, кроме последнего, уже проставлены. Пусть $S_{Ч}$ и $S_{Н}$ — суммы проставленных коэффициентов при чётных и нечётных степенях соответственно. Чтобы получить корень 1, надо поставить такой коэффициент, чтобы сумма всех коэффициентов равнялась 0, а чтобы получить корень $-1$, надо поставить такой коэффициент, чтобы знакопеременная сумма всех коэффициентов равнялась 0. Если оба варианта невозможны для первого, он в каждом из случаев должен последним ходом поставить 0. Но тогда имеем: $S_{Ч}+S_{Н}=0$ и $S_{Ч}-S_{Н}=0$, откуда $S_{Ч}=S_{Н}=0$. Значит, первый сможет выиграть, если перед последним ходом хотя бы одна из сумм $S_{Ч}$, $S_{Н}$ будет ненулевой.
Так как общее число коэффициентов нечётно, то и количество коэффициентов при степенях одной какой-то чётности нечётно, назовём соответствующие коэффициенты красными, а остальные — синими. Пусть первый сначала заменит один из красных коэффициентов на 1, а далее каждый раз заменяет числом коэффициент того же цвета, что и только что заменил второй. Когда первый игрок впервые будет заменять последний коэффициент одного из цветов, пусть он выберет такое число, что сумма коэффициентов этого цвета окажется ненулевой. Тогда финальным ходом он сможет выбрать ненулевое число так, чтобы обнулить либо $S_{Ч}+S_{Н}$, либо $S_{Ч}-S_{Н}$, то есть число 1 или $-1$ будет корнем итогового многочлена.
Ответ
При любом натуральном $n$ игрок, делающий последний ход, имеет выигрышную стратегию.
