Регион 2018

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

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

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

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

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

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