{ "id": "yumt-2025-grand-final-problem5", "title": "Наибольший гарантированный выигрыш на связном графе, ЮМТ 2025", "kind": { "primary": "olympiad_problem", "secondary": [ "graph_in_statement", "application" ] }, "language": "ru", "authors": [ { "name": "?", "status": "needs_human_review" } ], "problem_profile": { "objects": [ "rooted_connected_graph", "weighted_vertex_set", "simple_path", "rooted_spanning_tree" ], "methods": [ "spanning_tree_reduction", "double_counting_over_root_leaf_paths", "extremal_construction" ], "transformations": [ "connected_graph_to_rooted_spanning_tree" ], "goal": [ "determine_game_value", "sharp_lower_and_upper_bound" ], "auxiliary_graph_type": [ "rooted_tree" ], "invariants": [ "number_of_leaves", "root_leaf_path_lengths", "total_vertex_weight" ], "keywords": [ "yumt", "2025_grand_final_problem5", "yumt_2025" ], "status": "ai_checked" }, "statements": { "original": [ { "id": "stmt-original", "title": "Оригинальная формулировка", "text": "Дано натуральное n.\nАня рисует связный граф на n вершинах, в которых она расставляет неотрицательные вещественные числа с суммой 1.\nОдну из вершин Аня называет стартовой вершиной A.\nУвидев этот граф и числа, Боря выбирает в нём простой путь, возможно длины 0, выходящий из A.\nВыигрыш Бори — среднее арифметическое чисел, записанных в вершинах этого пути.\nКакой наибольший выигрыш может гарантировать Боря вне зависимости от действий Ани?", "source_id": "src-yumt-2025-grand-final-problem5-official", "status": "ai_checked", "self_contained": { "status": "ai_checked" }, "definition_ids": [ "connected_graph", "path" ] } ], "graph_theory": [], "olympiad_reformulations": [] }, "ideas": [ { "id": "idea-root-leaf-path-counting", "title": "Суммировать по путям от корня к листьям", "text": "Если M - наибольшее среднее на простом пути из стартовой вершины, то в любом остовном дереве сумма весов на каждом пути от корня к листу не превосходит M, умноженного на длину этого пути. Суммирование по листьям покрывает каждую вершину хотя бы один раз и дает нижнюю оценку на M через максимальную возможную сумму длин корень-лист.", "status": "ai_checked" }, { "id": "idea-broom-extremal-tree", "title": "Экстремальный пример - веник", "text": "Чтобы минимизировать выигрыш Бори, Аня берет путь-ручку из n-l нелистовых вершин и прикрепляет к его концу l листьев, а весь вес поровну кладет в листья. Тогда любой ненулевой выигрыш равен 1/[l(n-l+1)], и нужно выбрать l, максимизирующее l(n-l+1).", "status": "ai_checked" } ], "solutions": [ { "id": "sol-ai-root-leaf-counting", "title": "ИИ-решение: подсчет путей от корня к листьям", "text": "Ответ: 1/floor((n+1)^2/4).\n\nСначала докажем, что Боря всегда может получить не меньше этой величины. Рассмотрим произвольные граф, веса и стартовую вершину A, выбранные Аней, и возьмем в графе любое остовное дерево T с корнем A. Пусть M - максимальное среднее арифметическое на простом пути из A; достаточно оценивать только пути дерева, потому что они тоже являются простыми путями исходного графа.\n\nОбозначим листья корневого дерева T через L. Для листа x пусть \\(P_x\\) - путь от A до x, а \\(|P_x|\\) - число вершин в этом пути. По определению M для каждого листа x выполнено\n\\(\\sum_{v\\in P_x} a_v \\le M|P_x|\\),\nгде \\(a_v\\) - число в вершине v. Просуммируем эти неравенства по всем листьям. Левая часть равна сумме \\(a_v\\), где каждая вершина v посчитана столько раз, сколько листьев лежит в ее поддереве; это число хотя бы 1. Поэтому левая часть не меньше \\(\\sum_v a_v=1\\). Значит\n\\(1 \\le M\\sum_{x\\in L}|P_x|\\). (1)\n\nПусть в T ровно l листьев. На любом пути от корня к листу все вершины, кроме последнего листа, являются нелистовыми вершинами дерева. Нелистовых вершин всего n-l, поэтому \\(|P_x|\\) <= n-l+1 для каждого листа x. Следовательно,\n\\(\\sum_{x\\in L}|P_x| \\le l(n-l+1) \\le \\lfloor (n+1)^2/4 \\rfloor\\).\nИз (1) получаем M >= 1/floor((n+1)^2/4). Значит такой выигрыш Боря гарантирует всегда.\n\nОсталось показать, что большего гарантировать нельзя. При n=1 Аня вынуждена поставить число 1 в единственной вершине, и ответ равен 1. Пусть n>=2. Выберем целое l, на котором достигается максимум l(n-l+1), то есть l(n-l+1)=floor((n+1)^2/4). Аня строит дерево-\"веник\": путь из n-l нелистовых вершин, начинающийся в A, и l листьев, прикрепленных к последней вершине этого пути. Во все нелистовые вершины она записывает 0, а в каждый лист - 1/l.\n\nЛюбой простой путь из A в этом дереве либо заканчивается до листьев и имеет среднее 0, либо доходит до одного листа. Во втором случае путь содержит n-l+1 вершин и ровно один положительный вес 1/l, поэтому его среднее равно\n(1/l)/(n-l+1)=1/[l(n-l+1)]=1/floor((n+1)^2/4).\nЗначит Аня может не позволить Боре получить больше этой величины. Нижняя и верхняя оценки совпадают.", "idea_ids": [ "idea-root-leaf-path-counting", "idea-broom-extremal-tree" ], "standard_idea_ids": [], "status": "ai_checked", "definition_ids": [ "path", "tree" ] } ], "difficulty": { "main": "regional", "local_score": 6, "comment": "Импортировано из проверенной архивной карточки ЮМТ 2025_grand_final_problem5.md; этап: Гранд-лига, финал.", "status": "ai_checked" }, "tags": [ "connectivity", "goal_strategy_game" ], "sources": [ { "source_id": "src-yumt-2025-grand-final-problem5-official", "role": "problem_and_solutions_official", "status": "source_verified" } ], "editorial": { "created_by": "ai", "created_at": "2026-04-25", "review_status": "ai_checked", "public_ready": true, "notes": [ "2026-05-05: добавлено ИИ-решение; открытый поиск не выявил готового решения или автора, доказательство использует только элементарный подсчет путей от корня к листьям.", "Импортировано из проверенной рабочей карточки ЮМТ 2025_grand_final_problem5.md." ], "relations_status": "deep_done", "graph_theory_duplicate_removed": true, "solution_classification": { "type": "official_complete_or_near_complete", "label": "официальное полное/почти полное", "status": "ai_checked", "confidence": 0.78, "basis": "агентский аудит средней сложности", "notes": "Метаданные источника указывают на архивное или официальное решение; решение проверено.", "audit_source": "agent-russian-archives.json" } } }