Кто выиграл бы споры если бы Сеня утверждал что сможет нарисовать граф со 100 вершинами степени которых равны 1, 1, 2, 2, … 50, 50?

Давай разберем задачу о графе с вершинами степени 1, 1, 2, 2, …, 50, 50.

Основные концепции:

1. Граф: Совокупность вершин и рёбер.
2. Степень вершины: Количество рёбер, выходящих из данной вершины.
3. Условие существования графа: Сумма степеней всех вершин в графе должна быть чётной, поскольку каждое ребро добавляет 1 к степени двух вершин.

Решение:

1. Составление списка степеней:

   У нас дано 100 вершин со следующими степенями:

   • 1, 1, 2, 2, ..., 50, 50

2. Поиск суммы всех степеней:

   Каждая степень от 1 до 50 повторяется дважды. Поэтому сумма степеней будет:

   \[ 1 \times 2 + 2 \times 2 + 3 \times 2 + \ldots + 50 \times 2 \]

   Это можно упростить как:

   \[ 2 \times (1 + 2 + 3 + \ldots + 50) \]

3. Вычисление суммы от 1 до 50:

   Сумма первых \( n \) натуральных чисел вычисляется по формуле:

   \[ S_n = \frac{n(n + 1)}{2} \]

   Для \( n = 50 \):

   \[ S_{50} = \frac{50 \times 51}{2} = 1275 \]

   Следовательно, общая сумма степеней будет:

   \[ 2 \times 1275 = 2550 \]

4. Проверка на чётность:

   Сумма 2550 — чётное число.

Вывод:

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