На вечере присутствуют девять человек. Может ли так оказаться, что каждый из них знаком только с тремя участниками вечера?

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

В данной ситуации граф будет таким: каждая вершина имеет степень 3, то есть каждый человек (вершина) соединен с тремя другими людьми (тремя ребрами). Нам нужно понять, может ли такой граф существовать для 9 вершин.

Для начала определим общее количество рёбер в таком графе. Если у нас есть 9 вершин, и каждая вершина имеет степень 3, то общее количество рёбер будет равно половине произведения числа вершин на степень каждой вершины (так как каждое ребро соединяет две вершины):

Количество рёбер должно быть целым числом, но в данном случае мы получаем 13,5, что невозможно. Это значит, что такой граф не может существовать, так как количество рёбер должно быть целым числом.

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