Задача
ALG-B2-M01-P015 Довести трёхчлен до корня
Коэффициенты \(a,b,c\) квадратного трёхчлена \(ax^2+bx+c\) — натуральные числа, причём \(a+b+c=1800\). За одну монету можно изменить любой коэффициент на \(1\). Докажите, что за не более чем \(950\) монет можно получить квадратный трёхчлен с целым корнем.
Подсказка 1. Если \(c\) не слишком велико, сделайте \(c=0\).
Подсказка 2. Если \(c\) велико, замените его ближайшим квадратом, а \(a,b\) — удобными коэффициентами.
Если \(c\le950\), изменим \(c\) до \(0\). Получим \(ax^2+bx=x(ax+b)\), у которого есть целый корень \(0\), стоимость не больше \(950\).
Пусть теперь \(c>950\). Тогда \(a+b<850\). Найдём квадрат \(k^2\), ближайший к \(c\). Так как \(c<1800<43^2\), можно взять \(k\le42\), и расстояние от \(c\) до ближайшего квадрата не превосходит половины промежутка между соседними квадратами, то есть не больше \(42\). Заменим \(a\) на \(-1\), \(b\) на \(0\), \(c\) на \(k^2\). Стоимость не больше \((a+1)+b+42<893\). Получаем \(-x^2+k^2\), у которого есть целые корни \(\pm k\). В обоих случаях хватает \(950\) монет.
A. Анализ источника. Главные объекты: неравенства, порядок, экстремальный элемент или инвариант. Очевидный первый ход обычно даёт только локальную оценку. Скрытое наблюдение: надо выбрать правильную величину, которая не может уменьшаться, либо перемножить/сложить неравенства только после проверки знаков. Нужный шаг: переход к упорядоченной записи, инварианту, произведению или граничному случаю.
F. Обоснование сложности. Региональный уровень 7: требуется конструкция и аккуратная численная оценка ближайшего квадрата.
G. Почему это не одноходовая задача. Нельзя просто занулить один коэффициент во всех случаях; при большом \(c\) нужна другая стратегия.