** предприятии работают несколько сотрудников, зарплата каждого составляет целое число...

Question

На предприятии работают несколько сотрудников, зарплата каждого составляет целое число тугриков (разные сотрудники могут иметь разную зарплату). Инкассаторы привезли на предприятие 100 монет по 1 тугрику, 100 монет по 2 тугрика, …, 100 монет по 2017 тугриков. Привезенные деньги — это в точности суммарная зарплата всех сотрудников. При каком наибольшем количестве сотрудников зарплату заведомо удастся раздать (так, что каждый получит в точности причитающуюся ему сумму)?

Answer 1

Если сотрудников 102, то может выйти так, что у 101 сотрудника зарплата 1 тугрик, а у оставшегося - все остальные тугрики. В таком случае зарплату раздать не выйдет, так как есть только 100 монет по 1 тугрику.

Пусть сотрудников 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, то очевидно, выплатить получится. 

Comments

получается ответ: 1

---

а если по 200 монет?

---

Что за x обозначено?

---

Я недопонял

---

x - номинал самой дорогой монеты из тех, что еще не распределены.

---

а какой именно ответ? а если монет было бы 1000?

---

Может я не правильно понял условие, но если каждый сотрудник получит по 1 монете, то это и будет наибольшее количество сотрудников. В условии сказано, что разные сотрудники могут иметь разную зарплату, но не сказано что у всех разная. Поэтому 100 сотрудникам раздаем по 1 монете в 1 тугрик, 100 другим сотрудникам раздаем по 1 монете в 2 тугрика и т.д.
Получаем 100*2017=201700 сотрудников

---

...если по 1 тугрику зарплата, то 100х1+100х2+100х2017=202000 работников максимально может быть. А выдать зарплату можно так: выдать 2017 тугриков под роспись 2017 работникам, а они монету в 2017 тугриков разменяют в банке и раздадут друг другу по 1 тугрику.

---

Надо, чтобы каждый получил в точностимсвою зарплату. Поэтому нельзя разменивать деньги, давать группе, чтобы они сами распределили и т.п.

---

не правильно, правильный ответ 101!!!