Олимпиадная задача по теории графов для 8–10 классов от Волченкова С. Г.
25 мальчиков и несколько девочек собрались на вечеринке и обнаружили забавную закономерность. Если выбрать любую группу не меньше чем из 10 мальчиков, а потом добавить к ним всех девочек, знакомых хотя бы с одним из этих мальчиков, то в получившейся группе число мальчиков окажется на 1 меньше, чем число девочек. Докажите, что некоторая девочка знакома не менее чем с 16 мальчиками.
Разобрать решение
По условию имеется ровно 26 девочек, знакомых хотя бы с одним мальчиком из 25. Выберем произвольно мальчика M1. Для оставшихся 24 мальчиков ровно 25 девочек знакомы хотя бы с одним из них. Тогда девочка D1, не входящая в эти 25, знакома только с одним мальчиком M1. Аналогично, обозначив остальных мальчиков M2, ..., M25, найдём таких девочек D2, ..., D25, что Di знакома только с Mi. Рассмотрим оставшуюся девочку (отличную от D1, ..., D25). Если она знакома менее чем с 16 мальчиками, то для группы из k ≥ 10 мальчиков, не знакомых с ней, найдётся ровно k девочек, знакомых хотя бы с одним из них. Противоречие.
Обсуждение
0Комментариев пока нет.