Задача 4 (СПбГУ 2016)

Пусть $n$ — предполагаемая ежемесячная выплата, пусть $x_0$ — число претендентов на первую надбавку и $y_0$ — число претендентов на вторую. Тогда $x_0$ и $y_0$ неотрицательны и $59x_0 + 39y_0 = n$ .
Докажем, что при любом $n > 59 \cdot 39 = 2301$ уравнение $59x + 39y = n$ имеет решение в натуральных числах. Отсюда будет следовать, что при любом $n \ge 58 \cdot 38 = 2204$ уравнение $59x_0 + 39y_0 = n$ имеет решение в неотрицательных целых числах.
Во-первых, заметим, что $59 \cdot 2 + 39 \cdot (-3) = 1$, откуда $59 \cdot (2n) + 39 \cdot (-3n) = n$. Следовательно, уравнение $59x + 39y = n$ имеет решение в целых числах при любом целом $n$. Если ($x_0$; $y_0$) — произвольное целое решение этого уравнения, то ($x_0 + 39$; $y - 59$) и ($x - 39$; $y + 59$) — тоже его решения. Поэтому среди целых решений этого уравнения можно выбрать решение ($x_0$ ; $y_0$) , для которого $1 \le x_0 \le 39$. Тогда $59x_0 \le 59 \cdot 39$. Если $n > 59 \cdot 39$, то $y_0 = \frac{n - 59x_0}{39} >0$, и, таким образом, ($x_0 ; y_0$) — решение уравнения $59x_0 + 39y_0 = n$ в натуральных числах.
Осталось доказать, что уравнение $59x_0 + 39y_0 = 2300$ не имеет решений в натуральных числах. Рассуждаем от противного. Пусть натуральные числа $x_0$ и $y_0$ таковы, что $59x_0 + 39y_0 = 2300$. Тогда $x_0$ делится на $39$, откуда $59x_0 + 39y_0 > 59 \cdot 39 = 2301$. Противоречие. Итак, $2203$ рублей — наибольшая сумма, кратная $12$, которая не может быть выплачена в месяц. Следовательно, наибольшее значение выделенной для надбавок суммы могло составить $2203 \cdot 12 = 26436$ рублей.