В классе 25 человек. Может ли быть так, что 9 из них имеют по 5 друзей в этом классе, 8 – по 4 друга, а 8 – по 6 друзей?

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

Предположим, что каждый человек имеет определённое количество друзей, как указано в вопросе. Поясним, что такое "друзья" в контексте графа. Если человек A и человек B являются друзьями, то между ними существует рёберко, которое соединяет эти вершины. Каждый человек может иметь от 0 до 24 друзей, поскольку в классе 25 человек.

Предположим, что в классе:

• 9 человек имеют по 5 друзей,

• 8 человек имеют по 4 друга,

• 8 человек имеют по 6 друзей.

Для того чтобы проверить, возможно ли такое распределение, нужно учитывать два важнейших принципа:

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

2. Общее количество "друзей" должно быть совместимо с общими связями. Смыслом задачи является то, чтобы количество рёбер (дружеских отношений) могло быть организовано так, чтобы это распределение степеней было возможным.

Теперь подсчитаем:

• 9 человек имеют по 5 друзей — сумма степеней этих людей: $9 \times 5 = 45$,

• 8 человек имеют по 4 друга — сумма степеней этих людей: $8 \times 4 = 32$,

• 8 человек имеют по 6 друзей — сумма степеней этих людей: $8 \times 6 = 48$.

Теперь сложим все степени:

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

Таким образом, не может быть так, чтобы 9 человек имели по 5 друзей, 8 человек — по 4 друга, а 8 человек — по 6 друзей.