7 Каждый из 450 депутатов парламента дал пощёчину ровно одному своему коллеге. Доказать, что можно избрать парламентскую комиссию из 150 человек, среди членов ко- торой никто никого не бил.

Ответ: Доказано, что можно избрать парламентскую комиссию из 150 человек, среди членов которой никто никого не бил.

Доказательство:

• Рассмотрим граф, где вершины - депутаты, а ребра - пощечины. Ориентируем каждое ребро от давшего пощечину к получившему. Таким образом, у каждого депутата есть ровно одно исходящее ребро.

• Теперь построим множество независимых депутатов следующим образом: возьмем произвольного депутата A. Если он дал пощечину депутату B, то включим A в нашу комиссию, а B исключим из рассмотрения (или наоборот, включим B, а A исключим). Таким образом, мы обеспечим, что в комиссии не будет пары, где один дал пощечину другому.

• Разделим всех 450 депутатов на пары (A, B), где A дал пощечину B. В каждой паре выберем одного депутата в комиссию. Так как каждый депутат дал пощечину ровно одному коллеге, то таких пар будет 450. Выбирая по одному депутату из каждой пары, мы получим комиссию, где никто никого не бил.

• Теперь оценим размер комиссии. В каждой паре мы выбираем одного человека, значит, размер комиссии будет равен половине от общего числа депутатов, то есть 450 / 2 = 225.

• Таким образом, можно избрать комиссию из 225 человек, где никто никого не бил. Так как 225 > 150, то, тем более, можно избрать комиссию из 150 человек, выбрав 150 депутатов из этих 225.

Ответ: Доказано, что можно избрать парламентскую комиссию из 150 человек, среди членов которой никто никого не бил.