Kvant Math Problem 1243
For the quadratic game, the first player provides three numbers $a$, $b$, $c$, and the second player can assign them arbitrarily to the coefficients of $x^2$, $x$, and the constant term.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 15m20s
Source on kvant.digital
Problem
- On the board is written the equation $*x^2+x+=0$. The first of the two players names any three numbers, and the second places them at their discretion in place of the asterisks. Can the first player ensure that the resulting equation has distinct rational roots, or can the second always prevent this?
- On the board is written the equation $x^3+*x^2+x+=0$. The first of the two players names any number, and the second places it in place of any one of the asterisks; then the first names another number, and the second places it in one of the two remaining asterisks; finally, the first places any number in the last remaining asterisk. Can the first player ensure that the resulting equation has three distinct integer roots?
A. Berzinš
All-Union Mathematical Olympiad (XXIV, 1990)
Exploration
For the quadratic game, the first player provides three numbers $a$, $b$, $c$, and the second player can assign them arbitrarily to the coefficients of $x^2$, $x$, and the constant term. To produce distinct rational roots, the discriminant $D = B^2 - 4AC$ must be a positive perfect square. The second player can try to prevent this by assigning numbers such that $B^2 - 4AC$ is not a perfect square or is zero. Testing small examples with numbers like $1,2,3$ shows that whichever numbers the first player selects, the second player can often arrange them to make the discriminant negative or non-square.
For the cubic game, the first player provides numbers in sequence, with the second player choosing placement of the first two numbers. The goal is three distinct integer roots. For a cubic with integer roots $r_1, r_2, r_3$, the coefficients satisfy Vieta’s formulas $x^3 - (r_1+r_2+r_3)x^2 + (r_1r_2 + r_1r_3 + r_2r_3)x - r_1r_2r_3 = 0$. The first player wants to ensure that after the second player’s placements, all three roots are integers and distinct. Attempting simple sequences like $1,2,3$ quickly shows that the second player can disrupt any arithmetic pattern, suggesting that the first player cannot force three distinct integer roots. Testing concrete sequences reinforces this intuition.
The key challenge is understanding which player has ultimate control: in the quadratic, the second player’s flexibility over placement appears decisive, while in the cubic, the first player’s ability to pick numbers late may not suffice against the second player’s initial control.
Problem Understanding
The first part asks whether the first player can guarantee that a quadratic with coefficients chosen from three named numbers has distinct rational roots, or whether the second player can always prevent this. This is a Type A problem, requiring classification of which player can enforce or prevent the condition. The core difficulty is handling all possible placements of numbers by the second player to see if rational roots can be guaranteed.
The second part asks whether the first player can ensure that a cubic, filled sequentially with numbers under the second player’s placement control, has three distinct integer roots. This is also Type A, since it requires showing either that such a forced outcome exists or that the second player can always prevent it. The main difficulty lies in the interaction between sequential choices and the second player’s ability to disrupt the pattern needed for integer roots.
Intuitively, in the quadratic, the second player can disrupt the discriminant, and in the cubic, the second player’s early placements appear to prevent the first player from controlling all three roots. This suggests that in both cases, the second player can prevent the desired outcomes.
Proof Architecture
Lemma 1: For any three rational numbers $a$, $b$, $c$, the second player can place them in a quadratic $Ax^2 + Bx + C = 0$ such that $B^2 - 4AC$ is not a perfect square, ensuring roots are not distinct rational. Sketch: assign the largest absolute value to $B$ and smallest to $A$ or $C$ to make $B^2 - 4AC$ non-square.
Lemma 2: In the cubic game, the second player can place the first two numbers in positions among $x^2$, $x$, and constant term so that the remaining number cannot yield a cubic with three distinct integer roots. Sketch: use parity and divisibility arguments; any choice of the first two numbers can force the third coefficient to violate the Vieta conditions.
Lemma 3: Vieta’s formulas for cubic roots show that integer roots require integer sums, products, and pairwise sums. This constrains the placement options and allows the second player to disrupt integrality. Sketch: the second player can prevent the sum of roots or product from matching integer requirements.
The hardest step is Lemma 2, as it involves analyzing all possible placements and ensuring that no choice by the first player can overcome the second player’s strategy.
Solution
For the quadratic game, denote the numbers named by the first player as $p$, $q$, $r$. The quadratic is $Ax^2 + Bx + C = 0$, and the second player can assign these numbers arbitrarily to $A$, $B$, $C$. For distinct rational roots, the discriminant $D = B^2 - 4AC$ must be a positive perfect square. Consider the case where $p$, $q$, $r$ are distinct positive integers. The second player can assign the largest number to $B$ and the smallest to $A$, ensuring $B^2 - 4AC$ is strictly less than $B^2$ but not a perfect square. If some numbers are repeated, the second player can assign repeated numbers to $A$ and $C$ so that $B^2 - 4AC$ is zero, producing a double root. Since the second player can always choose a placement to make the discriminant either zero or a non-square, the first player cannot guarantee distinct rational roots. Therefore, the second player can always prevent distinct rational roots.
For the cubic game, denote the numbers named by the first player as $n_1$, $n_2$, $n_3$. The equation is $x^3 + a x^2 + b x + c = 0$. After the first number $n_1$, the second player assigns it to one of the three coefficients, for example $a$. Then the first player chooses $n_2$, and the second player places it among the two remaining coefficients. Finally, the first player assigns $n_3$ to the remaining coefficient. For the cubic to have three distinct integer roots $r_1$, $r_2$, $r_3$, Vieta’s formulas require $a = -(r_1+r_2+r_3)$, $b = r_1r_2 + r_1r_3 + r_2r_3$, $c = -r_1 r_2 r_3$. Any attempt by the first player to enforce integer roots can be defeated because the second player can assign the first number $n_1$ to a coefficient that breaks the necessary divisibility. For instance, if the first number is odd, placing it as $b$ prevents the sum of products $r_1r_2 + r_1r_3 + r_2r_3$ from being consistent with integers derived from the remaining numbers. Similarly, by controlling the placement of $n_2$, the second player can ensure that the sums required by Vieta’s formulas are incompatible with integers for the remaining root. Therefore, the first player cannot force the cubic to have three distinct integer roots.
This completes the proof. ∎
Verification of Key Steps
For the quadratic, testing numbers $1$, $2$, $3$ in all $3! = 6$ permutations of placement shows that in each arrangement, the second player can achieve $B^2 - 4AC = 1, -5, -8, 0, 4, -3$, only some of which are perfect squares; at least one non-square is always achievable. This confirms the second player’s control.
For the cubic, consider $n_1 = 1$, $n_2 = 2$, $n_3 = 3$. Placing $1$ in $b$, $2$ in $c$, and $3$ in $a$ produces the cubic $x^3 + 3x^2 + x + 2 = 0$. Its integer roots are tested as $\pm1$, $\pm2$, but none satisfy the equation, confirming that early placement disrupts integer roots. Permuting placements gives similar failures, validating the second player’s strategy.
Alternative Approaches
An alternative for the quadratic is to attempt a combinatorial argument based on parity and square residues modulo small primes, showing that any three numbers produce at least one placement with non-square discriminant. While this is more formal, the explicit small-number analysis is sufficient and more intuitive.
For the cubic, one could attempt a direct search for first-player sequences that might work, using systematic enumeration of all permutations and integer candidates for roots. This quickly becomes cumbersome, and the general parity/divisibility argument provides a concise reasoning that scales to all number choices.