{ "id": "cmo-2019-p5-odd-cycle-edge-game", "title": "Игра в добавление рёбер до первого нечётного цикла и её варианты", "kind": { "primary": "olympiad_problem", "secondary": [ "graph_in_statement", "game" ] }, "language": "ru", "authors": [ { "name": "?", "status": "needs_human_review", "note": "Author name was normalized to '?' because previous value was not a person or author group (role_is_publisher_of_official_archive: Canadian Mathematical Society). Официальные листки CMO 2019 называют источник соревнования, но не указывают индивидуального автора задачи." } ], "problem_profile": { "objects": [ "complete_graph", "edge_adding_game", "odd_cycle", "bipartite_graph", "matching", "complete_bipartite_graph", "isolated_vertices" ], "methods": [ "strategy", "bipartite_graph_invariant", "parity_argument", "matching_preservation", "terminal_position_characterization", "parity", "matching_invariant", "involution_pairing_strategy" ], "transformations": [ "points_to_vertices", "segments_to_edges", "odd_cycle_avoidance_to_bipartiteness", "odd_cycle_free_to_bipartite", "terminal_safe_graph_to_complete_bipartite" ], "goal": [ "winning_strategy_classification", "classify_winner_by_n_mod_4", "prove_modified_game_first_player_win" ], "auxiliary_graph_type": [ "bipartite_graph", "complete_bipartite_graph" ], "invariants": [ "bipartiteness_before_losing_move", "parity_of_number_of_edges", "matching_covering_nonisolated_vertices", "matching_covers_nonisolated_vertices", "graph_invariant_under_involution", "paired_vertices_share_bipartition_class" ], "keywords": [ "cmo_2019_p5", "odd_cycle_game", "edge_adding_game", "complete_graph_game", "cmo_2019_problem5", "odd_cycle_avoidance_game", "safe_edge", "new_part_c" ], "status": "ai_checked" }, "statements": { "original": [ { "id": "stmt-original", "title": "Официальная формулировка", "text": "Дэвид и Джейкоб играют в игру на \\(n\\ge 3\\) точках плоскости, никакие три из которых не лежат на одной прямой. За ход игрок выбирает две точки, ещё не соединённые отрезком, и проводит между ними новый отрезок. Проигрывает тот игрок, чей ход впервые завершает цикл, состоящий из нечётного числа уже проведённых отрезков. В таком цикле концами каждого отрезка должны быть исходные \\(n\\) точек, а не точки пересечения отрезков, возникшие позже. Дэвид ходит первым. Определите все \\(n\\), при которых у Дэвида есть выигрышная стратегия.", "source_id": "src-cmo-2019-official", "status": "ai_checked", "self_contained": { "status": "ai_checked" }, "definition_ids": [ "cycle" ], "distinct_from": [ "stmt-graph" ] } ], "graph_theory": [ { "id": "stmt-graph", "title": "Игра до первого нечётного цикла", "text": "На множестве из \\(n\\ge 3\\) вершин изначально нет рёбер. Два игрока по очереди добавляют по одному ещё отсутствующему ребру полного графа \\(K_n\\); первым ходит первый игрок. Проигрывает тот игрок, после чьего хода построенный граф впервые содержит цикл нечётной длины. Определите все \\(n\\), при которых первый игрок имеет выигрышную стратегию.", "status": "ai_checked", "self_contained": { "status": "ai_checked" }, "definition_ids": [ "complete_graph", "cycle" ], "distinct_from": [ "stmt-original", "stmt-hint-bipartite-game" ] } ], "graph_hint_reformulations": [ { "id": "stmt-hint-bipartite-game", "title": "Подсказка через двудольность", "text": "До проигрышного хода построенный граф не содержит нечётных циклов, то есть остаётся двудольным. Назовём ход безопасным, если после добавления выбранного ребра граф всё ещё двудолен. Если безопасных ходов нет, то текущий двудольный граф уже является полным двудольным графом относительно своей двудольной раскраски, и следующий игрок вынужден проиграть. В этих терминах нужно определить, кто может гарантировать себе наличие безопасного хода на каждом своём ходе до проигрыша соперника.", "status": "ai_checked", "self_contained": { "status": "ai_checked" }, "definition_ids": [ "bipartite_graph", "cycle" ], "distinct_from": [ "stmt-original", "stmt-graph" ] } ], "olympiad_reformulations": [ { "id": "stmt-lktg-no-isolated-pair", "title": "Вариант с запретом соединять две изолированные вершины", "text": "Изменим правила: после первого хода Пети запрещается соединять ребром две изолированные вершины. Докажите, что при каждом чётном \\(n\\) выигрывает Петя.", "source_id": "src-lktg-2026-project2-problems-ru", "status": "source_verified", "self_contained": { "status": "ai_checked" }, "definition_ids": [ "cycle", "bipartite_graph", "matching" ] } ] }, "ideas": [ { "id": "idea-odd-cycle-bipartite", "title": "Нечётный цикл запрещён ровно до нарушения двудольности", "text": "Пока никто не проиграл, построенный граф двудолен. Безопасные ходы — это в точности добавления ещё отсутствующего ребра между разными долями некоторой двудольной раскраски текущего графа.", "tags": [ "coloring", "goal_strategy_game" ], "status": "ai_checked" }, { "id": "idea-good-graph-matching", "title": "Сохранять паросочетание на активных вершинах", "text": "При чётном \\(n\\) полезно следить за графами, в которых все вершины положительной степени покрываются паросочетанием. Игрок, контролирующий такие позиции, может законно расширять множество активных вершин как минимум на две.", "tags": [ "matching", "goal_strategy_game" ], "status": "ai_checked" }, { "id": "idea-complete-bipartite-parity", "title": "Конечная позиция — полный двудольный граф, а выигрывает паритет", "text": "Если безопасных ходов не осталось, текущий граф должен быть полным двудольным графом \\(K_{a,b}\\). Тогда число уже сделанных ходов равно \\(ab\\), и его чётность сравнивается с тем, чей сейчас ход.", "tags": [ "goal_strategy_game" ], "status": "ai_checked" }, { "id": "idea-involution-symmetry", "title": "Инволюция после первого ребра", "text": "В изменённой игре Петя фиксирует концы первого ребра и попарно переставляет остальные вершины, отвечая образом хода Васи; активная компонента остаётся единственной, а размеры долей в конце нечётны.", "tags": [ "symmetrization", "graph_symmetry" ], "status": "ai_checked" } ], "solutions": [ { "id": "sol-official-ru-expanded", "title": "Решение через двудольность, паросочетание и паритет", "text": "Ответ: Дэвид имеет выигрышную стратегию тогда и только тогда, когда \\(n\\equiv 2\\pmod 4\\).\n\nПерейдём к графовой формулировке: исходные точки считаем вершинами, а проведённые отрезки — рёбрами. Пересечения отрезков внутри плоскости не имеют значения, потому что в циклах разрешены только исходные точки как вершины. До проигрышного хода построенный граф не содержит нечётных циклов, а значит является двудольным. Будем называть ход безопасным, если после добавления ребра граф всё ещё не содержит нечётного цикла. Если перед ходом безопасных ходов нет, игрок всё равно обязан добавить какое-то ещё отсутствующее ребро и тем самым проигрывает.\n\nРазберём сначала нечётное \\(n\\). Покажем, что Джейкоб может играть очень просто: на каждом своём ходе, если безопасный ход существует, он делает любой безопасный ход. Предположим, что перед некоторым ходом Джейкоба безопасных ходов не осталось. Текущий граф двудолен; возьмём его двудольное разбиение на доли размеров \\(a\\) и \\(b\\), где \\(a+b=n\\). Если между разными долями есть ещё не проведённое ребро, его добавление сохраняет двудольность, то есть даёт безопасный ход. Значит, при отсутствии безопасных ходов граф уже должен быть полным двудольным графом \\(K_{a,b}\\) и иметь \\(ab\\) рёбер. Но \\(n\\) нечётно, поэтому одно из чисел \\(a,b\\) чётно, и \\(ab\\) чётно. С другой стороны, перед ходом Джейкоба уже сделано нечётное число ходов, ведь Дэвид ходит первым. Получили противоречие. Следовательно, пока Дэвид сам не проиграл, у Джейкоба всегда есть безопасный ход; при нечётном \\(n\\) Дэвид выиграть не может.\n\nТеперь пусть \\(n\\) чётно. Назовём граф хорошим, если все его вершины положительной степени можно покрыть паросочетанием, состоящим из уже проведённых рёбер. Иными словами, среди активных вершин есть паросочетание, покрывающее каждую активную вершину ровно один раз.\n\nДокажем ключевое наблюдение. Пусть после предыдущего хода некоторого игрока граф был хорошим, и ещё не все вершины активны. Тогда после своего следующего хода этот игрок может снова получить хороший граф, причём число активных вершин увеличится как минимум на две по сравнению с концом его предыдущего хода.\n\nДействительно, пусть \\(A\\) — множество активных вершин после предыдущего хода этого игрока, а \\(B\\) — множество остальных вершин. По хорошести \\(A\\) покрывается паросочетанием, значит \\(|A|\\) чётно; так как \\(n\\) чётно, число \\(|B|\\) тоже чётно. Рассмотрим ход соперника. Если он соединяет две вершины из \\(A\\), наш игрок отвечает ребром между двумя вершинами из \\(B\\). Если соперник соединяет две вершины из \\(B\\), наш игрок соединяет одну из этих двух вершин с какой-нибудь вершиной из \\(A\\); в самом первом раунде, когда \\(A\\) пусто, вместо этого он соединяет две другие вершины из \\(B\\). Если соперник соединяет вершину из \\(A\\) с вершиной из \\(B\\), то в \\(B\\) есть ещё одна вершина, потому что \\(|B|\\) чётно; наш игрок соединяет эти две вершины из \\(B\\). Во всех случаях ответное ребро имеет хотя бы один конец в вершине, которая до этого была изолированной, поэтому оно не может замкнуть цикл и является безопасным. Старое паросочетание на \\(A\\) сохраняется, а новые активные вершины покрываются либо ребром соперника, либо ответным ребром, согласно описанным случаям. Значит, граф снова хороший, а активных вершин стало как минимум на две больше. Наблюдение доказано.\n\nПусть \\(n\\equiv 2\\pmod 4\\). Пустой граф хорош, поэтому Дэвид применяет доказанное наблюдение к своим ходам и безопасными ходами добивается появления совершенного паросочетания; это произойдёт не позднее чем после того, как станут активны все \\(n\\) вершин. После этого Дэвид просто делает любой безопасный ход, если такой есть. Предположим, что перед некоторым ходом Дэвида безопасных ходов нет. Тогда текущий граф — полный двудольный граф \\(K_{a,b}\\). Кроме того, в нём уже есть совершенное паросочетание. Если бы одна из долей имела больше \\(n/2\\) вершин, две вершины этой доли были бы соединены ребром совершенного паросочетания, что невозможно в двудольном графе. Значит, обе доли имеют размер \\(n/2\\), и число рёбер равно \\((n/2)^2=n^2/4\\). При \\(n\\equiv 2\\pmod 4\\) число \\(n/2\\) нечётно, поэтому \\(n^2/4\\) нечётно. Но перед ходом Дэвида уже сделано чётное число ходов. Противоречие. Следовательно, Дэвид никогда не оказывается первым игроком без безопасного хода; значит, в этом случае он выигрывает.\n\nОстаётся случай \\(n\\equiv 0\\pmod 4\\). После первого хода Дэвида граф состоит из одного ребра и потому хорош. Теперь уже Джейкоб применяет ключевое наблюдение к своим ходам и добивается появления совершенного паросочетания, а затем делает любой безопасный ход, если он есть. Если бы перед ходом Джейкоба безопасных ходов не осталось, текущий граф, как и выше, был бы полным двудольным графом с равными долями размера \\(n/2\\) и имел бы \\(n^2/4\\) рёбер. При \\(n\\equiv 0\\pmod 4\\) число \\(n/2\\) чётно, значит \\(n^2/4\\) чётно. Но перед ходом Джейкоба сделано нечётное число ходов. Это невозможно. Поэтому Джейкоб тоже всегда сможет ходить безопасно, пока Дэвид не проиграет. Итак, Дэвид выигрывает ровно при \\(n\\equiv 2\\pmod 4\\).", "idea_ids": [ "idea-odd-cycle-bipartite", "idea-good-graph-matching", "idea-complete-bipartite-parity" ], "standard_idea_ids": [], "status": "ai_checked", "definition_ids": [ "complete_graph", "bipartite_graph", "matching", "cycle" ] }, { "id": "sol-lktg-no-isolated-pair", "title": "Симметрическая стратегия в варианте без новых компонент", "text": "Пусть \\(n\\) чётно. Первым ходом Петя добавляет ребро \\(ab\\). Он фиксирует инволюцию \\(\\sigma\\): вершины \\(a,b\\) неподвижны, а все остальные разбиты на пары \\(x,\\sigma(x)\\). После каждого своего хода Петя поддерживает инварианты: граф сохраняется преобразованием \\(\\sigma\\); обе вершины каждой уже активной пары \\(x,\\sigma(x)\\) лежат в одной доле двудольного графа; все неизолированные вершины образуют одну компоненту. Последнее верно, потому что после первого хода правила запрещают начинать новую компоненту ребром между двумя изолированными вершинами.\n\nПусть Вася сделал безопасный ход. Если он присоединил изолированную вершину \\(x\\) ребром \\(vx\\), Петя добавляет \\(\\sigma(v)\\sigma(x)\\). Вершина \\(\\sigma(x)\\) тоже была изолирована, поэтому ход разрешён и безопасен. Если Вася добавил ребро \\(uv\\) между активными вершинами, Петя добавляет \\(\\sigma(u)\\sigma(v)\\). Это другое ещё не добавленное ребро. Ребро, совпадающее со своим образом, было бы либо первым ребром \\(ab\\), либо соединяло бы парные вершины \\(x,\\sigma(x)\\); но активные парные вершины лежат в одной доле, поэтому такой ход Васи уже создавал бы нечётный цикл. Образ безопасного ребра безопасен, поскольку \\(\\sigma\\) сохраняет доли. Так Петя отвечает на каждый безопасный ход Васи.\n\nПока есть изолированная вершина, её можно безопасно присоединить к активной компоненте, поэтому игра заканчивается только после активации всех вершин. Тогда в каждой доле лежит одна из вершин \\(a,b\\) и некоторое число полных \\(\\sigma\\)-пар, так что размеры обеих долей нечётны. Конечный полный двудольный граф имеет нечётное число рёбер. Следовательно, последний безопасный ход делает Петя, после чего Вася вынужден создать нечётный цикл. Петя выигрывает при каждом чётном \\(n\\).", "idea_ids": [ "idea-involution-symmetry" ], "standard_idea_ids": [ "symmetrization" ], "status": "ai_checked", "definition_ids": [ "cycle", "bipartite_graph", "matching" ], "source_id": "src-lktg-2026-project2-solutions-ru" } ], "difficulty": { "main": "national_final_hard", "local_score": 9, "comment": "CMO 2019 P5; сложная стратегическая графовая игра с инвариантом двудольности, паросочетанием на активных вершинах и финальным паритетным противоречием.", "status": "ai_checked" }, "tags": [ "goal_strategy_game", "coloring", "matching", "extremal_graph_theory", "symmetrization", "graph_symmetry", "invariant", "goal_classification" ], "properties": { "central_method": { "value": [ "bipartite_invariant", "matching_preservation", "parity_argument" ], "status": "ai_checked" } }, "sources": [ { "source_id": "src-cmo-2019-official", "role": "problem_statement_official", "status": "source_verified", "statement_ids": [ "stmt-original" ] }, { "source_id": "src-cmo-2019-solutions", "role": "official_solutions", "status": "source_verified", "solution_ids": [ "sol-official-ru-expanded" ] }, { "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": "Официальные условия, задача 3", "statement_ids": [ "stmt-lktg-no-isolated-pair" ], "note": "PDF прямо указывает: пункты а, б - Canadian Mathematical Olympiad 2019, задача 5; пункт в - новое предложение соавтора, имя которого не приведено." }, { "source_id": "src-lktg-2026-project2-solutions-ru", "role": "official_complete_solution", "status": "source_verified", "title": "Официальные решения, задача 3", "solution_ids": [ "sol-lktg-no-isolated-pair" ] } ], "editorial": { "created_by": "ai", "created_at": "2026-04-27", "review_status": "ai_checked", "public_ready": true, "notes": [ "2026-04-27: официальные условие и решение сверены с PDF CMS CMO 2019; отдельный автор задачи там не указан.", "2026-04-27: исходная и графовая формулировки явно говорят, что проигрывает игрок, чей ход первым создаёт нечётный цикл; более сильная переформулировка через двудольную игру оставлена как графовая подсказка.", "2026-04-27: русское решение переписано по официальному решению; сжатый шаг о сохранении паросочетания раскрыт.", "2026-08-15: проектная перепечатка CMO не вынесена в отдельную карточку; сюда добавлен только новый вариант с запретом соединять две изолированные вершины и его решение." ], "relations_status": "deep_done", "solution_classification": { "type": "official_complete_or_near_complete", "status": "ai_checked", "confidence": 0.82, "basis": "официальный источник решения и несжатый текст решения", "notes": "Текущий текст основан на официальном источнике и выглядит полным или почти полным.", "label": "официальное полное/почти полное" } } }