{ "id": "spbmo-2010-10-p4-cubic-edge-company-game", "title": "Игра на рёбрах кубического графа и три компании, СПбМО 2010, 10 класс, задача 4", "kind": { "primary": "olympiad_problem", "secondary": [ "graph_in_statement" ] }, "language": "ru", "authors": [ { "name": "Карпов Д.В.", "status": "source_verified", "source_id": "src-spbmo-2010-city-911-tex", "notes": "В официальном TeX после задачи стоит макрос dvk = signed(Д. Карпов)." } ], "problem_profile": { "objects": [ "simple_graph", "degree", "edge_coloring_game" ], "methods": [ "threat_strategy", "fork_strategy", "recursive_descent", "strategy_game", "graph_modeling" ], "transformations": [ "roads_to_cubic_graph", "companies_to_edge_colors" ], "goal": [ "determine_winning_player" ], "auxiliary_graph_type": [ "cubic_graph" ], "invariants": [ "local_two_color_threat", "double_threat_fork", "fresh_cubic_component_contains_cycle", "degree_three" ], "keywords": [ "spbmo_2010_10_p4", "cubic_graph", "edge_coloring_game", "rainbow_vertex", "spbmo" ], "status": "ai_checked" }, "statements": { "original": [ { "id": "stmt-original", "title": "Условие", "text": "В стране 2010 городов, из каждого из которых выходит ровно по три дороги, ведущие в другие города. Президент и премьер-министр играют в следующую игру: они по очереди продают дороги трём частным компаниям; изначально все дороги государственные, каждый своим ходом продаёт ровно одну дорогу. Первым ходит премьер. Президент хочет добиться того, чтобы хотя бы для одного города все три выходящие из него дороги оказались проданы разным компаниям, а премьер хочет этого избежать. Проигравший уходит в отставку. Кто из двух политиков сможет сохранить свой пост при правильной игре?", "source_id": "src-spbmo-2010-city-911-tex", "status": "ai_checked", "self_contained": { "status": "ai_checked" }, "definition_ids": [ "simple_graph", "degree" ], "review_notes": "Сверено с c_911_10.tex из официального архива СПбМО 2010 для городского тура 9-11 классов, строки задачи 10 класса, пункт 4." } ], "graph_theory": [ { "id": "stmt-graph", "title": "Игра раскраски рёбер кубического графа", "text": "Дан 3-регулярный граф на 2010 вершинах. Два игрока по очереди окрашивают по одному ещё не окрашенному ребру в один из трёх цветов; первый ходит игрок, который хочет избежать радужной вершины. Второй игрок выигрывает, если в некоторый момент найдётся вершина, у которой три инцидентных ребра имеют три попарно различных цвета. Первый игрок выигрывает, если все рёбра окрашены и такой вершины не появилось. Определите, кто имеет выигрышную стратегию.", "status": "ai_checked", "self_contained": { "status": "ai_checked" }, "definition_ids": [ "simple_graph", "degree", "bridge", "cycle", "path", "tree" ], "distinct_from": [ "stmt-original" ], "review_notes": "Города соответствуют вершинам, дороги — рёбрам, три компании — трём цветам рёбер; условие 'из каждого города выходит ровно по три дороги' даёт 3-регулярность." } ], "olympiad_reformulations": [] }, "ideas": [ { "id": "idea-local-threat", "title": "Опасная вершина с двумя разными цветами", "text": "Если у вершины степени 3 уже окрашены два инцидентных ребра в разные цвета, а третье ещё свободно, то на своём следующем ходе президент немедленно выигрывает, окрашивая третье ребро в оставшийся цвет. Поэтому премьер обязан гасить каждую такую угрозу сразу.", "tags": [ "coloring", "goal_strategy_game", "graph_model" ], "status": "ai_checked" }, { "id": "idea-double-threat-path", "title": "Путь между двумя окрашенными входами даёт вилку", "text": "Если две вершины соединены ещё неокрашенным путём, а в каждую из них уже входит по одному окрашенному ребру извне, президент может идти по этому пути, каждый раз создавая единственную локальную угрозу. На последнем ребре он выбирает цвет, отличный от цвета предыдущего ребра пути и от цвета второго входа; тогда опасными становятся сразу обе концевые вершины, и премьер может закрыть только одну угрозу.", "tags": [ "goal_strategy_game", "extremal_choice", "graph_model" ], "status": "ai_checked" }, { "id": "idea-descend-to-cycle", "title": "Спуск по свежей компоненте не может продолжаться бесконечно", "text": "После закрытия опасной вершины можно смотреть на свежую компоненту за одним из только что окрашенных рёбер. Если два передних соседа текущей вершины уже соединены внутри этой компоненты, применяется вилка по пути. Если нет, каждая отделившаяся свежая компонента имеет ровно одну вершину с внутренней степенью 2, остальные степени 3, а значит содержит цикл; президент переходит в меньшую такую компоненту. В конечном графе этот спуск обязан остановиться.", "tags": [ "goal_strategy_game", "minimal_counterexample", "degree_counting" ], "status": "ai_checked" } ], "solutions": [ { "id": "sol-double-threat-and-recursive-descent", "title": "Две угрозы на конце пути и спуск в свежую компоненту", "text": "Ответ: президент сохраняет свой пост.\n\nБудем говорить, что вершина опасна, если у неё уже окрашены два инцидентных ребра в два разных цвета, а третье инцидентное ребро ещё не окрашено. Если после хода премьера есть опасная вершина, президент сразу выигрывает: он окрашивает третье ребро этой вершины в оставшийся третий цвет. Поэтому, когда президент своим ходом создаёт опасную вершину, премьер обязан следующим ходом окрашивать именно её третье ребро и обязан красить его в один из двух уже имеющихся у этой вершины цветов.\n\nСначала опишем вспомогательную вилку. Пусть есть неокрашенный путь\n\\[\np_0p_1\\ldots p_k\n\\]\nв такой части графа, где никакие другие рёбра, инцидентные вершинам пути, ещё не окрашены, кроме двух внешних рёбер, входящих в \\(p_0\\) и \\(p_k\\). Президент ходит. Если \\(k=1\\), он красит ребро \\(p_0p_1\\) в цвет, отличный от цветов обоих внешних рёбер, если эти цвета различны, и в любой другой цвет, если они совпадают. Тогда сразу обе вершины \\(p_0,p_1\\) становятся опасными, а премьер может закрыть только одну из двух угроз; следующим ходом президент выигрывает.\n\nЕсли \\(k>1\\), президент красит \\(p_0p_1\\) в цвет, отличный от цвета внешнего ребра при \\(p_0\\). Вершина \\(p_0\\) становится опасной, и премьер вынужден окрасить её третье ребро, не лежащее на пути. Затем президент красит \\(p_1p_2\\) в цвет, отличный от цвета \\(p_0p_1\\); премьер вынужден закрывать угрозу при \\(p_1\\). Так президент последовательно проходит путь. На последнем шаге он красит ребро \\(p_{k-1}p_k\\) в цвет, отличный одновременно от цвета \\(p_{k-2}p_{k-1}\\) и от цвета внешнего ребра при \\(p_k\\); среди трёх цветов такой выбор всегда есть. Тогда опасными становятся обе вершины \\(p_{k-1}\\) и \\(p_k\\). Премьер одним ходом может закрыть только одну из этих угроз, поэтому президент выигрывает следующим ходом. Значит, как только президент получает две уже окрашенные внешние дороги к концам свежего неокрашенного пути, он может форсировать победу.\n\nРассмотрим первый ход премьера: он красит ребро \\(uv\\) в цвет \\(a\\). Если \\(uv\\) лежит на цикле, возьмём путь \\(u=p_0,p_1,\n\\ldots,p_k=v\\), который получается из этого цикла удалением ребра \\(uv\\). Президент красит \\(p_0p_1\\) в цвет, отличный от \\(a\\). Вершина \\(u\\) стала опасной, поэтому премьер вынужден окрасить третье ребро из \\(u\\). После этого у свежего пути \\(p_1p_2\\ldots p_k\\) есть два окрашенных внешних ребра: \\(p_0p_1\\) при \\(p_1\\) и \\(uv\\) при \\(p_k=v\\). Все остальные рёбра, инцидентные вершинам этого пути и не лежащие на нём, ещё не окрашены. Президент применяет вилку и выигрывает.\n\nОстаётся случай, когда первый ход премьера пришёлся на мост \\(uv\\). Удалим этот мост и посмотрим на компоненту \\(H\\), содержащую \\(u\\). В графе \\(H\\) вершина \\(u\\) имеет степень 2, а все остальные вершины имеют степень 3. Такая конечная компонента не может быть деревом: если в ней \\(m\\) вершин, сумма внутренних степеней равна \\(3m-1\\), значит число внутренних рёбер равно \\((3m-1)/2>m-1\\). Следовательно, в \\(H\\) есть цикл.\n\nТеперь президент спускается внутри \\(H\\). Текущая вершина \\(x\\) имеет одно уже окрашенное внешнее ребро цвета \\(c\\) к обработанной части, а два остальных ребра ведут в свежую компоненту \\(H\\) и ещё не окрашены; сначала это \\(x=u\\), \\(c=a\\). Президент красит одно из двух свежих рёбер из \\(x\\) в цвет, отличный от \\(c\\). Вершина \\(x\\) становится опасной, и премьер вынужден окрасить второе свежее ребро из \\(x\\). Если два новых конца соединены путём в \\(H-x\\), президент берёт кратчайший такой путь; его внутренние вершины не имеют окрашенных инцидентных рёбер, и президент выигрывает по вилке.\n\nЕсли эти два конца лежат в разных компонентах графа \\(H-x\\), президент выбирает одну из этих компонент и делает её новой свежей компонентой. Она снова имеет ровно одну вершину внутренней степени 2, а все остальные её вершины имеют внутреннюю степень 3, поэтому по тому же подсчёту содержит цикл. Кроме того, она строго меньше прежней свежей компоненты. Значит, такой спуск не может продолжаться бесконечно. На некотором шаге два передних конца окажутся соединены свежим путём, после чего президент применит вилку двух одновременных угроз.\n\nТаким образом, при любой игре премьера президент форсирует появление вершины, у которой три дороги проданы трём разным компаниям. Значит, премьер уходит в отставку, а президент сохраняет пост.", "idea_ids": [ "idea-local-threat", "idea-double-threat-path", "idea-descend-to-cycle" ], "standard_idea_ids": [ "invariant" ], "status": "ai_checked", "definition_ids": [ "simple_graph", "degree", "bridge", "cycle", "path", "tree" ] } ], "difficulty": { "main": "regional", "local_score": 6, "comment": "Городской тур СПбМО 2010, 10 класс, задача 4; условие и автор сверены с официальным TeX. Решение использует локальные угрозы, вилку двух опасных вершин и спуск по свежим компонентам кубического графа.", "status": "ai_checked" }, "tags": [ "coloring", "goal_strategy_game", "graph_model", "invariant", "minimal_counterexample" ], "properties": { "central_method": { "value": [ "local_threat", "double_threat_fork", "recursive_descent_in_fresh_cubic_component" ], "status": "ai_checked" }, "typical_olympiad_use": { "value": "Игра на частичной раскраске рёбер: локальная угроза в вершине степени 3 вынуждает немедленный ответ, а две разнесённые угрозы дают выигрышную вилку.", "status": "ai_checked" } }, "sources": [ { "source_id": "src-spbmo-2010-city-911-tex", "role": "official_problem_statement", "status": "source_verified", "statement_ids": [ "stmt-original", "stmt-graph" ] } ], "editorial": { "created_by": "ai", "created_at": "2026-05-03", "review_status": "ai_checked", "public_ready": true, "notes": [ "Официальный источник: c_911_10.tex из архива 91110tex.zip, задача 10 класса, пункт 4; авторская метка dvk.", "Графовая роль проверена: это игра раскраски рёбер 3-регулярного графа в три цвета с целью получить радужную вершину.", "2026-05-06: точный веб-поиск нашёл официальную/зеркальную публикацию условия, но не нашёл официального полного решения. Найдена также неофициальная листовка AESC 'Питерские графы, которые Глеб ещё не решил' с похожей, но искажённой целью 'дороги одной компании'; она не использована как источник условия.", "2026-05-06: кандидатное паритетное завершение заменено самодостаточной стратегией через вилку двух угроз и конечный спуск по свежим компонентам; малая компьютерная проверка на \\(K_4\\), \\(K_{3,3}\\), треугольной призме и кубе согласуется с ответом.", "2026-05-06: глубокий поиск связей выполнен; добавлен weak/same_motif relation к локальной fork-strategy лемме, сильных paired_variant или solution_transfer связей не найдено." ], "relations_status": "deep_done", "solution_classification": { "type": "ai_original", "label": "ИИ-решение с нуля", "status": "ai_checked", "confidence": 0.82, "basis": "реконструкция агентом высокой сложности после поиска официального решения", "notes": "Официальное решение не найдено; текущий текст является самостоятельной реконструкцией с закрытым финальным шагом.", "audit_source": "official-plan-expansion-spbmo-2010-10-p4-2026-05-06" } } }