#комбинаторика #задача

Предлагаем вам сегодня задачу С.Л. Берлова, Д.В. Карпова с кубка Колмогорова 1999 года!


Не более 10% жителей государства Х — враги народа. На день рождения президента каждый гражданин государства сделал ему подарок: написал в ДГБ письмо со своей подписью, разоблачающее одного из знакомых ему врагов народа. При этом известно, что честные граждане разоблачали только истинных врагов, а враги могли как разоблачить других врагов, так и оклеветать честных граждан.
a) Известно, что у каждого гражданина этого государства менее 500 знакомых. Докажите, что на основании полученных данных ДГБ может посадить некоторое количество граждан так, чтобы больше половины посаженных была врагами народа.
b) Не читая этих доносов, президент приказал посадить всех граждан, на которых поступило не менее, чем 1998 доносов. Верно ли, что более половины посаженных обязательно являются врагами народа?