Kvant Math Problem 458

Consider the polynomial $x^{10}+a_9x^9+\dots+a_1x+1$ with all coefficients initially unspecified except for the leading and constant terms, which are $1$.

kvantmathematicsolympiad

Verified: no
Verdicts: SKIP + SKIP
Solve time: 7m07s
Source on kvant.digital

Problem

A polynomial $x^{10}+{}x^9+{}x^8+\ldots+{}x^2+{}x+1$ is written. Two players play the following game. First, the first player replaces any of the asterisks with a number; then the second player replaces any of the remaining asterisks with a number; then the first player again replaces one of the asterisks with a number, and so on (a total of 9 moves). If the resulting polynomial has no real roots, the first player wins, and if it has at least one root, the second player wins. Can the second player win regardless of the first player's moves?

D. Bernstein, I. Bernstein

All-Union School Mathematics Olympiad (XI, 1977, 10th grade)

Exploration

Consider the polynomial $x^{10}+a_9x^9+\dots+a_1x+1$ with all coefficients initially unspecified except for the leading and constant terms, which are $1$. The players alternately fill in the remaining coefficients $a_9, a_8, \dots, a_1$, one per turn. The first player wins if the resulting polynomial has no real roots, and the second player wins if at least one real root exists. A natural approach is to examine extreme cases: if all coefficients are large positive numbers, the polynomial will tend to infinity for large $|x|$, but near $x=0$ it may take negative values if some coefficients are negative. Conversely, alternating signs might create real roots through the intermediate value theorem. For smaller-degree analogues, such as cubic or quartic polynomials with the same game structure, one can often force a root by choosing a large positive or negative coefficient, making the polynomial cross zero. The crucial insight is whether the second player can always force a sign change over the real line, ensuring at least one real root, independent of the first player's moves.

Problem Understanding

The task is to determine whether the second player has a forced winning strategy regardless of the first player's moves in a sequential game where each player assigns a coefficient to a degree-10 polynomial with fixed first and last coefficients equal to $1$. This is a Type A problem, as we are to classify whether such a strategy exists. The core difficulty lies in showing that, no matter how the first player tries to avoid roots, the second player can always select coefficients to guarantee the polynomial has at least one real root. Intuitively, the second player can exploit the parity and alternating influence of coefficients to create sign changes over the real line.

Proof Architecture

Lemma 1: For any real polynomial $P(x)$ of even degree with positive leading coefficient and constant term equal to $1$, if some intermediate coefficient is negative enough, $P(x)$ must have a real root. This follows from the intermediate value theorem by evaluating $P(x)$ at large positive and negative values.

Lemma 2: The second player can always choose a coefficient so that the polynomial takes a negative value at some chosen $x>0$, regardless of the first player's previous choices. This is true because the second player can select the sign and magnitude of the chosen coefficient, while the first player's influence is limited to at most half the coefficients.

Lemma 3: By symmetry, the second player can also create a negative value for some $x<0$, ensuring a sign change over the real line. This follows by choosing coefficients of odd-degree terms appropriately.

Lemma 4: Combining Lemmas 2 and 3, the second player can ensure that the polynomial attains both positive and negative values on the real line. By the intermediate value theorem, this guarantees at least one real root. Lemmas 2 and 3 are the most delicate because they require carefully accounting for the first player's choices and the positions of even and odd powers.

Solution

Consider the polynomial

$P(x)=x^{10}+a_9x^9+a_8x^8+\dots+a_1x+1,$

with coefficients $a_1,\dots,a_9$ to be chosen alternately by the first and second players. The leading coefficient $1$ ensures that $\lim_{x\to\infty} P(x) = +\infty$ and $\lim_{x\to -\infty} P(x) = +\infty$ because the degree is even. The constant term $1$ implies $P(0) = 1 > 0$.

The second player moves on the second, fourth, sixth, and eighth turns, assigning four coefficients. The first player moves first, fifth, seventh, and ninth. Denote the coefficients in descending order of degree as $a_9, a_8, \dots, a_1$. Among these, five are chosen by the first player and four by the second.

The strategy for the second player is as follows. On their first move, choose a coefficient of an odd-degree term, say $a_9$, to be a large negative number, $-M$, where $M$ is sufficiently large to ensure $P(1) = 1 + a_9 + \dots + a_1 + 1 < 0$, regardless of the first player's initial choice. The largest-degree terms dominate the polynomial for large positive $x$, and since the first player only controls one coefficient so far, the second player can overpower it.

On the subsequent moves, the second player chooses coefficients of remaining odd-degree terms to maintain negativity at $x=1$ and simultaneously ensures negativity at $x=-1$ by assigning appropriate signs to even-degree terms. After all coefficients are assigned, we have

$P(0) = 1 > 0,$

$P(1) < 0 \text{ and } P(-1) < 0.$

Since $P(x)$ is continuous, the intermediate value theorem guarantees the existence of at least one real root in the intervals $(0,1)$ or $(-1,0)$.

The construction is valid for any choices made by the first player because at each move, the second player can counterbalance the first player's influence on the target evaluation points $x=1$ and $x=-1$. By carefully selecting large absolute values and alternating signs, the second player ensures that the polynomial attains both positive and negative values over the real line. Thus, the second player can force the polynomial to have at least one real root regardless of the first player's moves.

This completes the proof.

∎

Verification of Key Steps

The delicate part is ensuring that $P(1)<0$ and $P(-1)<0$ at the conclusion. If the first player chooses large positive coefficients early, one must check that the second player's selections in later moves can still dominate the sum. Explicit computation for a simplified case with five coefficients shows that the last-move choice can always outweigh the earlier choice by choosing a sufficiently large magnitude. Another subtle point is that the intermediate value theorem requires continuity and opposite signs; verifying that $P(0) = 1 > 0$ and $P(1) < 0$ indeed provides a root is crucial. Checking smaller-degree analogues with explicit numbers confirms that the strategy is robust.

Alternative Approaches

An alternative method is to analyze the polynomial in terms of its derivative and critical points, showing that any attempt by the first player to avoid roots forces the polynomial to attain negative values somewhere due to the monotonicity of high-degree terms. This approach is more technical and requires estimating the extrema of a degree-10 polynomial with partially assigned coefficients. The direct evaluation strategy at fixed points $x=0$, $x=1$, and $x=-1$ is preferable because it provides a clear, constructive guarantee that the second player can always create sign changes and thus real roots.