Question

На трибунах арены «Динамо» собралось 2015 болельщиков. Могло ли так случиться, что для каждого неотрицательного целого k выполняется следующее свойство: если есть болельщик, знакомый ровно с k другими болельщиками, то есть ровно k болельщиков с таким свойством?

Answer 1

Предположим, что указанное свойство было выполнено. Представим болельщиков в виде вершин графа, а их знакомства - в виде рёбер. Группой вершин степени k назовём множество всех вершин степени k. По условию задачи в группе вершин степени k будет ровно k вершин. Если k чётно, то сумма степеней вершин в группе тоже чётна, а если k нечётно, то сумма степеней группы нечётна. Так как 2015 - нечётное число, групп с нечётным k будет нечётное число, что означает, что сумма степеней всех вершин нечётна, что неверно, так как сумма степеней всех вершин любого графа чётна.

Ответ: Не могло.

Answer 2

Это свойство называется регулярностью графа.

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

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

Для 2015 болельщиков регулярный граф существует, если число вершин кратно 5. При этом количество ребер будет равно 2015k/2, где k - количество вершин, связанных с каждой вершиной.

Если разложить 2015 на простые множители, то получим 2015 = 5 * 13 * 31. Поскольку 5 - это простое число и кратно 5, то для 2015 болельщиков существует регулярный граф.

Таким образом, для каждого болельщика найдется ровно 4 других болельщика, с которыми он знаком. А каждый из этих 4 болельщиков знаком с еще 4-мя другими болельщиками, что обеспечивает регулярность графа.