В комнате находятся 19 человек. Может ли каждый из них быть знаком ровно с тремя другими?
от

1 Ответ

дано:  
В комнате находятся 19 человек. Каждый из них знаком ровно с тремя другими.

найти:  
Можно ли организовать такую ситуацию, при которой каждый из 19 человек будет знаком ровно с тремя другими?

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

1. Если у каждого из 19 человек по 3 знакомства, то каждая вершина графа имеет степень 3.  
   Степень вершины - это количество рёбер, соединяющих эту вершину с другими вершинами.

2. Сумма степеней всех вершин в графе равна удвоенному числу рёбер (по теореме о степени):
   
   S = сумма степеней = 3 * количество вершин = 3 * 19 = 57.

3. Поскольку сумма степеней равна удвоенному количеству рёбер, мы имеем:

   2 * E = 57,

   где E - количество рёбер в графе.

4. Отсюда можем выразить E:

   E = 57 / 2 = 28.5.

5. Однако количество рёбер (E) должно быть целым числом, так как нельзя иметь половину ребра.

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

ответ:  
Нет, не может быть организовано такое знакомство среди 19 человек.
от