Задача: В компании 100 детей, некоторые дети дружат (дружба всегда взаимна). Известно, что при выделении любого ребёнка оставшихся 99 детей можно разбить на 33 группы по три человека так, чтобы в каждой группе все трое попарно дружили. Найдите наименьшее возможное количество пар дружащих детей.
Решение: Переведём задачу на язык графов, сопоставляя ребёнку вершину, а дружбе — ребро. Тогда нам известно, что в данном графе на 100 вершинах при удалении любой вершины оставшиеся можно разбить на 33 тройки так, что в каждой тройке вершины попарно соединены. Требуется же найти минимальное возможное число рёбер в таком графе.
Для начала построим пример ровно с 198 рёбрами. Разобьём 99 вершин, кроме вершины A, на 33 группы по 3 вершины. Соединим попарно вершины в каждой тройке; наконец, соединим A со всеми другими вершинами. Тогда условия задачи выполнены: при удалении A разбиение на тройки уже приведено, а при удалении любой другой вершины B в этом же разбиении достаточно заменить B на A. При этом в описанном графе всего 33 * 3 + 99 = 198 рёбер.
Осталось доказать, что это количество — наименьшее. Назовём граф на 3k + 1 вершинах хорошим, если при удалении любой вершины остальные 3k вершин разбиваются на k троек попарно соединённых. Докажем индукцией по k, что в хорошем графе на 3k + 1 вершинах хотя бы 6k рёбер; при k = 33 получим требуемую оценку. База при k = 1 несложна: так как при удалении любой вершины три остальных попарно соединены, любые две вершины должны быть соединены, то есть число рёбер равно C²₄ = 6.
Докажем переход индукции. Если из каждой вершины выходит хотя бы по 4 ребра, общее количество рёбер не меньше, чем (3k + 1)·4/2 = 2(3k + 1), что даже больше, чем требуемое 6k. В противном случае найдётся вершина A, соединённая не более, чем с тремя другими. Если удалить любую вершину, кроме A, то A попадёт в какую-то тройку, а значит, она соединена хотя бы с двумя вершинами. Если удалить одну из этих вершин, у A останется не менее двух смежных, то есть было их не меньше трёх. Итак, A соединена ровно с тремя вершинами B, C и D. Тогда при удалении, скажем, B вершины A, C и D образуют тройку, то есть C и D соединены; аналогично получаем, что B, C и D попарно соединены.
Выбросим теперь из нашего графа вершины A, B, C и D, взамен добавив одну вершину X, соединённую со всеми, с кем была соединена хотя бы одна из вершин B, C и D. Заметим, что при этом количество рёбер уменьшилось хотя бы на 6 (т. е. на количество рёбер между A, B, C и D). Покажем, что полученный новый граф хороший; отсюда будет следовать переход индукции, ибо тогда в новом графе будет не менее 6(k – 1) рёбер, а значит, в исходном — не менее 6(k – 1) + 6 = 6k рёбер.
Пусть из нового графа удалена некоторая вершина Y ≠ X. Если её удалить из исходного графа, остальные вершины разобьются на тройки; пусть при этом вершина A окажется, для определённости, в тройке с B и C, а вершина D — в другой тройке. Тогда можно разбить новый граф так же, поместив вершину X в ту тройку, где была вершина D. Наконец, если удалить из нового графа вершину X, можно проделать ту же операцию, считая, что из исходного графа удалена вершина D (тогда A, B и C автоматически окажутся в одной тройке). Таким образом, переход индукции доказан.
Ответ: 198