{ "id": "lktg-2026-project2-problem07-two-degenerate-orientation-game", "title": "Парная стратегия против ориентированного цикла: 2-вырожденные графы и решётки", "kind": { "primary": "problem", "secondary": [ "game", "orientation_characterization" ] }, "language": "ru", "problem_profile": { "objects": [ "two_degenerate_graph", "acyclic_orientation", "orientation_game", "edge_pairs", "infinite_square_grid", "rectangular_grid_graph", "reference_orientation" ], "methods": [ "degeneracy_ordering", "sink_in_dag", "pairing_strategy", "cycle_sink_obstruction", "acyclic_reference_orientation", "coordinate_extremum", "edge_parity" ], "transformations": [ "vertex_deletion_order_to_orientation", "reference_orientation_to_edge_pairs", "grid_coordinates_to_incoming_edge_pairs", "finite_grid_to_structural_and_arbitrary_pairs" ], "goal": [ "characterize_two_degeneracy", "give_acyclist_winning_strategy", "determine_winner_on_infinite_grid", "prove_parity_cases_on_finite_grid" ], "auxiliary_graph_type": [ "acyclic_reference_orientation", "directed_square_grid" ], "invariants": [ "indegree_at_most_two", "paired_edges_have_equal_direction_relative_to_center", "acyclic_coordinate_orientation" ], "keywords": [ "two_degenerate_graph", "orientation_game", "cycle_prevention_pairing", "square_grid", "pairing_by_left_and_lower_edges", "grid_parity" ], "status": "ai_checked" }, "statements": { "original": [ { "id": "stmt-problem07", "title": "Ориентация 2-вырожденного графа и игра на его рёбрах", "text": "В игре на неориентированном графе \\(G\\) Циклист и Ациклист по очереди выбирают ещё не ориентированное ребро и направляют его в любую сторону. Циклист выигрывает немедленно, как только появляется ориентированный цикл длины не менее 3; если все рёбра ориентированы и такого цикла нет, выигрывает Ациклист.\n\nГраф называется 2-вырожденным, если в каждом его непустом подграфе есть вершина степени не больше 2.\n\nа) Докажите, что граф 2-вырожден тогда и только тогда, когда существует ациклическая ориентация всех его рёбер с входящей степенью каждой вершины не больше 2. В этом пункте игра не ведётся: нужно лишь ориентировать рёбра графа.\n\nб) Пусть \\(G\\) - конечный 2-вырожденный граф. Докажите, что Ациклист выигрывает, если \\(|E(G)|\\) чётно и начинает Циклист, а также если \\(|E(G)|\\) нечётно и начинает Ациклист.", "source_id": "src-lktg-2026-project2-problems-ru", "status": "source_verified", "self_contained": { "status": "ai_checked" }, "definition_ids": [ "orientation", "cycle", "degree", "indegree", "outdegree" ] } ], "olympiad_reformulations": [ { "id": "stmt-square-grids", "title": "Формулировки для бесконечной и прямоугольной квадратных решёток", "text": "На неориентированном графе \\(G\\) Циклист и Ациклист по очереди выбирают ещё не ориентированное ребро и направляют его в любую сторону. Циклист выигрывает немедленно, как только появляется ориентированный цикл длины не менее 3; если все рёбра ориентированы и цикла нет, выигрывает Ациклист. На бесконечном графе Циклист должен создать конечный цикл за конечное число ходов; если этого никогда не происходит, выигрывает Ациклист.\n\nа) На бесконечной квадратной решётке с вершинами \\((x,y)\\in\\mathbb Z^2\\) и рёбрами между вершинами на расстоянии 1 определите победителя, когда первым ходит Циклист и когда первым ходит Ациклист.\n\nб) Пусть \\(m,n\\ge1\\), а \\(P_m\\square P_n\\) - конечная прямоугольная решётка, где \\(P_k\\) обозначает путь на \\(k\\) вершинах. Докажите, что Ациклист выигрывает, если \\(m\\) и \\(n\\) одной чётности и начинает Циклист, а также если \\(m\\) и \\(n\\) разной чётности и начинает Ациклист.", "source_id": "src-lktg-2026-project2-problems-ru", "status": "source_verified", "self_contained": { "status": "ai_checked" }, "definition_ids": [ "orientation", "cycle", "path" ] } ] }, "ideas": [ { "id": "idea-degeneracy-order", "title": "Порядок удаления задаёт ациклическую ориентацию", "text": "Каждое ребро направляется от позже удалённой вершины к раньше удалённой; номера вдоль стрелок убывают, а входящая степень ограничена степенью в момент удаления.", "tags": [ "induction", "goal_characterization" ], "status": "ai_checked" }, { "id": "idea-reference-incoming-pairs", "title": "Пары входящих рёбер эталонной ориентации", "text": "Два эталонных ребра, входящих в одну вершину, связываются в пару; Ациклист направляет их одинаково относительно центра, что несовместимо с ориентированным циклом.", "tags": [ "invariant", "goal_strategy_game" ], "status": "ai_checked" }, { "id": "idea-grid-reference-orientation", "title": "Рёбра слева и снизу как структурная пара", "text": "В эталонной ориентации вправо и вверх в каждую вершину входят рёбра слева и снизу; одинаковое направление этих пар в игре запрещает ориентированный цикл.", "tags": [ "invariant", "graph_symmetry" ], "status": "ai_checked" }, { "id": "idea-origin-defect", "title": "Один непарный вход в начале координат", "text": "При первом ходе Ациклиста горизонтальные рёбра нулевой строки направляются от начала координат, так что только в начале координат остаётся одно входящее эталонное ребро, уже занятое первым ходом.", "tags": [ "construction", "goal_strategy_game" ], "status": "ai_checked" }, { "id": "idea-max-coordinate-cycle", "title": "Вершина цикла с максимальной суммой координат", "text": "В конечной решётке оба ребра цикла при вершине с максимальным \\(x+y\\) идут влево и вниз и образуют структурную пару.", "tags": [ "extremal_choice", "invariant" ], "status": "ai_checked" } ], "solutions": [ { "id": "sol-problem07-complete", "title": "Полное решение пунктов а и б", "text": "а) Пусть граф 2-вырожден. Будем по одной удалять вершины, каждый раз выбирая в оставшемся графе вершину степени не больше 2. Получим порядок \\(v_1,v_2,\\ldots,v_n\\), где \\(v_i\\) удалена раньше \\(v_{i+1}\\). Каждое ребро направим от вершины, удалённой позже, к вершине, удалённой раньше. В вершину \\(v_i\\) входят только рёбра, соединявшие её в момент удаления с ещё не удалёнными вершинами, поэтому входящая степень не больше 2. Вдоль каждой стрелки индекс вершины уменьшается, так что ориентированного цикла нет.\n\nОбратно, пусть дана ациклическая ориентация, в которой входящая степень каждой вершины не больше 2. Возьмём любой непустой подграф и ограничим на него ориентацию; она остаётся ациклической. В конечном ациклическом ориентированном графе есть сток. Иначе из каждой вершины выходила бы стрелка, и, всё время двигаясь по стрелкам, мы в конечном графе повторили бы вершину и получили ориентированный цикл. У стока все рёбра рассматриваемого подграфа входят в него, поэтому его степень не больше 2. Следовательно, исходный граф 2-вырожден.\n\nб) Выберем эталонную ациклическую ориентацию \\(D\\) из пункта а. Для каждой вершины, в которую в \\(D\\) входят ровно два ребра, объединим эти рёбра в пару. Пары не пересекаются, потому что каждое ребро входит ровно в одну из своих вершин.\n\nКлючевое наблюдение: если в настоящей игре два ребра каждой такой пары направлены одинаково относительно их общей вершины - либо оба входят, либо оба выходят, - то ориентированного цикла нет. Действительно, предположим, что цикл появился. Ограничим эталонную ориентацию \\(D\\) на рёбра этого цикла. Она ациклична, поэтому на цикле есть сток: вершина, в которую в \\(D\\) входят оба соседних ребра цикла. Эти два ребра образуют выделенную пару. Но в настоящем ориентированном цикле одно из них входит в вершину, а другое выходит, что противоречит условию пары.\n\nЕсли \\(|E(G)|\\) чётно и начинает Циклист, число рёбер, не вошедших в выделенные пары, тоже чётно. Произвольно разобьём их на пары. После каждого хода Циклиста Ациклист берёт второе ребро той же пары. Для выделенной пары он выбирает направление так, чтобы оба ребра одинаково смотрели относительно общей вершины; для произвольной пары направление ответа неважно.\n\nЕсли \\(|E(G)|\\) нечётно и начинает Ациклист, среди непарных рёбер есть хотя бы одно, поскольку выделенные пары содержат чётное число рёбер. Первым ходом Ациклист ориентирует одно непарное ребро как угодно. После этого оставшиеся непарные рёбра разбиваются на пары, и далее действует то же правило ответа.\n\nОстаётся проверить, что Циклист не успеет замкнуть цикл своим ходом до ответа Ациклиста. Перед каждым его ходом любая выделенная пара либо не тронута, либо уже закончена и направлена одинаково относительно центра. Если новая стрелка замкнула цикл, возьмём сток эталонной ориентации \\(D\\) на этом цикле. Оба соседних с ним ребра образуют выделенную пару. Она не могла быть закончена раньше, потому что её направления несовместимы с циклом; она не могла быть и нетронутой, потому что оба её ребра уже входят в возникший цикл. Противоречие. После ответа Ациклиста парный инвариант снова выполнен. Значит, цикл не возникает ни после чьего хода, и Ациклист выигрывает.", "idea_ids": [ "idea-degeneracy-order", "idea-reference-incoming-pairs" ], "standard_idea_ids": [ "greedy_ordering", "invariant" ], "status": "ai_checked", "definition_ids": [ "orientation", "cycle", "degree", "indegree", "outdegree" ], "source_id": "src-lktg-2026-project2-solutions-ru" }, { "id": "sol-square-grid-pairing", "title": "Геометрическая реализация парной стратегии на решётке", "text": "а) На бесконечной квадратной решётке Ациклист выигрывает при обоих порядках хода.\n\nПусть начинает Циклист. В качестве эталонной ориентации \\(D\\) направим все горизонтальные рёбра вправо, а вертикальные вверх. В каждую вершину входят ровно два эталонных ребра - слева и снизу; объединим их в пару. После хода Циклиста Ациклист берёт второе ребро той же пары и направляет его так же относительно общей вершины, как первое. Ориентированный цикл невозможен: ограниченная на его рёбра эталонная ориентация ациклична, потому что вдоль каждой её стрелки растёт хотя бы одна координата. Поэтому на цикле есть эталонный сток, и два соседних с ним ребра составляют пару. В игровом ориентированном цикле одно из них входит в сток, а другое выходит, тогда как стратегия направляет их одинаково относительно центра. Цикл не может появиться и непосредственно после хода Циклиста: перед этим соответствующая структурная пара либо нетронута, либо уже закончена; в первом случае оба её ребра не могли оказаться в новом цикле, во втором их направления несовместимы с циклом. Бесконечность решётки не мешает доказательству, потому что любой победный цикл конечен.\n\nПусть начинает Ациклист. Первым ходом она направляет ребро \\((0,-1)(0,0)\\) вверх. Построим изменённую эталонную ориентацию: все вертикальные рёбра направлены вверх; на строке \\(y=0\\) горизонтальные рёбра направлены от начала координат; на остальных строках горизонтальные рёбра направлены вправо. Эта ориентация ациклична. Вдоль вертикальной стрелки координата \\(y\\) строго растёт, поэтому цикл не может содержать вертикальных рёбер; внутри каждой строки стрелки образуют направленные пути без циклов. В начало координат входит ровно одно эталонное ребро - уже ориентированное первым ходом. В каждую другую вершину входят ровно два ребра. Их Ациклист попарно связывает и далее отвечает по тому же правилу. Единственное непарное ребро уже занято первым ходом, поэтому ориентированный цикл не возникнет.\n\nб) В графе \\(P_m\\square P_n\\) число рёбер равно\n\\[m(n-1)+n(m-1)=2mn-m-n,\\]\nа значит, \\(|E(P_m\\square P_n)|\\equiv m+n\\pmod2\\). Дадим независимую парную стратегию. Мысленно направим все горизонтальные рёбра вправо, а вертикальные вверх. В каждой вершине, имеющей соседа слева и соседа снизу, объединим два приходящих от них ребра в структурную пару. Остальные рёбра пока оставим без пары.\n\nЕсли число рёбер чётно и начинает Циклист, оставшихся рёбер тоже чётное число; произвольно разобьём их на пары. Если число рёбер нечётно и начинает Ациклист, оставшихся рёбер нечётное и положительное число. Первым ходом Ациклист ориентирует одно из них как угодно, а остальные разбивает на пары. Далее после хода Циклиста она всегда берёт второе ребро той же пары. В структурной паре два ребра направляются одинаково относительно общей вершины; в произвольной паре направление ответа неважно.\n\nОриентированный цикл невозможен. В любом цикле решётки возьмём вершину с наибольшей суммой координат. Оба ребра цикла при этой вершине идут влево и вниз, то есть образуют структурную пару. Но в ориентированном цикле одно из них входит в вершину, а другое выходит, тогда как стратегия направляет их одинаково относительно вершины. Цикл не возникает и сразу после хода Циклиста по той же проверке нетронутой или уже законченной пары. Значит, Ациклист выигрывает. Чётность числа рёбер совпадает с чётностью \\(m+n\\): она чётна, когда \\(m,n\\) одной чётности, и нечётна, когда они разной чётности. Это даёт оба требуемых случая. При \\(m=n=1\\) рёбер нет, и Ациклист выигрывает автоматически.", "idea_ids": [ "idea-grid-reference-orientation", "idea-origin-defect", "idea-max-coordinate-cycle" ], "standard_idea_ids": [ "invariant", "extremal_choice" ], "status": "ai_checked", "definition_ids": [ "orientation", "cycle", "path" ], "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": [ "induction", "invariant", "goal_characterization", "goal_strategy_game", "dynamics", "planar_graphs", "graph_symmetry", "extremal_choice" ], "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": "Официальные условия, задача 7", "statement_ids": [ "stmt-problem07", "stmt-square-grids" ], "note": "В PDF задача названа составительской; конкретный автор не указан." }, { "source_id": "src-lktg-2026-project2-solutions-ru", "role": "official_complete_solution", "status": "source_verified", "title": "Официальные решения, задача 7" } ], "editorial": { "created_by": "ai", "created_at": "2026-08-15", "review_status": "ai_checked", "public_ready": true, "graph_theory_duplicate_removed": true, "notes": [ "Общие правила ориентационной игры из PDF включены в statement, поэтому карточка не зависит от соседних задач сборника.", "Проверка невозможности цикла до ответа Ациклиста перенесена явно.", "Задача о квадратных решётках хранится как геометрическая формулировка той же парной стратегии, а не как отдельная карточка." ], "relations_status": "deep_done", "solution_classification": { "type": "official_complete_or_near_complete", "label": "официальное полное решение", "status": "ai_checked", "confidence": 0.98, "basis": "Официальный PDF содержит полное доказательство характеризации и игровой стратегии.", "notes": "Решение самодостаточно доказывает существование стока в конечном ациклическом орграфе." } } }