Задача 4 (СПбГУ 2016)
В Стране чудес было единственное, но свое учебное заведение – Университет чудес, управлял им ректор.
Ректор Университета чудес решил повысить рейтинг руководимого им учебного заведения путём материального стимулирования публикационной активности сотрудников. Для этого была сформирована комиссия, предложившая выплачивать ежемесячно в течение года (12 месяцев) определённую надбавку: по 59 золотых монет каждому сотруднику, опубликовавшему в престижных журналах в предшествующем году не менее 4 статей, и по 39 золотых монет – каждому сотруднику, опубликовавшему 3 статьи, и с этой целью выделить из бюджета университета определённую сумму, кратную двенадцати. Однако оказалось, что выделенную сумму не удастся распределить полностью между сотрудниками ни при каком количестве претендентов на надбавку.
Какое наибольшее значение могла иметь эта сумма?
Ответ
Пусть n — предполагаемая ежемесячная выплата, пусть — число претендентов на первую надбавку и — число претендентов на вторую. Тогда и неотрицательны и .
Докажем, что при любом уравнение имеет решение в натуральных числах. Отсюда будет следовать, что при любом уравнение имеет решение в неотрицательных целых числах.
Во-первых, заметим, что , откуда . Следовательно, уравнение имеет решение в целых числах при любом целом n. Если ( ) — произвольное целое решение этого уравнения, то (x0+39; y−59) и (x−39; y+59) — тоже его решения. Поэтому среди целых решений этого уравнения можно выбрать решение (x0 ; y0), для которого . Тогда . Если , то , и, таким образом, (x0;y0) — решение уравнения 59x0+39y0=n в натуральных числах.
Осталось доказать, что уравнение 59x0+39y0=2300 не имеет решений в натуральных числах. Рассуждаем от противного. Пусть натуральные числа x0 и y0 таковы, что 59x0+39y0=2300. Тогда x0 делится на 39, откуда . Противоречие. Итак, 2203 рублей — наибольшая сумма, кратная 12, которая не может быть выплачена в месяц. Следовательно, наибольшее значение выделенной для надбавок суммы могло составить рублей.
Ответ:
26436 рублей.