|
|
 |
Условие
Каждый из 450 депутатов парламента дал пощёчину ровно одному своему коллеге.
Докажите, что можно избрать парламентскую комиссию из 150 человек, среди
членов которой никто никого не бил.
Решение 1
Рассмотрим наибольшую группу A депутатов, в которой никто никого не бил. Тогда каждый из оставшихся депутатов попадает в группу B тех, кого били депутаты из A, либо в группу C тех, кто бил депутатов из A (иначе его можно было бы добавить к A, что противоречит её максимальности). Ясно, что в B депутатов не больше чем в A. Но и в C депутатов не больше чем в A, поскольку в ней никто никого не бил. Следовательно, в A не меньше 150 депутатов.
Решение 2
Согласно задаче 108403 депутатов можно разбить на три группы, в каждой из которых никто никого не бил. В наибольшей из них не меньше 150 депутатов.
Замечания
1. 3 балла.
2. Ср. с задачей 107762.
