Задача ЕГЭ
В одном из заданий на конкурсе бухгалтеров требуется выдать премии сотрудникам некоторого отдела на общую сумму 800 000 рублей (размер премии каждого сотрудника — целое число, кратное 1000). Бухгалтеру дают распределение премий, и он должен их выдать без сдачи и размена, имея 250 купюр по 1000 рублей и 110 купюр по 5000 рублей.
При каком наибольшем количестве сотрудников в отделе задание удастся выполнить при любом распределении размеров премий?
Решение. Самое главное в понимании условия задачи — это слово «любое» в распределении размеров премий — чтобы не случилось его подмены на какое-нибудь конкретное, которое умеет сделать раздающий премии бухгалтер или назначающий премии начальник (например, раздать всем поровну).
Покажем, что для 64 или большего числа сотрудников любое распределение премий невозможно. Распределим премии так: 63 человека должны получить по 4 тысячи, один — всё остальное, остальные — ничего. Тогда 1-тысячных купюр потребуется 63∙4 = 252 — эта задача невыполнима, поскольку в распоряжении бухгалтера имеется всего 250 таких купюр.
Если же сотрудников не больше 63, то выберем всех, кроме одного. Будем выдавать им премии, используя не более четырёх тысячных купюр, пока не кончатся пятитысячные. Если пятитысячные купюры закончились, то оставшиеся премии выдать точно удастся. Если же нет, то все премии, кроме одной, будут выданы, а последний просто заберёт все оставшиеся деньги.
Ответ: 63.