{ "id": "utyum-2018_lichol_6_strategic_cities", "title": "Тотальное доминирование в связном графе, УТЮМ 2018", "kind": { "primary": "olympiad_problem", "secondary": [ "graph_in_statement", "application" ] }, "language": "ru", "authors": [ { "name": "?", "status": "needs_human_review" } ], "problem_profile": { "objects": [ "connected_graph", "spanning_tree", "total_dominating_set", "extremal_tree_construction" ], "methods": [ "extremal_construction", "delete_to_simplify" ], "transformations": [ "reduce_to_tree" ], "goal": [ "find_minimum_guaranteed_total_dominating_set_size" ], "auxiliary_graph_type": [], "invariants": [], "keywords": [ "utyum", "2018_lichol_6_strategic_cities", "utyum_2018", "total_domination", "two_thirds_bound" ], "status": "ai_checked" }, "statements": { "original": [ { "id": "stmt-original", "title": "Оригинальная формулировка", "text": "Некоторые из 2017 городов страны соединены прямыми двусторонними авиарейсами так, что из каждого города\nможно добраться до любого другого. Нужно выбрать k стратегически значимых городов так, чтобы из любого города,\nвключая стратегически значимые, ровно за один перелёт можно было попасть в стратегически значимый город.\n\nПри каком наименьшем k это наверняка можно сделать?", "source_id": "src-utyum-2018_lichol_6_strategic_cities-official", "status": "ai_checked", "self_contained": { "status": "ai_checked" }, "definition_ids": [ "connected_graph", "tree", "dominating_set" ] } ], "graph_theory": [ { "id": "stmt-graph", "title": "Тотальное доминирующее множество", "text": "Дан связный граф на 2017 вершинах. Нужно выбрать \\(k\\) вершин так, чтобы каждая вершина графа, включая выбранные вершины, была смежна хотя бы с одной выбранной вершиной. При каком наименьшем \\(k\\) это всегда возможно?", "status": "ai_checked", "self_contained": { "status": "ai_checked" }, "definition_ids": [ "connected_graph", "tree", "dominating_set" ], "distinct_from": [ "stmt-original" ] } ], "olympiad_reformulations": [] }, "ideas": [ { "id": "idea-total-domination-not-closed-domination", "title": "Стратегический город тоже должен иметь стратегического соседа", "text": "Фраза «ровно за один перелёт» означает не обычное доминирование, а полное доминирование: каждая вершина, даже выбранная, должна иметь выбранного соседа.", "tags": [ "goal_bound" ], "status": "ai_checked" }, { "id": "idea-tree-two-thirds-total-domination", "title": "В дереве достаточно выбрать не больше двух третей вершин", "text": "Для любого дерева на \\(n\\ge3\\) вершинах есть полное доминирующее множество размера не больше \\(\\lfloor2n/3\\rfloor\\). Связный граф можно сначала заменить его остовным деревом: если вершины доминируют дерево, они доминируют и исходный граф.", "tags": [ "trees", "induction" ], "status": "ai_checked" } ], "solutions": [ { "id": "sol-official", "title": "Решение", "text": "Ответ: \\(k=1344\\).\n\nСначала уточним перевод на язык графов. Города - вершины, авиарейсы - рёбра. Нужно выбрать множество \\(S\\) вершин так, чтобы у каждой вершины был сосед из \\(S\\). Важно, что выбранная вершина тоже должна иметь выбранного соседа: попасть в стратегический город надо ровно за один перелёт, а не за ноль перелётов.\n\nНижняя оценка. Построим связный граф на 2017 вершинах: возьмём центральную вершину \\(A\\) и для каждого \\(i=1,\\ldots,672\\) добавим путь \\(A-B_i-C_i-D_i\\). Всего вершин \\(1+3\\cdot672=2017\\). Рассмотрим любой подходящий набор \\(S\\). Вершина \\(D_i\\) имеет единственного соседа \\(C_i\\), значит обязательно \\(C_i\\in S\\). Но тогда сама вершина \\(C_i\\), будучи выбранной или нет, должна иметь выбранного соседа; её соседи - только \\(B_i\\) и \\(D_i\\), поэтому хотя бы одна из вершин \\(B_i,D_i\\) тоже должна лежать в \\(S\\). Значит для каждого \\(i\\) из тройки \\(B_i,C_i,D_i\\) выбраны как минимум две вершины. Таких троек 672, поэтому \\(|S|\\ge2\\cdot672=1344\\). Следовательно, меньшего \\(k\\) гарантировать нельзя.\n\nВерхняя оценка. Нам понадобится стандартная лемма: в каждом дереве на \\(n\\ge3\\) вершинах есть множество \\(S\\) размера не больше \\(\\lfloor2n/3\\rfloor\\), такое что у каждой вершины дерева есть сосед из \\(S\\). Лемма доказывается индукцией по \\(n\\): берут конец длиннейшего пути и срезают около него маленький висячий фрагмент. Если у предпоследней вершины есть хотя бы два листа, эти листы удаляют, а при восстановлении добавляют одну их общую соседнюю вершину; если же конец пути идёт цепочкой, удаляют три подряд идущие вершины у конца и при восстановлении добавляют две соседние вершины. В обоих случаях все удалённые вершины получают выбранного соседа, связь с оставшимся деревом контролируется граничной вершиной, а расход не превосходит две выбранные вершины на три удалённые. Базы \\(n=3,4\\) проверяются напрямую выбором двух соседних вершин. Поэтому после всех шагов получается не больше \\(\\lfloor2n/3\\rfloor\\) выбранных вершин.\n\nТеперь пусть дан произвольный связный граф \\(G\\) на 2017 вершинах. Возьмём в нём остовное дерево \\(T\\). По лемме в \\(T\\) есть множество \\(S\\) размера не больше\n\\[\n\\left\\lfloor {2\\cdot2017\\over3}\\right\\rfloor=1344.\n\\]\nУ каждой вершины есть сосед из \\(S\\) уже в дереве \\(T\\), а все рёбра дерева являются рёбрами исходного графа \\(G\\). Значит то же множество \\(S\\) подходит и для исходной сети авиарейсов. Нижняя и верхняя оценки совпали, поэтому минимальное гарантированное значение равно \\(1344\\).", "idea_ids": [ "idea-total-domination-not-closed-domination", "idea-tree-two-thirds-total-domination" ], "standard_idea_ids": [ "delete_to_simplify" ], "status": "ai_checked", "repair_status": "high_reasoning_repaired_2026_05_07", "review_notes": "Аудит высокого уровня 2026-05-07: исправлена интерпретация на полное доминирование, проверена экстремальная конструкция из 672 путей A-B-C-D и верхняя оценка через остовное дерево и лемму floor(2n/3).", "definition_ids": [ "connected_graph", "tree", "dominating_set" ] } ], "difficulty": { "main": "regional", "local_score": 6, "comment": "Импортировано из пакета УТЮМ; этап: личная олимпиада, 6 класс.", "status": "ai_checked" }, "tags": [ "trees", "connectivity", "goal_strategy_game" ], "sources": [ { "source_id": "src-utyum-2018_lichol_6_strategic_cities-official", "role": "problem_and_solutions_official", "status": "source_verified" } ], "editorial": { "created_by": "ai", "created_at": "2026-04-25", "review_status": "ai_checked", "public_ready": false, "notes": [ "Импортировано из карточки пакета УТЮМ 2018_lichol_6_strategic_cities.yaml.", "Роль графа: явно присутствует в условии.", "Уверенность: высокая.", "Задача прямо формулируется на графе городов и авиарейсов, а официальное решение строит экстремальный пример и затем сводит общий случай к дереву." ], "relations_status": "deep_done", "graph_theory_duplicate_removed": false, "solution_classification": { "type": "official_complete_or_near_complete", "label": "официальное полное/почти полное", "status": "ai_checked", "confidence": 0.9, "basis": "агентский аудит средней сложности", "notes": "Решение распознано как официальное или архивное; оснований понижать статус не найдено.", "audit_source": "agent-russian-archives.json" } } }