Регион 2022

Первое решение. Рассмотрим граф дружб, в котором вершины — это люди, а ребро соединяет двух людей, если они дружат. Пусть в компании человека. Построим граф: одну вершину соединим с тремя другими Остальные вершин разобьём на пары и соединим вершины в каждой паре. Всего получаем 52 ребра. При удалении любой вершины исчезает нечётное число рёбер, значит, остаётся также нечётное число. Таким образом, компания из человек подходит. Покажем, что компаний больше чем из 102 людей быть не может, для этого выберем из них любые 103, достаточно показать, что не существует уже такой компании.

Докажем, что компании из человек быть не может. Всего способов выбросить две вершины из равно

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

_________________________________________________________________________________________________________________________________________________________________________________

Второе решение. Рассмотрим граф дружб, в котором вершины — это люди, а ребро соединяет двух людей, если они дружат. Пусть в компании человека. Построим граф: одну вершину соединим с тремя другими Остальные вершин разобьём на пары и соединим вершины в каждой паре. Всего получаем 52 ребра. При удалении любой вершины исчезает нечётное число рёбер, значит, остаётся также нечётное число. Таким образом, компания из человек подходит. Покажем, что компаний больше чем из 102 людей быть не может, для этого выберем из них любые 103, достаточно показать, что не существует уже такой компании.

Докажем, что компании из человек быть не может. Назовём вершину чётной, если её степень чётна, и нечётной иначе.

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

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

что нечётно. Противоречие.