{ "id": "tc-2018-19-simple-state-tree-game", "title": "Простое государство: Петя не проигрывает, Турнир городов 2018/19", "kind": { "primary": "olympiad_problem", "secondary": [ "application" ] }, "language": "ru", "authors": [ { "name": "Дидин М. А.", "status": "source_verified" } ], "problem_profile": { "objects": [ "connected_graph", "tree", "orientation_game" ], "methods": [ "invariant", "strategy_argument", "tree_paths" ], "transformations": [ "orient_edges_to_target" ], "goal": [ "prove_nonlosing_strategy" ], "auxiliary_graph_type": [], "invariants": [ "acyclicity", "unique_path", "edge_orientation_to_token" ], "keywords": [ "orientation_game", "tree_state", "petya_nonlosing" ], "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", "path", "tree" ] } ], "graph_theory": [ { "id": "stmt-graph", "text": "Дано дерево с не менее чем двумя вершинами. Петя сначала ориентирует все рёбра дерева и выбирает начальную вершину фишки. На каждом своём ходе Петя обязан передвинуть фишку по исходящему ребру в соседнюю вершину, после чего Вася разворачивает одно ребро, инцидентное новой вершине фишки. Если перед ходом Пети из текущей вершины нет исходящих рёбер, Вася выигрывает. Докажите, что Петя может выбрать начальную ориентацию, начальную вершину и дальнейшие ходы так, чтобы ходить бесконечно долго при любых ответах Васи.", "status": "ai_checked", "self_contained": { "status": "ai_checked" }, "definition_ids": [ "directed_graph", "tree" ], "title": "Простое государство: Петя не проигрывает, Турнир городов 2018/19", "source_ids": [ "src-lktg-2026-project2-problems-ru" ] } ], "olympiad_reformulations": [] }, "ideas": [ { "id": "idea-tree-token-sink", "title": "Все пути ведут к туристу", "text": "В дереве можно выбрать целевую вершину и ориентировать каждое ребро по единственному пути к ней. После первого хода турист оказывается в этой вершине; затем каждый разворот Васи даёт Пете единственное исходящее ребро, а проход по нему снова делает текущую вершину общей целью всех ориентированных путей.", "tags": [ "trees" ], "status": "ai_checked" } ], "solutions": [ { "id": "sol-petya-tree-invariant", "title": "Ориентация к движущемуся корню", "text": "Выберем вершину \\(r\\), её соседа \\(s\\), направим все рёбра дерева к \\(r\\) и поставим фишку в \\(s\\). Первым ходом Петя идёт \\(s\\to r\\). После этого перед каждым разворотом Васи все рёбра дерева направлены к вершине \\(v\\), в которой стоит фишка. Вася разворачивает одно инцидентное ребро \\(vu\\), и оно становится единственным исходящим ребром из \\(v\\). Петя идёт по нему в \\(u\\). Теперь все рёбра направлены к \\(u\\): в дереве путь к новому корню отличается от пути к старому корню только направлением ребра \\(uv\\). Инвариант восстановлен, поэтому Петя может ходить бесконечно.", "idea_ids": [ "idea-tree-token-sink" ], "status": "ai_checked", "definition_ids": [ "path", "tree" ], "standard_idea_ids": [], "repair_status": "medium_reasoning_understandable_2026_05_06", "review_notes": "Проверка среднего уровня 2026-05-06: решение понятно ИИ с рассуждением среднего уровня; при чтении не найдено скрытых непроверенных переходов.", "source_ids": [ "src-lktg-2026-project2-solutions-ru" ] } ], "difficulty": { "main": "national_final_medium", "local_score": 5, "comment": "Осенний сложный тур 2018/19, 8-9 класс, задача 7a на 5 баллов.", "status": "ai_checked" }, "tags": [ "trees", "goal_strategy_game" ], "properties": { "central_method": { "value": [ "strategy_argument", "invariant" ], "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": "Прежний архивный источник сохранён как дополнительный источник той же задачи." } } }