Задача 8.4 из книги «Введение в настоящую математику»
а) В фирме 28 служащих с большим стажем и 37 — с маленьким. Хозяин фирмы выделил некую сумму для подарков служащим на Новый год. Бухгалтер подсчитал, что есть только один способ разделить деньги так, чтобы все служащие с большим стажем получили поровну и все с маленьким — тоже поровну (все получают целое число рублей, большее 0). Какую наименьшую и какую наибольшую сумму мог выделить хозяин на подарки?
b*) А если ещё требуется, чтобы служащий с большим стажем получил больше денег, чем служащий с маленьким стажем?
28·x + 37·y = N, x, y — целые, x ≥ 1, y ≥ 1
Здесь x — сумма для сотрудника с большим стажем, y — с маленьким, N — выделенная хозяином сумма. Двигайте N и смотрите, сколько целых точек прямой попадает в положительную четверть.
Типовые значения N — нажмите, чтобы установить на шкале:
решений с x, y ≥ 1 (пункт а)
—
из них с x > y (пункт b)
—
Все решения уравнения в целых числах лежат на одной прямой и идут с постоянным шагом: следующая точка получается из предыдущей сдвигом x → x + 37, y → y − 28 (это следствие того, что НОД(28, 37) = 1). Поэтому вопрос «сколько решений с x, y ≥ 1» — это вопрос «сколько точек этой цепочки помещается в положительной четверти».
Решение единственно ровно тогда, когда его точка лежит в прямоугольнике {1…37} × {1…28} (включите галочку выше): шаг вправо-вниз тогда выбрасывает y за ноль, а шаг влево-вверх выбрасывает x. Минимум и максимум линейной функции N = 28x + 37y на этом прямоугольнике достигаются в его углах: Nmin = 28 + 37 = 65 в точке (1, 1) и Nmax = 28·37 + 37·28 = 2072 в точке (37, 28).
В пункте b) добавляется условие x > y (точка должна лежать ниже пунктирной прямой y = x). Замена d = x − y превращает задачу в такое же уравнение 28d + 65y = N, и тот же приём даёт Nmin = 28 + 65 = 93 (решение x = 2, y = 1) и Nmax = 2·28·65 = 3640 (решение x = 93, y = 28).