В компании 10 человек. Каждому из десяти нравится ровно 5 человек из компании. Докажите, что найдутся два человека, которые нравятся друг другу.
Желательно полным ответом.
Answers & Comments
AnGeL548
Бросим на плоскость 10 точек, и соединим каждые две точки отрезком (ребром). Поэтому будет нарисовано ровно ребер.
Если не найдётся пары человек (т.е. ребра), которые нравятся друг другу, то у каждого из 10-ти человек будет свой набор из 5-ти ребер: . Противоречие.
6 votes Thanks 7
katepureshka
Представим между каждым человек и пятью, которые ему нравятся линии. Если их посчитать, то получится 45 линий. Решаем от противного: Если не найдётся пары линий, которые нравятся друг другу, то у каждого из 10-ти человек будет свой набор из 5-ти, то есть у всех вместе будет 50 линий. 50>45 - Противоречие. Просто копировать не надо)
Answers & Comments
Поэтому будет нарисовано ровно ребер.
Если не найдётся пары человек (т.е. ребра), которые нравятся друг другу,
то у каждого из 10-ти человек будет свой набор из 5-ти ребер:
. Противоречие.
Решаем от противного:
Если не найдётся пары линий, которые нравятся друг другу,
то у каждого из 10-ти человек будет свой набор из 5-ти, то есть у всех вместе будет 50 линий. 50>45 - Противоречие. Просто копировать не надо)