На конференцию собрались учёные. Могло ли оказаться так, что пятеро из них знакомы ровно с тремя другими, а все остальные имеют ровно четверых знакомых среди собравшихся?

Решение:

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

Условие задачи означает, что в графе есть 5 вершин степени 3 (пятеро знакомы ровно с тремя другими) и n - 5 вершин степени 4 (все остальные имеют ровно четверых знакомых), где n — общее количество учёных.

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

Пусть n — общее число учёных. Тогда:

• 5 вершин имеют степень 3. Сумма их степеней = 5 * 3 = 15.
• (n - 5) вершин имеют степень 4. Сумма их степеней = (n - 5) * 4 = 4n - 20.

Общая сумма степеней всех вершин равна: 15 + (4n - 20) = 4n - 5.

По лемме о рукопожатиях, эта сумма должна быть чётной:

4n - 5 = 2k (где k — некоторое целое число, равное количеству рёбер).

Левая часть уравнения (4n - 5) является нечётным числом (так как 4n — чётное, а вычитание 5 делает его нечётным). Правая часть уравнения (2k) — чётное число.

Нечётное число не может равняться чётному числу. Следовательно, такое условие задачи невозможно.

Вывод: Не могло оказаться так, что пятеро из них знакомы ровно с тремя другими, а все остальные имеют ровно четверых знакомых среди собравшихся.

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