В компании 10 человек. Каждому из десяти нравится ровно 5 человек из компании. Докажите, что найдутся два человека, которые нравятся друг другу. Желательно полным ответом.
В компании 10 человек. Каждому из десяти нравится ровно 5 человек из
компании. Докажите, что найдутся два человека, которые нравятся друг другу.
Желательно полным ответом.
Гость
Ответ(ы) на вопрос:
ГостьБросим на плоскость 10 точек, и соединим каждые две точки отрезком (ребром).
Поэтому будет нарисовано ровно ребер.
Если не найдётся пары человек (т.е. ребра), которые нравятся друг другу,
то у каждого из 10-ти человек будет свой набор из 5-ти ребер:
. Противоречие.
Не нашли ответ?
Похожие вопросы