Задача
Фирма записала свои расходы в рублях по 100 статьям бюджета, получив список из 100 чисел (у каждого числа не более двух знаков после запятой). Каждый счетовод взял копию списка и нашёл приближённую сумму расходов, действуя следующим образом. Вначале он произвольно выбрал из списка два числа, сложил их, отбросил у суммы знаки после запятой (если они были) и записал результат вместо выбранных двух чисел. С полученным списком из 99 чисел он проделал то же самое, и так далее, пока в списке не осталось одно целое число. Оказалось, что в итоге все счетоводы получили разные результаты. Какое наибольшее число счетоводов могло работать в фирме?
Решение
Оценка. Счетоводы каждый раз вычисляли целую часть суммы каких-то двух чисел, которая равна сумме их целых частей плюс, возможно, единица. Назовём это добавление единицы оказией. Она могла случаться лишь тогда, когда оба слагаемых были нецелыми. Каждый счетовод получил в итоге сумму целых частей исходных чисел плюс количество оказий, случившихся у него. Поскольку каждая оказия удаляла два нецелых числа, то оказий было максимум 50, а возможных различных результатов – 51.
Пример. Пусть было 50 чисел 0,3 и 50 чисел 0,7. Покажем, как счетоводу получить любой целый результат k от 0 до 50. Сначала он складывает k раз 0,3 + 0,7 и получает k единиц (при k = 0 он складывает 0,3 + 0,3). Далее к имеющемуся уже целому числу он добавляет по очереди все остальные числа без оказий.
Ответ
51 счетовод.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь