В одном из заданий на конкурсе бухгалтеров требуется выдать премии сотрудникам некоторого отдела на общую сумму 800 000 рублей (размер премии каждого сотрудника — целое число, кратное 1000). Бухгалтеру дают распределение премий, и он должен их выдать без сдачи и размена, имея 250 купюр по 1000 рублей и 110 купюр по 5000 рублей.
а) Удастся ли выполнить задание, если в отделе 40 сотрудников и все должны получить поровну?
б) Удастся ли выполнить задание, если ведущему специалисту надо выдать 80 000 рублей, а остальное поделить поровну на 80 сотрудников?
в) При каком наибольшем количестве сотрудников в отделе задание удастся выполнить при любом распределении размеров премий?
Посмотреть решение
Предварительное решение, не проверено экспертом.
Ранее доступное решение переведено в общий параметрический рецепт; новая независимая проверка не проводилась.
Шаг 1. Измеряем премии в тысячах рублей. Чтобы выплатить целую премию p купюрами 1 и 5, нужно не меньше pmod5 единичных купюр. Для всего распределения пусть R - сумма этих остатков. Выплата возможна ровно при R не больше имеющегося числа единичных купюр O: после минимальных остатков оставшиеся единичные купюры заменяют некоторое количество пятёрок. Всего денег ровно T, поэтому R≡T по модулю 5 и остальные ограничения выполняются автоматически.
Шаг 2. Записываем точный список параметров или построенное распределение.
T=(0;250)
Шаг 3. Да. Построенный пример удовлетворяет всем условиям.
Шаг 1. Измеряем премии в тысячах рублей. Чтобы выплатить целую премию p купюрами 1 и 5, нужно не меньше pmod5 единичных купюр. Для всего распределения пусть R - сумма этих остатков. Выплата возможна ровно при R не больше имеющегося числа единичных купюр O: после минимальных остатков оставшиеся единичные купюры заменяют некоторое количество пятёрок. Всего денег ровно T, поэтому R≡T по модулю 5 и остальные ограничения выполняются автоматически.
Шаг 2. Записываем точный список параметров или построенное распределение.
T=(320;250)
Шаг 3. Нет. Полученное необходимое ограничение исключает такую возможность.
Шаг 1. Измеряем премии в тысячах рублей. Чтобы выплатить целую премию p купюрами 1 и 5, нужно не меньше pmod5 единичных купюр. Для всего распределения пусть R - сумма этих остатков. Выплата возможна ровно при R не больше имеющегося числа единичных купюр O: после минимальных остатков оставшиеся единичные купюры заменяют некоторое количество пятёрок. Всего денег ровно T, поэтому R≡T по модулю 5 и остальные ограничения выполняются автоматически.
Шаг 2. Для N сотрудников сумма остатков не больше 4N. В данном домене T и O кратны пяти. Значит, при 4N<O+5 всегда R≤O. Для первого N с 4N≥O+5 строим N положительных остатков от 1 до 4 с суммой O+5, а оставшуюся сумму T−O−5, кратную пяти, прибавляем к одной премии. Такое распределение требует слишком много единичных купюр. Разделение любой премии на две положительные не уменьшает сумму остатков, поэтому контрпример продолжается на все большие количества сотрудников, для которых распределение возможно.
N=63
Шаг 3. Записываем точный список параметров или построенное распределение.