На предприятии работают несколько сотрудников, зарплата каждого составляет целое число тугриков (разные сотрудники могут иметь разную зарплату). Инкассаторы привезли на предприятие 150 монет по 1 тугрику, 150 монет по 2 тугрика, …, 150 монет по 2017 тугриков. Привезенные деньги — это в точности суммарная зарплата всех сотрудников. При каком наибольшем количестве сотрудников зарплату заведомо удастся раздать (так, что каждый получит в точности причитающуюся ему сумму)?
More Questions From This User See All
Answers & Comments
Пусть сотрудников 101 или меньше. Упорядочим их по убыванию оставшегося размера выплаты. Будем распределять монеты так:
Заплатимпервому в очереди 1 монетой максимального номинала из имеющихся, азатем поставим его в очередь согласно оставшемуся размеру выплаты.
Почемуэто сработает: если максимальный номинал монеты x >= 3, то осталосьвыплатить не меньше, чем 100*(1+2+3+...+(x-1))+x = 50x^2-49x, у первого вочереди остаток к выплате не меньше, чем (50x^2-49x)/101 >= x.
Еслиx = 2, то первому в очереди надо выплатить не меньше 2 тугриков,поскольку в противном случае сумма всех монет была бы не больше 101 (неболее 101 человека, каждому надо выплатить не более 1 тугрика), но суммавсех монет не меньше, чем 100*1 + 2 = 102.
Если x = 1, то очевидно, выплатить получится.