Парламент

[arqady]

У кажлого из 90 членов парламента не менее 30 друзей. Докажите, что этот парламент можно разбить на три равные фракции так, что у каждого члена парламента есть друг в его фракции.

[TOTAL]

Образуем наибольшее возможное количество камер, в которых сидит пара знакомых друг с другом депутатов. Очевидно, таких камер не менее 30.

Т.к. ещё не сидящие депутаты совсем не знакомы друг с другом, то для каждого их них найдется по крайней мере 15 камер со знакомым. Досадим их к этим знакомым так, что в камерах будет не более 4 человек.

Очевидно, камер с 4 депутатами не более, чем камер с 2 депутатами. Объединим 4-ки с 2-ками, затем 3-ки с 3-ми, затем 2-ки с 2-ками. Получим ровно 15 камер с 6-ю избранниками в каждой. У каждого депутата в его камере есть знакомый, чтобы поговорить.