У жадины Вовочки 25 одноклассников. В честь своего дня рождения он принёс в класс 200 конфет. Чтобы он не съел всё сам, мама Вовочки велела раздать конфеты так, чтобы у любых 16 его одноклассников суммарно оказалось хотя бы 100 конфет. Какое наибольшее количество конфет Вовочка может оставить себе, выполнив при этом просьбу мамы?

Пусть Вовочка раздаст одноклассникам конфеты так: у 25 человек будет по $a_1,a_2,\dots ,a_{25}$ конфет. Нужно оставить себе как можно больше, значит нужно минимизировать количество конфет, которое он отдаст.

Расположим количества конфет по возрастанию:

Самые «опасные» 16 одноклассников — это те, у кого конфет меньше всего. Если у них вместе будет хотя бы 100 конфет, то у любых других 16 человек тоже будет не меньше.

Значит, необходимо:

Обозначим количество конфет у 16-го человека через $x$. Тогда все остальные 9 человек должны получить не меньше $x$ конфет, потому что список отсортирован.

Чтобы раздать как можно меньше, выгодно сделать сумму первых 16 человек ровно 100. Тогда всего будет:

Нужно сделать $x$ как можно меньше. Но первые 16 человек получают не больше $x$ каждый, поэтому максимум их общая сумма равна:

Она должна быть не меньше 100:

Отсюда:

Так как конфеты считаются штуками, получаем:

Тогда минимальное количество конфет, которое нужно отдать:

Осталось проверить, можно ли так сделать. Например, раздать:

• 6 одноклассникам по 5 конфет;

• 19 одноклассникам по 7 конфет.

Всего будет:

Самые бедные 16 человек в таком случае получат:

Условие выполняется.

Значит, Вовочка может оставить себе:

Ответ: 37 конфет.