Задача 67427
|
|
 |
Условие
В математическом кружке $45$ школьников, некоторые дружат. Как ни разбивай их на тройки, в какой-то тройке все будут друг с другом дружить. Докажите, что всех школьников можно разбить на тройки так, чтобы в каждой тройке хотя бы какие-то двое дружили друг с другом.Решение 1
Докажем аналогичное утверждение для $3N$ школьников: если при любом разбиении их на $N$ троек в какой-то тройке все будут друг с другом дружить, то всех школьников можно разбить на $N$ троек так, чтобы в каждой тройке хотя бы какие-то двое дружили друг с другом.Достаточно доказать, что можно выделить $N$ отдельных пар друзей, тогда, подсоединив к каждой паре одного из оставшихся школьников, получим требуемое. Пусть можно выделить максимум $N-1$ пар (людей в них будем обозначать чёрными точками). Тогда осталось минимум $N+2$ человека (их будем обозначать белыми точками), и среди них никто не дружит. Каждые две точки, соответствующие друзьям, соединим отрезком (ребром).
Заметим, что для каждой пары из наших $N-1$ пар чёрных точек есть максимум одна белая точка, соединённая с обеими вершинами пары (иначе можно вместо одной пары чёрных точек создать две новые). Тогда будем постепенно присоединять к каждой чёрной паре по белой точке так, чтобы не получилось полной тройки (в которой все друг с другом дружат). Это получится сделать для всех чёрных пар, и ещё три белые точки останутся, образуя пустую тройку (среди этих троих никто не дружит) — мы получили разбиение на тройки, противоречащее условию!
Решение 2
Как и в предыдущем решении, докажем утверждение для $3N$ школьников. Обозначим школьников точками и каждых двух друзей соединим отрезком (ребром). Будем формировать «полуполные» тройки — в которых есть хотя бы одно ребро, но не все три ребра. Пусть мы не можем из остатка сформировать очередную «полуполную» тройку. Тогда в остатке либо все попарно не дружат, либо все попарно дружат. (В самом деле, пусть в остатке есть и дружащие, и не дружащие. Выберем из них двоих друзей $A$ и $B$. Тогда все другие люди из остатка дружат и с $A$, и с $B$ (иначе возникнет полуполная тройка с ребром $AB$), но при этом в остатке имеется некто $C$, который с кем-то из остатка не дружит — скажем, с $D$. Тогда $A$, $C$, $D$ — полуполная тройка.)Если в остатке все попарно не дружат — получается разбиение без полных троек, что противоречит условию. Если в остатке все попарно дружат — получается разбиение из полуполных и полных троек, что решает задачу.
