Задача 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 \geq 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 ) — произвольное целое решение этого уравнения, то (x0+39; y−59) и (x−39; y+59) — тоже его решения. Поэтому среди целых решений этого уравнения можно выбрать решение (x0 ; y0), для которого 1 \leq x_0 \leq 39. Тогда 59x_0 \leq 59 \cdot 39. Если n>59 \cdot 39, то y_0=\frac{n−59x_0}{39}>0, и, таким образом, (x0;y0) — решение уравнения 59x0+39y0=n в натуральных числах.
Осталось доказать, что уравнение 59x0+39y0=2300 не имеет решений в натуральных числах. Рассуждаем от противного. Пусть натуральные числа x0 и y0 таковы, что 59x0+39y0=2300. Тогда x0 делится на 39, откуда 59x_0+39y_0>59 \cdot 39=2301. Противоречие. Итак, 2203 рублей — наибольшая сумма, кратная 12, которая не может быть выплачена в месяц. Следовательно, наибольшее значение выделенной для надбавок суммы могло составить 2203 \cdot 12=26436 рублей.
Ответ:
26436 рублей.