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

Для решения данного вопроса будем использовать теорему о рукопожатиях и теорию графов, так как они предоставляют удобные инструменты для анализа подобных ситуаций.

Рассмотрим эту задачу в терминах теории графов. Пусть каждый человек в компании будет представлять вершину графа ( G ), а наличие симпатии между двумя людьми будет представлять ребро, соединяющее две вершины. Нам известно, что в графе ( G ) каждая вершина имеет степень не менее 5, то есть из каждой вершины выходит не меньше 5 рёбер.

Граф с 10 вершинами, где каждая вершина соединена хотя бы с 5 другими вершинами, называется графом с минимальной степенью (\delta(G) \geq 5).

Попробуем доказать, что найдется хотя бы одна пара вершин (людей), которые нравятся друг другу (то есть между ними есть ребро в графе ( G )).

1. Сумма степеней вершин: В графе ( G ) с ( n ) вершинами сумма степеней всех вершин равна удвоенному количеству рёбер (по теореме о рукопожатиях). Обозначим количество рёбер через ( E ). Тогда: [ \sum{v \in V(G)} \deg(v) = 2|E| ] В нашем случае (\sum{v \in V(G)} \deg(v) \geq 10 \times 5 = 50), следовательно, [ 2|E| \geq 50 \implies |E| \geq 25 ]

2. Дополнение графа: Рассмотрим дополнение графа ( G ), обозначенное как ( \overline{G} ). В графе ( \overline{G} ) вершины соединены ребром тогда и только тогда, когда они не соединены в ( G ).

   Поскольку в ( G ) каждая вершина имеет степень не менее 5, в ( \overline{G} ) каждая вершина имеет степень не более ( 10 - 5 - 1 = 4 ). Заметим, что ( \overline{G} ) также имеет 10 вершин.

3. Рассмотрение мин. степени дополнения: Если в графе ( \overline{G} ) каждая вершина имеет степень не более 4, то: [ \sum{v \in V(\overline{G})} \deg{\overline{G}}(v) \leq 10 \times 4 = 40 ]

4. Общий вывод: В ( G ) у нас много рёбер (минимум 25), а в ( \overline{G} ) – мало (максимум 20). Если бы не было ни одной пары людей, которые нравятся друг другу, то ( G ) не имел бы ни одного ребра. Но это противоречит нашему условию, что сумма степеней вершин в ( G ) равна или превышает 50, и, следовательно, количество рёбер в ( G ) должно быть как минимум 25.

Таким образом, по принципу Дирихле, в ( G ) найдётся хотя бы одна пара вершин, соединённых ребром, то есть найдутся два человека, которые нравятся друг другу.

Следовательно, в компании из 10 человек, у каждого из которых есть не менее 5 симпатий, обязательно существует хотя бы одна пара человек, которые нравятся друг другу.

Для доказательства этого утверждения применим принцип Дирихле (или принцип ящика и шаров).

Предположим, что у каждого человека в компании нравится как минимум 5 других человек. Тогда общее количество "понравившихся" пар будет не меньше, чем 10 * 5 = 50 пар.

Однако, в компании всего 10 человек, следовательно, максимальное количество различных пар может быть только 10 * 9 / 2 = 45 пар.

Из этого следует, что как минимум одна пара людей должна понравиться друг другу. Таким образом, найдутся 2 человека, которые нравятся друг другу.