Тургор(весенний) 2024, 10-11, 6 задача.
В математическом кружке 45 школьников, некоторые дружат. Как ни разбивай их на тройки, в какой-то тройке все будут друг с другом дружить. Докажите, что всех школьников можно разбить на тройки так, чтобы в каждой тройке хотя бы какие-то двое дружили друг с другом.
Подсказка
Попробуйте набирать неполные тройки (в которых одно или 2 ребра из 3)
Решение
Обозначим школьников точками и каждых двух друзей соединим отрезком (ребром). Будем формировать «полуполные» тройки — в которых есть хотя бы одно ребро, но не все три ребра.
Пусть мы не можем из остатка сформировать очередную «полуполную» тройку. Тогда в остатке либо все попарно не дружат, либо все попарно дружат. (В самом деле, пусть в остатке есть и дружащие, и не дружащие. Выберем из них двоих друзей A и B. Тогда все другие люди из остатка дружат и с A, и с B (иначе возникнет полуполная тройка с ребром AB), но при этом в остатке имеется некто C, который с кем-то из остатка не дружит — скажем, с D. Тогда A, C, D — полуполная тройка.)
Если в остатке все попарно не дружат — получается разбиение без полных троек, что противоречит условию. Если в остатке все попарно дружат — получается разбиение из полуполных и полных троек, что решает задачу.