|
|
 |
Условие
Совет из 2000 депутатов решил утвердить государственный бюджет, содержащий 200 статей расходов. Каждый депутат подготовил свой проект бюджета, в котором указал по каждой статье максимально допустимую, по его мнению, величину расходов, проследив за тем, чтобы общая сумма расходов не превысила заданную величину S. По каждой статье совет утверждает наибольшую величину расходов, которую согласны выделить не менее k депутатов. При каком наименьшем k можно гарантировать, что общая сумма утверждённых расходов не превысит S?
Решение
Если k ≤ 1990, может случиться, что первые 10 депутатов предложат ничего не выделять по первой статье расходов, а по остальным выделить по S/199. Следующие 10 депутатов ничего не выделят по второй статье и выделят по S/199 по остальным и так далее. В результате по каждой статье будет утверждена сумма расходов в S/199, а по всем двумстам статьям
200/199 S > S.
Если k = 1991, то после утверждения расходов по всем статьям окажется, что по каждой статье не более девяти депутатов предложили величину расходов, меньшую утверждённой. Поскольку 200·9 < 2000, найдётся депутат, который по всем статьям предложил величину расходов, не меньшую утверждённой. Но сумма предложенных им расходов не больше S, а значит, и утверждённая сумма тоже.
Ответ
k = 1991.
