Question

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

Answer 1

Если сотрудников >2 017 000, то 2 017 001 сотрудник точно ничего не получит, т. к. каждый сотрудник от 1-ого до 2 017 000-ого получил ≥1 мон., а всего монет 2 017 000. Значит, макс. возможное кол-во сотрудников 
≤2 017 000, а 2 017 000 возможно (каждый получает по 1 монете)
Ответ: 2 017 000 сотрудников

Answer 2

Для того чтобы найти наибольшее количество сотрудников, при котором удастся раздать зарплату в точности, нужно найти наибольшее целое число, которое является делителем суммарной зарплаты всех сотрудников и при этом не превышает количество монет каждого номинала.

Суммарная зарплата всех сотрудников можно найти как сумму арифметической прогрессии, где первый элемент - 1, второй - 2, и т.д., последний - 2017. Формула суммы арифметической прогрессии: S = (a1 + an) * n / 2, где a1 - первый элемент, an - последний элемент, n - количество элементов.

Подставляем значения: S = (1 + 2017) * 2017 / 2 = 2037178.

Теперь находим наибольший делитель числа 2037178, который меньше или равен 1000 (максимальное количество монет каждого номинала). Это можно сделать путем последовательного деления числа 2037178 на все числа от 1 до 1000 и проверки остатка от деления. Но для ускорения процесса можно воспользоваться алгоритмом Евклида для поиска наибольшего общего делителя.

После проведения вычислений, наибольшее количество сотрудников, при котором удастся раздать зарплату в точности, составляет 1009 человек.