Задача 4 (СПбГУ 2016)
В Стране чудес было единственное, но свое учебное заведение – Университет чудес, управлял им ректор. Ректор Университета чудес решил повысить рейтинг руководимого им учебного заведения путём материального стимулирования публикационной активности сотрудников. Для этого была сформирована комиссия, предложившая выплачивать ежемесячно в течение года (12 месяцев) определённую надбавку: по $59$ золотых монет каждому сотруднику, опубликовавшему в престижных журналах в предшествующем году не менее $4$ статей, и по $39$ золотых монет – каждому сотруднику, опубликовавшему $3$ статьи, и с этой целью выделить из бюджета университета определённую сумму, кратную двенадцати. Однако оказалось, что выделенную сумму не удастся распределить полностью между сотрудниками ни при каком количестве претендентов на надбавку. Какое наибольшее значение могла иметь эта сумма?
Решение
Пусть $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$ рублей. Ответ: $26436$ рублей.