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

Предыдущий
вопрос Следующий
вопрос

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

Обозначим количество рёбер в графе знакомств как S. Тогда сумма степеней всех вершин (в графе неориентированный граф) равна 2S. Поскольку каждый степень каждой вершины не превосходит 2, сумма степеней всех вершин не превосходит 2n (где n - количество вершин). Таким образом, 2S ≤ 2n и S ≤ n.

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

С учётом того, что степень всех вершин этого графа не меньше 3, сумма степеней вершин равна как минимум 3n. Но также S ≤ n. Поэтому 3n ≤ 2S, откуда следует, что 3n ≤ 2n, что невозможно при любом натуральном n. Значит, предположение о том, что нет первокурсника, который знаком со всеми, неверно. Такой первокурсник обязан существовать.