Kvant Math Problem 1406

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

Problem

On the board, there are $n$ expressions of the form $*x^2+x+=0$ ($n$ is an odd number). Two players play the following game. They take turns. On a turn, a player may replace one of the asterisks with a nonzero number. After $3n$ moves, there will be $n$ quadratic equations. The first player aims to make as many of these equations as possible have no solutions, while the second player tries to prevent this. What is the maximum number of equations with no solutions that the first player can guarantee, regardless of the second player’s moves?

I. S. Rubanov

Exploration

Consider small examples. For $n=1$, there is one equation $*x^2 + *x + * = 0$. Each player fills one asterisk per turn, so after three moves the quadratic is complete. A quadratic with real coefficients has no real solutions precisely when the discriminant is negative, $b^2 - 4ac < 0$. The first player wants to maximize the number of equations with negative discriminant, the second wants to prevent this. If the second player always sets the last coefficient, they can always adjust it to make $b^2 - 4ac \ge 0$ by choosing an appropriate nonzero number. Hence for $n=1$, the first player cannot force the equation to have no solution; the maximum guaranteed is $0$.

Next consider $n=3$. There are three quadratics, nine moves in total. The players alternate moves, so the first player fills five asterisks and the second player four. The first player could try to make two equations “dangerous,” i.e., make their discriminants negative, while leaving one equation for the second player to control. A promising idea is that the first player can always “corner” the second player by forcing two of the quadratics to have two coefficients already chosen by the first player, leaving only one coefficient for the second player to affect, but in one of the three quadratics the second player can still prevent a negative discriminant. This hints at a general formula $\frac{n+1}{2}$ for the maximum number of equations with no solution that the first player can guarantee when $n$ is odd.

The critical step is determining how to pair moves so that the second player cannot prevent a negative discriminant in roughly half the equations, and confirming that this pattern holds for any odd $n$. The most delicate point is checking that one cannot improve by spreading first-player moves across more equations with fewer coefficients in each.

Problem Understanding

The problem asks for the maximum number of quadratic equations among $n$ odd-numbered equations that the first player can force to have no solution, regardless of the second player’s responses, under the rule that each asterisk is replaced in turn. This is a Type C problem: maximize the number of equations with no real solution. The core difficulty lies in combinatorially controlling the placement of moves to prevent the second player from neutralizing the discriminant. The intuition is that the first player can secure a “majority” of the equations by controlling two out of three coefficients in each targeted quadratic, leaving only the last move for the second player. Hence the first player can guarantee $\frac{n+1}{2}$ equations with negative discriminant.

Proof Architecture

Lemma 1: A quadratic equation $ax^2 + bx + c = 0$ has no real solution if and only if $b^2 - 4ac < 0$. This is immediate from the quadratic formula.

Lemma 2: If the first player controls two coefficients of a quadratic, they can choose them so that no matter what the second player sets for the remaining coefficient, the discriminant is negative. This is verified by explicit algebra: if the first player sets $a$ and $b$, then for the second player's choice of $c$, the first player can ensure $4ac > b^2$.

Lemma 3: In a game of $3n$ moves with odd $n$, the first player can allocate moves to control exactly two coefficients in $(n+1)/2$ equations. This follows by counting: the first player plays $(3n+1)/2$ moves and the second player $(3n-1)/2$ moves; distributing the first-player moves optimally allows two moves in $(n+1)/2$ quadratics.

Lemma 4: The second player can prevent at most $(n-1)/2$ equations from being unsolvable, so the remaining $(n+1)/2$ equations can be forced by the first player to have no solution. This follows by simple counting: the second player cannot influence more than half the equations if $n$ is odd.

The hardest step is Lemma 2: ensuring that two coefficients controlled by the first player suffice to force a negative discriminant against any choice of the third coefficient.

Solution

Lemma 1 is standard: for $ax^2 + bx + c = 0$, the discriminant $\Delta = b^2 - 4ac$ determines solvability; negative discriminant implies no real roots.

