{ "id": "tc-2018-19-complex-state-cycle-game", "title": "Сложное государство: выигрыш Васи, Турнир городов 2018/19", "kind": { "primary": "olympiad_problem", "secondary": [ "application" ] }, "language": "ru", "authors": [ { "name": "Дидин М. А.", "status": "source_verified" } ], "problem_profile": { "objects": [ "connected_graph", "cycle", "orientation_game" ], "methods": [ "induction", "strategy_argument", "delete_to_simplify", "cycle_strategy" ], "transformations": [ "reduce_graph_with_cycle", "delete_farthest_vertex_from_cycle" ], "goal": [ "prove_winning_strategy" ], "auxiliary_graph_type": [], "invariants": [ "connectedness", "cycle_presence", "edge_orientation" ], "keywords": [ "orientation_game", "cycle_state", "vasya_winning" ], "status": "ai_checked" }, "statements": { "original": [ { "id": "stmt-original", "title": "Игра в сложном государстве", "text": "В виртуальном компьютерном государстве не менее двух городов. Некоторые пары городов соединены дорогой, причём из каждого города можно добраться по дорогам до любого другого. Государство называется сложным, если можно, начав движение из какого-то города и не проходя дважды по одной и той же дороге, вернуться в этот город. Петя и Вася играют так: сначала Петя задаёт направление на каждой дороге и помещает туриста в один из городов; затем за ход Петя перемещает туриста по дороге в разрешённом направлении в соседний город, а Вася меняет направление одной дороги, входящей или выходящей из нового города туриста. Вася выигрывает, если Петя в какой-то момент не сможет сделать ход. Докажите, что в сложном государстве Вася может гарантировать победу, как бы ни играл Петя.", "source_id": "src-problems-66727", "status": "ai_checked", "self_contained": { "status": "ai_checked" }, "definition_ids": [ "connected_graph", "directed_graph", "cycle" ] } ], "graph_theory": [ { "id": "stmt-graph", "text": "Дан связный неориентированный граф, содержащий цикл. Петя сначала ориентирует все рёбра графа и выбирает начальную вершину фишки. На каждом своём ходе Петя обязан передвинуть фишку по исходящему ребру в соседнюю вершину, после чего Вася разворачивает одно ребро, инцидентное новой вершине фишки. Если перед ходом Пети из текущей вершины нет исходящих рёбер, Вася выигрывает. Докажите, что Вася имеет стратегию, которая при любой начальной ориентации, начальной вершине и дальнейших ходах Пети приводит к победе за конечное число ходов.", "status": "ai_checked", "self_contained": { "status": "ai_checked" }, "definition_ids": [ "connected_graph", "directed_graph", "cycle" ], "title": "Сложное государство: выигрыш Васи, Турнир городов 2018/19", "source_ids": [ "src-lktg-2026-project2-problems-ru" ] } ], "olympiad_reformulations": [] }, "ideas": [ { "id": "idea-cycle-forces-one-direction", "title": "Цикл заставляет идти вперёд", "text": "На простом цикле Вася после каждого хода Пети разворачивает ребро перед туристом. Если это не запирает туриста сразу, то турист вынужден двигаться в одну сторону по циклу и при возвращении к стартовой вершине оказывается без хода.", "tags": [ "connectivity", "goal_strategy_game" ], "status": "ai_checked" }, { "id": "idea-delete-outer-vertex", "title": "Удаление вершины вне минимального цикла", "text": "В общем графе с циклом можно удалить вершину максимального расстояния от минимального цикла: оставшийся граф связен и всё ещё содержит цикл. Стратегия в меньшем графе либо выигрывает сразу, либо вынуждает Петю всё реже входить в удалённую вершину.", "tags": [ "induction", "connectivity" ], "status": "ai_checked" } ], "solutions": [ { "id": "sol-vasya-cycle-induction", "title": "Индукция от цикла", "text": "Докажем индукцией по числу вершин более сильное утверждение: если связный граф содержит цикл, то из любой ориентации и любого положения фишки в момент, когда Васе предстоит развернуть ребро, Вася за конечное время оставит фишку без исходящих рёбер.\n\nБаза: граф является простым циклом. Если сейчас из вершины фишки выходит ровно одно ребро, Вася разворачивает его внутрь и сразу запирает фишку. Если исходящих рёбер ноль или два, Вася одним разворотом оставляет ровно одно исходящее ребро; Петя вынужден пройти по нему. Обозначим этот ход \\(A_1\\to A_2\\) и выберем соответствующее направление обхода цикла. Теперь Вася смотрит на следующее ребро \\(A_2A_3\\). Если оно выходит из \\(A_2\\), Вася разворачивает его внутрь, и оба ребра при \\(A_2\\) становятся входящими. Если оно входит в \\(A_2\\), Вася разворачивает его наружу, и Петя вынужден перейти в \\(A_3\\). Вася повторяет правило. Либо фишка остановится раньше, либо обойдёт весь цикл; тогда при возвращении в \\(A_1\\) Вася разворачивает исходное ребро \\(A_1A_2\\) внутрь и останавливает фишку.\n\nИндукционный переход. Выберем цикл наименьшей длины \\(C\\). У него нет хорды, иначе хорда разделила бы его на два цикла, один из которых короче. Если граф не равен \\(C\\), выберем среди вершин вне \\(C\\) вершину \\(x\\), находящуюся на наибольшем расстоянии от \\(C\\). Граф \\(G-x\\) связен и всё ещё содержит \\(C\\). Действительно, для любой \\(y\\ne x\\) кратчайший путь от \\(y\\) к \\(C\\) не проходит через \\(x\\), иначе расстояние от \\(y\\) до \\(C\\) было бы больше расстояния от \\(x\\), вопреки максимальности выбора \\(x\\).\n\nВнутри \\(G-x\\) Вася применяет индукционную стратегию и не трогает рёбра, инцидентные \\(x\\). Если Петя проходит по стрелке \\(u\\to x\\), Вася немедленно разворачивает именно её в \\(x\\to u\\). На следующем ходу Петя обязательно выходит из \\(x\\) обратно в \\(G-x\\), после чего Вася заново запускает индукционную стратегию из нового состояния. Каждый уход в \\(x\\) навсегда уменьшает число стрелок, направленных из \\(G-x\\) в \\(x\\): одна такая стрелка разворачивается наружу, а в остальное время граничные рёбра не меняются. Поэтому уйти в \\(x\\) можно лишь конечное число раз. После последнего ухода индукционная стратегия за конечное время останавливает фишку в \\(G-x\\).\n\nЕсли в исходном рассматриваемом состоянии фишка находилась в \\(x\\), Вася сначала делает обязательный разворот. Если из \\(x\\) выходит ровно одна стрелка, он разворачивает её и сразу выигрывает. Иначе он разворачивает любое инцидентное \\(x\\) ребро так, чтобы исходящая стрелка существовала; первый ход Пети выводит фишку в \\(G-x\\), после чего применяется описанная стратегия. Индукция завершена.", "idea_ids": [ "idea-cycle-forces-one-direction", "idea-delete-outer-vertex" ], "standard_idea_ids": [ "induction", "delete_to_simplify" ], "status": "ai_checked", "definition_ids": [ "connected_graph", "path", "cycle" ], "source_ids": [ "src-lktg-2026-project2-solutions-ru" ] } ], "difficulty": { "main": "national_final_hard", "local_score": 7, "comment": "Осенний сложный тур 2018/19, 8-9 класс, задача 7b на 7 баллов.", "status": "ai_checked" }, "tags": [ "connectivity", "induction", "goal_strategy_game" ], "properties": { "central_method": { "value": [ "induction", "delete_to_simplify" ], "status": "ai_checked" } }, "sources": [ { "source_id": "src-problems-66727", "role": "problem_and_solution_archive", "status": "source_verified" }, { "source_id": "src-lktg-2026-project2-page", "role": "project_page", "status": "source_verified", "title": "Официальная страница проекта ЛКТГ 2026" }, { "source_id": "src-lktg-2026-project2-problems-ru", "role": "official_problem_statement", "status": "source_verified", "title": "Официальные условия, задача 5", "statement_ids": [ "stmt-graph" ], "note": "PDF указывает источник как Турнир городов 2018/19 и объединяет в одной задаче два результата: дерево и граф с циклом. Номера исходных задач и авторы в PDF не названы." }, { "source_id": "src-lktg-2026-project2-solutions-ru", "role": "official_complete_solution", "status": "source_verified", "title": "Официальные решения, задача 5" } ], "editorial": { "created_by": "ai", "created_at": "2026-04-27", "review_status": "ai_checked", "public_ready": true, "notes": [ "Выделено из исходной составной карточки игры с состояниями.", "2026-08-15: задача 5 проекта ЛКТГ является перепечаткой этого случая; её официальный источник и полное решение присоединены к канонической карточке." ], "relations_status": "deep_done", "solution_classification": { "type": "official_complete_or_near_complete", "label": "официальное полное решение", "status": "ai_checked", "confidence": 0.97, "basis": "Полное доказательство сверено с официальным PDF решений проекта ЛКТГ 2026.", "notes": "Прежний архивный источник сохранён как дополнительный источник той же задачи." } } }