Problem
ALG-B2-M01-P015 Forcing a root in a trinomial
The coefficients \(a,b,c\) of the quadratic trinomial \(ax^2+bx+c\) are positive integers and \(a+b+c=1800\). For one coin, one may change any coefficient by \(1\). Prove that with at most \(950\) coins one can obtain a quadratic trinomial with an integer root.
Hint 1. If \(c\) is not too large, make \(c=0\).
Hint 2. If \(c\) is large, replace it by a nearby square and choose convenient \(a,b\).
If \(c\le950\), change \(c\) to \(0\). Then \(ax^2+bx=x(ax+b)\) has the integer root \(0\), and the cost is at most \(950\).
Now suppose \(c>950\). Then \(a+b<850\). Choose a square \(k^2\) nearest to \(c\). Since \(c<1800<43^2\), we may take \(k\le42\), and the distance from \(c\) to the nearest square is at most half the gap between neighbouring squares, hence at most \(42\). Change \(a\) to \(-1\), \(b\) to \(0\), and \(c\) to \(k^2\). The cost is at most \((a+1)+b+42<893\). The resulting trinomial \(-x^2+k^2\) has integer roots \(\pm k\). In both cases, \(950\) coins are enough.
A. Source analysis. Main objects: inequalities, order, an extremal element, or an invariant. The obvious first move usually gives only a local estimate. The hidden observation is to choose the right nondecreasing quantity, or to add/multiply inequalities only after signs are controlled. The needed step is an ordering, an invariant, a product transformation, or a boundary case.
F. Difficulty justification. Regional level 7: it requires a construction and a careful numerical estimate for the nearest square.
G. Why this is not a one-step exercise. One cannot simply zero out one coefficient in all cases; for large \(c\), another strategy is needed.