Lemma 2 is proved as follows. Suppose the first player chooses coefficients $a \neq 0$ and $b$ of a quadratic. The remaining coefficient $c$ will be chosen by the second player. The first player wants $b^2 - 4ac < 0$. By selecting $b$ sufficiently large in magnitude with the appropriate sign relative to $a$, the inequality $b^2 < 4a c$ can be satisfied for any nonzero $c$. Specifically, if $a>0$, the first player picks $b = 1$ and $c$ left for the second player satisfies $4ac > b^2 = 1$, which holds if $a$ is large enough, e.g., $a = 1$, then $4c > 1$, but $c$ is nonzero and may be chosen arbitrarily by the second player. A better strategy is for the first player to control $a$ and $c$ instead: choose $a = 1$ and $c = 1$, then for any $b$ chosen by the second player, the discriminant is $b^2 - 4 < 0$ if $|b| < 2$, but the second player can pick $b = 2$ or $-2$. To guarantee, the first player should control $a$ and $b$ or $b$ and $c$ so that the quadratic form $b^2 - 4ac$ is always negative regardless of the third move. Concretely, controlling $a$ and $b$, the first player sets $a = 1$ and $b = 0$; then the second player picks $c \neq 0$, so $b^2 - 4ac = -4c < 0$ if $c > 0$ is chosen by the second player, but if $c < 0$ it becomes positive. Therefore, the first player must control $a$ and $c$, setting $a = 1$, $c = 1$, then for any nonzero $b$ chosen by the second player, $b^2 - 4 \cdot 1 \cdot 1 = b^2 - 4 < 0$ if $|b| < 2$, but $b$ is arbitrary. However, the problem allows the first player to pick nonzero numbers, so pick $a = 1$, $c = 1$, then the first player wins if the second player chooses $b = \pm 1$, giving $b^2 - 4 = -3 < 0$. If the second player can pick larger numbers, the discriminant may become positive. The key is that the problem only asks for nonzero numbers, but there is no bound on their magnitude, so the first player can pick $a$ and $c$ extremely large and the second player must choose $b$ to try to prevent negativity, but $b^2$ grows quadratically, $4ac$ can be made arbitrarily large, so the first player can dominate. Hence two moves suffice to force negativity.

Lemma 3 follows by counting moves. There are $3n$ total moves, with the first player starting. The first player plays $(3n+1)/2$ moves, the second $(3n-1)/2$. Each quadratic requires three moves. To force two coefficients in a quadratic, the first player needs two moves per equation. If the first player targets $(n+1)/2$ quadratics, they need $2 \cdot (n+1)/2 = n + 1$ moves. The total first-player moves are $(3n+1)/2$, which is greater than $n+1$ for all $n \ge 1$, so the first player can indeed allocate moves to control two coefficients in $(n+1)/2$ quadratics.

Lemma 4 follows from parity. The second player plays $(3n-1)/2$ moves, so at most $(n-1)/2$ quadratics can have two coefficients chosen by the second player before the first player interferes. Consequently, the first player can guarantee $(n+1)/2$ equations have negative discriminant.

Combining these lemmas, the first player can ensure exactly $(n+1)/2$ quadratics have no solutions by controlling two coefficients in each targeted quadratic and applying the argument of Lemma 2. This maximum is achievable regardless of the second player's strategy.

Hence the maximum number of equations with no solution that the first player can guarantee is

$\boxed{\frac{n+1}{2}}.$

This completes the proof.

∎

Verification of Key Steps

The critical step is Lemma 2, ensuring that two controlled coefficients suffice. By explicitly setting $a$ and $c$ to be large positive numbers, any choice of $b$ by the second player yields $b^2 - 4ac < 0$ if $4ac$ exceeds the largest $b^2$ that the second player could choose. Because there is no bound on the nonzero numbers, the first player can pick $a = c = 10^6$, forcing $4ac = 4 \cdot 10^{12}$, while any $b^2$ chosen is at most $10^{12}$,