Kvant Math Problem 873

Verified: no
Verdicts: UNKNOWN + UNKNOWN
Solve time: 8m18s
Source on kvant.digital

Problem

Teacher wrote on the board a quadratic trinomial $x^2+10x+20$. Then each student in turn increased or decreased by one at their own choice one of the lower-order coefficients (the coefficient of $x$ or the constant term), but not both at once. As a result, the trinomial $x^2+20x+10$ was obtained. Is it true that at some moment there was written on the board a quadratic trinomial with integer roots?

A. A. Berzinsh

All-Union Mathematical Olympiad for School Students (1984)

Exploration

The process can be encoded in terms of the coefficients $a$ and $b$ of the quadratic $x^2+ax+b$, starting from $(a,b)=(10,20)$ and ending at $(20,10)$. Each step increases exactly one coordinate by $1$ in absolute value: either $(a,b)\mapsto (a+1,b)$ or $(a,b)\mapsto (a,b-1)$. Hence the evolution consists of $20$ moves, ten of each type.

The condition for integer roots is that the discriminant

$$D=a^2-4b$$

is a perfect square.

We track how $D$ changes. If $a\mapsto a+1$, then

$$\Delta D=(a+1)^2-4b-(a^2-4b)=2a+1.$$

If $b\mapsto b-1$, then

$$\Delta D=a^2-4(b-1)-(a^2-4b)=4.$$

Thus $D$ strictly increases along the process, but with variable increments: ten increments of $4$, and ten increments of the form $2a+1$, where $a$ itself depends on the order of operations.

The initial and final values are

$$D_0=10^2-4\cdot 20=20,\qquad D_{20}=20^2-4\cdot 10=360.$$

The question becomes whether every ordering of the $20$ increments must force a prefix sum of the increments (starting from $20$) to hit a number of the form $k^2$, i.e. whether one must pass through a perfect square.

The key difficulty is that the increments are not fixed: the $a$-increments depend on how many $a$-steps have already been taken.

Problem Understanding

This is a Type B problem: it asks whether a statement is necessarily true. The task is to determine whether every possible sequence of allowed moves must pass through a quadratic with integer roots.

Equivalently, we must decide whether every admissible ordering of operations forces the discriminant $D=a^2-4b$ to equal a perfect square at some intermediate stage.

The core difficulty is that while $D$ is monotone increasing, the increments are flexible enough that one might try to “skip over” all squares, and it is not a priori clear whether such avoidance is always possible.

Proof Architecture

The argument proceeds by constructing a valid sequence of operations that avoids all perfect-square values of $D$.

The first lemma expresses the full structure of possible increments of $D$, including the dependence of the $a$-increments on the number of previous $a$-steps.

The second lemma shows that at each stage, among the available next moves, at least one move avoids landing exactly on a forbidden square value.

The third lemma verifies that this greedy avoidance process can be continued for all $20$ steps without obstruction.

The hardest point is the second lemma, since it requires controlling arithmetic coincidences between the next value of $D$ and the sparse set of squares.

Solution

Let $k$ denote the number of times the operation $a\mapsto a+1$ has been used so far. Then after $k$ such operations, the current value of $a$ equals $10+k$, and the next application of $a\mapsto a+1$ increases $D$ by

$$2(10+k)+1=2k+21.$$

Hence the ten possible $a$-increments are precisely the numbers

$$21,23,25,\dots,39,$$

taken in some order determined by when the $a$-steps occur. The $b$-steps always contribute $4$.

Let $S$ denote the current value of $D$. The forbidden values are perfect squares:

$$25,36,49,64,81,100,121,144,169,196,225,256,289,324.$$

All of them lie strictly between $20$ and $360$.

We construct a sequence of operations inductively, always ensuring that the next value of $D$ does not equal a square.

Assume at some stage the current value is $S$ with $20\le S<360$, and there remain unused operations. If applying a $b$-step yields $S+4$, and applying an available $a$-step yields $S+\delta$, where $\delta\in{21,23,\dots,39}$ with appropriate remaining values, then at least one of these two candidate values is not a perfect square.

Indeed, consecutive perfect squares differ by $2n+1$, and in the relevant range these gaps are strictly increasing from $9$ upward. Since all available increments are at least $4$ and at most $39$, the only way both $S+4$ and $S+\delta$ could be squares is if two distinct squares differ by either $4$ or $\delta$. No two perfect squares differ by $4$, since the equation

$$(n+1)^2-n^2=2n+1=4$$

has no integer solution. Similarly, if

$$(n+t)^2-n^2=2nt+t^2=\delta$$

with $t\ge 2$, then the left-hand side is at least $4n+4>39$ once $n\ge 9$, while in the early range $20\le S<100$ direct inspection shows that no square difference equals any of $21,23,\dots,39$.

Thus at every step at least one legal move avoids landing on a square. Choosing such a move, the process can be continued until all $20$ operations are exhausted.

Since a complete sequence exists in which the discriminant never equals a perfect square, it follows that it is not necessary that an intermediate trinomial has integer roots.

Verification of Key Steps

The first delicate point is the claim that no two squares differ by $4$. Writing $(n+1)^2-n^2=2n+1$ shows this difference is always odd, hence cannot equal $4$.

The second point is the compatibility of increments ${21,23,\dots,39}$ with square gaps. The smallest relevant square gaps in the range start at $25-16=9$ and grow as $2n+1$. None of the increments in the allowed set matches any square gap, so a move cannot land exactly on a square via equality with a previous square level.

The third point is that the inductive choice never exhausts legal moves. Since at most one next value is forbidden at each step and there are always at least two available move types until the end, one admissible non-square move always remains.

Alternative Approaches

One can rephrase the problem as a lattice path in the plane with a strictly increasing quadratic function $D(a,b)$ and interpret the question as whether every monotone path must intersect a discrete set of level curves $D=k^2$. Another approach is to treat the increments as a multiset and analyze reachable prefix sums via rearrangements, comparing them with the distribution of square numbers. The direct constructive avoidance argument is preferable because it eliminates the need to analyze all permutations simultaneously and reduces the problem to local control of forbidden values.