{ "id": "lktg-2026-project2-problem06-two-tokens-reversing-arcs", "title": "Две фишки и развороты пройденных стрелок", "kind": { "primary": "problem", "secondary": [ "game", "directed_graph", "dynamic_orientation" ] }, "language": "ru", "authors": [ { "name": "М. Дидин", "role": "author_of_source_problem", "status": "source_verified", "note": "Официальный PDF указывает источник «М. Дидин, 2026»; пункт а отдельно назван предложением соавтора без имени." } ], "problem_profile": { "objects": [ "finite_directed_graph", "two_tokens", "edge_reversal_walk", "directed_paths" ], "methods": [ "edge_disjoint_path_invariant", "path_tail_switching", "integer_potential", "eventual_equality_analysis" ], "transformations": [ "full_position_to_two_paths", "walk_to_simple_path_by_cycle_deletion" ], "goal": [ "prove_reachability_after_finite_disturbance", "prove_forced_win_in_alternating_game", "bound_number_of_moves" ], "auxiliary_graph_type": [ "two_edge_disjoint_directed_paths" ], "invariants": [ "paths_end_at_target_and_share_no_edges", "nonincreasing_total_path_length_with_turn_bit" ], "keywords": [ "two_tokens", "reversing_arcs", "tail_switching", "path_length_potential" ], "status": "ai_checked" }, "statements": { "original": [ { "id": "stmt-problem06", "title": "Достижение цели при развороте каждого пройденного ребра", "text": "На конечном ориентированном графе выбраны две различные вершины \\(A\\) и \\(B\\). В \\(A\\) стоит фишка Пети, в \\(B\\) - фишка Васи; из \\(A\\) в \\(B\\) существует ориентированный путь. При каждом передвижении фишка идёт по выходящей стрелке, после чего направление пройденного ребра немедленно меняется на противоположное. Фишки могут находиться в одной вершине; положение одной фишки никак не ограничивает движение другой. Петя хочет привести свою фишку в вершину \\(B\\).\n\nа) Сначала Вася совершает любое конечное число допустимых передвижений своей фишки, возможно ни одного, и после этого больше не ходит. Затем ходит только Петя. Докажите, что после любых ходов Васи Петя может попасть в \\(B\\).\n\nб) Теперь игроки ходят по очереди, начинает Петя. За ход игрок может либо пропустить ход, либо передвинуть свою фишку. Петя выигрывает, как только его фишка впервые попадает в \\(B\\); если этого никогда не происходит, выигрывает Вася. Существует ли исходный ориентированный граф, на котором Вася может помешать Пете выиграть?", "source_id": "src-lktg-2026-project2-problems-ru", "status": "source_verified", "self_contained": { "status": "ai_checked" }, "definition_ids": [ "directed_graph", "path" ] } ] }, "ideas": [ { "id": "idea-two-path-memory", "title": "Хранить только два пути к цели", "text": "Поддерживаются не имеющие общих рёбер направленные пути \\(P\\) от фишки Пети к \\(B\\) и \\(Q\\) от фишки Васи к \\(B\\); остальные рёбра позиции для стратегии несущественны.", "tags": [ "invariant", "graph_model" ], "status": "ai_checked" }, { "id": "idea-tail-switching", "title": "Пересадка хвостов при ходе Васи по пути Пети", "text": "Если Вася проходит ребро пути \\(P\\), это ребро удаляется, а оставшиеся части \\(P\\) и \\(Q\\) переклеиваются так, чтобы оба новых пути снова шли к \\(B\\) и не имели общих рёбер.", "tags": [ "invariant", "construction" ], "status": "ai_checked" }, { "id": "idea-length-turn-potential", "title": "Сумма длин путей и бит очереди", "text": "Потенциал \\(S=|P|+|Q|+\\varepsilon\\), где \\(\\varepsilon\\) кодирует очередь хода, не возрастает; если он стабилизировался, путь Пети укорачивается на каждом его ходу и не меняется ходами Васи.", "tags": [ "potential_function", "goal_strategy_game" ], "status": "ai_checked" } ], "solutions": [ { "id": "sol-problem06-complete", "title": "Полное решение через два пути и целый потенциал", "text": "В каждый момент будем поддерживать два направленных пути к цели: \\(P\\) идёт от текущего положения фишки Пети до \\(B\\), а \\(Q\\) - от текущего положения фишки Васи до \\(B\\). Пути не имеют общих рёбер, хотя могут иметь общие вершины. Изначально \\(P\\) - данный в условии путь из \\(A\\) в \\(B\\), а \\(Q\\) - пустой путь из \\(B\\) в \\(B\\).\n\nОпишем перестройку. На своём ходу Петя проходит первое ребро \\(P\\); после разворота это ребро удаляется из \\(P\\). Если \\(P\\) стал пустым, Петя уже находится в \\(B\\). Пусть Вася прошёл по ребру \\(q\\to r\\), которое после хода стало \\(r\\to q\\). Если ребро \\(qr\\) не лежало ни в \\(P\\), ни в \\(Q\\), допишем \\(r\\to q\\) в начало \\(Q\\). Если \\(q\\to r\\) лежало в \\(Q\\), оно было первым ребром \\(Q\\), и мы удаляем его. Если \\(q\\to r\\) лежало в \\(P\\), представим\n\\[P=P_0+(q\\to r)+P_1\\]\nи заменим пути по правилу\n\\[P\\leftarrow P_0+Q,\\qquad Q\\leftarrow P_1.\\]\nЭто пересадка хвостов в вершине \\(q\\). Старые пути не имели общих рёбер, а перевёрнутое ребро из обоих новых маршрутов удалено, поэтому новые маршруты также не имеют общих рёбер. Если после склейки какая-либо вершина встречается дважды, вырежем заключённый между двумя появлениями направленный цикл. Так направленный маршрут превращается в простой направленный путь; концы, ориентация и отсутствие общих рёбер сохраняются. В первом случае возникающие циклы удаляются тем же способом. Значит, инвариант всегда можно поддержать.\n\nа) После каждого из конечного числа ходов Васи перестраиваем \\(P,Q\\) по этим правилам. Когда Вася остановился, путь \\(P\\) направлен из \\(A\\) в \\(B\\). Петя проходит его по порядку. После каждого хода разворачивается только уже пройденное и удалённое из \\(P\\) ребро, поэтому оставшийся хвост по-прежнему направлен к \\(B\\). Петя достигает цели.\n\nб) Ответ: такого исходного графа не существует; Петя выигрывает на любом допустимом графе. Петя никогда не пропускает ход, пока \\(P\\) непуст. Положим\n\\[S=|P|+|Q|+\\varepsilon,\\]\nгде \\(\\varepsilon=0\\) перед ходом Пети и \\(\\varepsilon=1\\) перед ходом Васи. На ходу Пети длина \\(P\\) уменьшается на 1, а \\(\\varepsilon\\) меняется с 0 на 1, поэтому \\(S\\) не меняется. После хода Васи \\(\\varepsilon\\) меняется с 1 на 0. Если он прошёл по ребру вне \\(P\\cup Q\\), длина \\(Q\\) выросла не более чем на 1, поэтому \\(S\\) не увеличилась. Если он прошёл по \\(Q\\), длина \\(Q\\) уменьшилась на 1. При пересадке хвостов из суммарной длины исчезло ребро \\(qr\\), поэтому\n\\[|P_{\\rm new}|+|Q_{\\rm new}|\\le |P_{\\rm old}|+|Q_{\\rm old}|-1.\\]\nЕсли Вася пропускает ход, пути не меняются, а \\(\\varepsilon\\) уменьшается на 1. Следовательно, \\(S\\) - неотрицательное целое число, которое не возрастает после каждого хода; во всех случаях, кроме прохода Васи по новому ребру вне обоих путей без потерь при удалении циклов, ход Васи строго уменьшает \\(S\\).\n\nПредположим, что партия бесконечна. Неотрицательная целая величина \\(S\\) не может строго уменьшаться бесконечно, поэтому с некоторого момента постоянна. Тогда каждый ход Васи обязан быть единственным случаем равенства: он проходит по ребру вне \\(P\\cup Q\\), добавляет к \\(Q\\) ровно одно ребро и при удалении циклов ничего не теряется. Такой ход не меняет \\(P\\). Но каждый ход Пети удаляет первое ребро \\(P\\). Следовательно, через конечное число ходов \\(P\\) станет пустым, и Петя попадёт в \\(B\\), противоречие. Значит, Петя обязательно выигрывает.\n\nПолучим также явную оценку. Пусть в исходном графе \\(n\\) вершин и \\(L_0=|P_0|\\le n-1\\). Рассмотрим \\(L=|P|+|Q|\\) перед ходами Пети. За полный раунд \\(L\\) не возрастает. Пока \\(L=k\\) и не уменьшается, Вася каждый раз попадает в случай равенства и не меняет \\(P\\), а Петя укорачивает \\(P\\) на одно ребро. Поэтому не более чем через \\(k\\) ходов Пети величина \\(L\\) уменьшится или Петя победит. Число ходов Пети не превосходит\n\\[L_0+(L_0-1)+\\cdots+1\\le\\frac{n(n-1)}2.\\]", "idea_ids": [ "idea-two-path-memory", "idea-tail-switching", "idea-length-turn-potential" ], "standard_idea_ids": [ "invariant", "potential_function" ], "status": "ai_checked", "definition_ids": [ "directed_graph", "path", "cycle" ], "source_id": "src-lktg-2026-project2-solutions-ru" } ], "difficulty": { "main": "national_final_medium", "local_score": 8, "comment": "Официальная шкала проекта: а) 2/5, б) 4/5. Полная поочерёдная игра требует устойчивого инварианта двух путей и анализа равенства в потенциале.", "status": "source_verified" }, "tags": [ "invariant", "potential_function", "dynamics", "construction", "goal_strategy_game", "goal_bound" ], "sources": [ { "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": "Официальные условия, задача 6", "statement_ids": [ "stmt-problem06" ], "note": "PDF указывает источник «М. Дидин, 2026» и отдельно сообщает, что пункт а предложен соавтором без указания имени." }, { "source_id": "src-lktg-2026-project2-solutions-ru", "role": "official_complete_solution", "status": "source_verified", "title": "Официальные решения, задача 6" } ], "editorial": { "created_by": "ai", "created_at": "2026-08-15", "review_status": "ai_checked", "public_ready": true, "graph_theory_duplicate_removed": true, "notes": [ "Оба подпункта закрыты; ответ пункта б отрицательный: графа, на котором Вася способен вечно мешать, не существует.", "Решение не зависит от демонстрационного рисунка в PDF: все три перестройки путей и удаление направленных циклов описаны текстом.", "Имя соавтора пункта а не указано в PDF и не добавлено." ], "relations_status": "deep_done", "solution_classification": { "type": "official_complete_or_near_complete", "label": "официальное полное решение", "status": "ai_checked", "confidence": 0.98, "basis": "Официальный PDF решений содержит полный инвариант двух путей, доказательство конечности и количественную оценку.", "notes": "Все случаи хода Васи проверены; анализ стабилизации потенциала исключает бесконечную игру." } } }