В компании 10 человек. Каждому из них нравится не меньше 5 человек в этой компании. Найдутся ли в этой компании 2 человека, которые нравятся друг другу?

Да, найдутся. Давайте разберем эту задачу с помощью теории графов. 1. Представим каждого человека как вершину графа (всего 10 вершин). 2. Если человек А нравится человеку Б, проведем ребро между ними. В условии сказано, что каждому нравится не меньше 5 человек. Это значит, что степень каждой вершины $\deg(v) \ge 5$. 3. Сумма степеней всех вершин равна удвоенному количеству ребер в графе (лемма о рукопожатиях): $\sum \deg(v) = 2E$. 4. Так как у нас 10 вершин и у каждой степень не меньше 5, то сумма степеней равна $10 \times 5 = 50$ (это минимально возможное значение). 5. Значит, $2E \ge 50$, то есть ребер в графе минимум 25. Теперь рассмотрим задачу «от противного». Предположим, что не существует двух людей, которым бы они нравились друг другу. Это значит, что в графе нет ребер, которые были бы «двусторонними» (то есть если А нравится Б, то Б не может нравиться А). В полном графе из 10 человек (где каждый нравится каждому) всего ребер будет $\frac{10 \times 9}{2} = 45$. Если симпатии не взаимны, то каждое ребро графа направлено (это ориентированный граф). Если А нравится Б, это направленное ребро $A \to B$. Если А и Б не могут нравиться друг другу взаимно, значит, мы не можем провести «двустороннее» ребро. У нас есть 10 человек. Всего пар людей $\binom{10}{2} = 45$. В каждой паре может быть только одно «одностороннее» отношение, чтобы они не нравились друг другу взаимно. Значит, максимально возможное количество ребер в таком графе — 45. Но давайте посчитаем иначе: каждый человек «отдает» свои симпатии 5 другим. Всего симпатий $10 \times 5 = 50$. Если нет взаимных симпатий, то каждые 2 человека могут образовать максимум 1 связь (либо А нравится Б, либо Б нравится А, но не оба). У нас 45 пар. Чтобы распределить 50 симпатий так, чтобы ни одна не была взаимной, нам нужно «разместить» 50 стрелок в 45 доступных слотах (каждая пара — это 1 слот). По принципу Дирихле: если 50 стрелок (симпатий) распределяются по 45 парам, то хотя бы в одной паре окажется больше одной стрелки. А если в одной паре две стрелки (А нравится Б и Б нравится А), значит, они нравятся друг другу. **Ответ:** Да, такие 2 человека обязательно найдутся.