Дружба и графы ("Квант")

[Ktina]

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

[Dave]

Ответ: обязательно.
Возьмём студента $B$ (от backslapper), у которого больше всего друзей, $n$. Рассмотрим множество этих друзей, $F$. Так как все люди из этого множества дружат с $B$, то числа друзей у них всех различны (попарно различны, чтобы никто не придрался). С другой стороны, все эти числа больше $0$ (опять же, потому, что все они дружат с $B$) и не больше $n$ (исходя из выбора $B$). Значит эти числа - $1,2,\ldots,n$ в некотором порядке, в частности, в $F$ найдётся человек, имеющий только одного друга ($B$), что и требовалось доказать.
Как видим, справедливо даже более сильное утверждение - при соблюдении условий задачи множество "чисел друзей" - всегда непрерывное, если можно так выразиться, множество, т.е. заполняет весь промежуток от $1$ до своего максимума.

[Dave]

Интересна такая задача:

Для каждого натурального $n$
1) Доказать, что существует (не в реальности, конечно, а чисто гипотетически) группа студентов, удовлетворяющая условию задачи и в которой максимальное количество друзей у одного студента равно в точности $n$.
2) Найти минимальный размер такой группы.

[Naf2000]

Dave в сообщении #587306 писал(а):

Интересна такая задача:
1) Доказать, что существует (не в реальности, конечно, а чисто гипотетически) группа студентов, удовлетворяющая условию задачи и в которой максимальное количество друзей у одного студента равно в точности $n$.

По индукции.
Для $N=0$ это просто вершина
Для $N=1$ это граф из двух соединенных вершин
Пусть есть подобные графы для $0..(N-1)$. Рассмотрим граф состоящий из $N+1$ вершины, одна из вершин (и только она) соединена ребрами со всеми остальными. Пронумеруем эти остальные от 1 до $N$. К вершине с номером $k$ "приклеим" подграф из предположения индукции для $k-1$, отождествив эту вершину с "максимальной" вершиной приклеиваемого подграфа.

В результат для $N$ с условием задачи, это будет дерево с $2^N$ вершинами. Мне кажется это и будет минимальный граф, но доказательства пункта 2 у меня нет.

[Dave]

Naf2000 в сообщении #587499 писал(а):

В результат для $N$ с условием задачи, это будет дерево с $2^N$ вершинами. Мне кажется это и будет минимальный граф, но доказательства пункта 2 у меня нет.

Нет, можно и меньше.

[muzeum]

Ответ: наименьшая компания с максиммумом n состоит из 2n членов
Разумеется, отношение дружбы считаем антирефлексивным