Решение задачи 515

Условие:
Профессор Выбегалло написал 1001 статью. В каждой статье он может поставить ссылки на другие статьи, но никакие две статьи не должны ссылаться друг на друга. Выбегалло получит значимость k, если после этого у него будет k статей, на каждую из которых ссылаются хотя бы k статей. Какой наибольшей значимости он может добиться?

Решение:

Оценка. Пусть есть k статей, на каждую из которых ссылаются хотя бы k статей. Обозначим это множество через A. Тогда суммарное число ссылок, ведущих в А, не меньше k². Посчитаем потенциальное максимальное число ссылок, ведущих в А. Число ссылок из в А максимум k(k−1)/2 ссылок, так как в полном графе на k вершинах k(k−1)/2 ребер, в нашем случае ребро порождает максимум одну ссылку. Еще есть ссылки из не А в А. Их максимум (1001−k)k. Максимальное число ссылок, ведущих в А, должно быть не меньше k²: (1001−k)k + k(k−1)/2 ≥  k². Отсюда легко находим, что k≤667.

Пример. Расположим 667 статей по кругу, из каждой поставим ссылки на следующие 333 статьи. Тогда каждую статью ссылаются 333 статьи. Из всех оставшихся 334 статей поставим ссылки во все 667 статьи, стоящие в кругу. Тогда есть 667 статей, на каждую из которых ссылаются 667 других.

Ответ: 667.

Источник: устный турнир городов, 2014.