Задача на графы (подсчет смежных пар)

[sasha-parazit]

Пожалуйста, подскажите идею решения следующей задачи:
В первый класс школы зачислены 90 детей. У каждого из них не менее 30 друзей среди остальных первоклассников. Докажите, что всех 90 человек можно так разбить на три класса по 30 человек, чтобы у каждого был хотя бы один друг в его классе.

[sasha-parazit]

Кажется, решил.

Рассмотрим дополнительный граф, т.е. граф состоящий из того же множества вершин, в котором вершины смежны тогда и только тогда когда в исходном графе вершины не смежны. Количество подграфов $K_{1,29}$ в дополнительном графе не превосходит величины $90C^{29}_{59}$.
Пусть имеется некоторое разбиение на три класса, фиксированный подграф $K_{1,29}$ "портит" разбиение, если все его вершины содержатся в каком-то одном классе. Если разбиение не испорченно ни одним подграфом, то оно "решает задачу". Таким образом заключаем, что максимальное количество "испорченных" разбиений не превосходит $270C^{29}_{59}$. Всего разбиений на три класса $C^{30}_{90} C^{30}_{60} C_{30}^{30}$. Очевидно, что $C^{30}_{90} C^{30}_{60} C_{30}^{30} > 270C^{29}_{59}$. Значит, нужное разбиение на классы существует.

Не ошибся ли я?

[Skeptic]

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

Можно без ущерба для задачи количество учеников и их дружественные связи уменьшить в 10 раз.

[DeBill]

sasha-parazit
А разве один подграф портит только три разбиения? А не $3\cdot C^{30}_{60}$?

-- 10.01.2017, 19:59 --

Но даже с учетом этого, вроде бы, получится...

[sasha-parazit]

Спасибо, DeBill.
Да, действительно, портит $3\cdot C^{30}_{60}$ разбиений. Но, все равно соответствующее неравенство $C^{30}_{90} C^{30}_{60} C_{30}^{30} > 270C^{29}_{59}C^{30}_{60}$ выполняется. Задача решена.