Давайте рассмотрим данную задачу с использованием теории графов. Построим двудольный граф, в котором одна доля будет представлять мальчиков, а другая — девочек. Ребро будет проводить от мальчика к девочке, если они дружат. У нас есть 13 мальчиков и 17 девочек.
Согласно условию, каждый мальчик дружит хотя бы с 4 девочками. Это значит, что сумма степеней вершин в части мальчиков будет не менее:
[
\text{Общая связь мальчиков} = 13 \times 4 = 52.
]
Теперь обозначим количество дружб, которое имеет каждая девочка, как ( d_1, d_2, \ldots, d_{17} ). Сумма степеней вершин в части девочек равна:
[
d_1 + d_2 + \ldots + d_{17} = \text{Общая связь девочек}.
]
По свойству двудольного графа, сумма степеней вершин в обоих долях должна совпадать. Таким образом, у нас есть:
[
d_1 + d_2 + \ldots + d_{17} = 52.
]
Теперь, чтобы доказать, что найдется хотя бы одна девочка, которая дружит не менее чем с 4 мальчиками, предположим обратное: что все девочки дружат не более чем с 3 мальчиками. В этом случае максимальная сумма степеней всех девочек будет:
[
d_1 + d_2 + \ldots + d_{17} \leq 3 \times 17 = 51.
]
Однако, у нас есть ранее полученное неравенство:
[
d_1 + d_2 + \ldots + d_{17} = 52,
]
что противоречит предположению. Следовательно, наше предположение неверно, и значит, найдется хотя бы одна девочка, которая дружит не менее чем с 4 мальчиками.
Таким образом, задача доказана.
