{ "id": "lktg-2026-bella-chingiz-perfect-matching-bias-1-2-and-1-3", "title": "Белла и Чингиз с начальным совершенным паросочетанием, версии 1:2 и 1:3", "kind": { "primary": "olympiad_problem", "secondary": [ "graph_in_statement", "game", "author_variant" ] }, "language": "ru", "authors": [], "problem_profile": { "objects": [ "complete_graph", "edge_coloring", "perfect_matching", "clique" ], "methods": [ "strategy", "pairing_strategy", "fixed_point_free_involution" ], "transformations": [ "white_clique_to_larger_black_clique" ], "goal": [ "winning_strategy" ], "auxiliary_graph_type": [], "invariants": [ "ordered_pairs", "black_partner_edges" ], "keywords": [ "bella_chingiz", "biased_clique_game", "one_to_two", "initial_black_perfect_matching" ], "status": "ai_checked" }, "statements": { "original": [ { "id": "stmt-original", "title": "Версия 1:2", "text": "Пусть \\(n\\ge 2\\) — чётное число. Белла и Чингиз играют на рёбрах полного графа \\(K_n\\). До первого хода Чингиз красит в чёрный цвет рёбра некоторого совершенного паросочетания, то есть \\(n/2\\) попарно непересекающихся рёбер, покрывающих все вершины. Затем игра идёт по раундам. Белла красит одно свободное ребро белым, после чего Чингиз красит два свободных ребра чёрным; если свободных рёбер осталось меньше двух, он красит все оставшиеся. После окраски всех рёбер Чингиз выигрывает, если наибольшая чёрная клика строго больше наибольшей белой. Докажите, что Чингиз имеет выигрышную стратегию.", "status": "ai_checked", "self_contained": { "status": "ai_checked" }, "definition_ids": [ "complete_graph", "matching", "clique" ], "distinct_from": [ "stmt-bias-1-3" ] }, { "id": "stmt-bias-1-3", "title": "Версия 1:3", "text": "Пусть \\(n\\ge 2\\) — чётное число. Белла и Чингиз играют на рёбрах полного графа \\(K_n\\). До первого хода Чингиз красит в чёрный цвет рёбра некоторого совершенного паросочетания, то есть \\(n/2\\) попарно непересекающихся рёбер, покрывающих все вершины. Затем игра идёт по раундам. Белла красит одно свободное ребро белым, после чего Чингиз красит три свободных ребра чёрным; если свободных рёбер осталось меньше трёх, он красит все оставшиеся. После окраски всех рёбер Чингиз выигрывает, если наибольшая чёрная клика строго больше наибольшей белой. Докажите, что Чингиз имеет выигрышную стратегию.", "status": "ai_checked", "self_contained": { "status": "ai_checked" }, "definition_ids": [ "complete_graph", "matching", "clique" ] } ], "graph_theory": [], "olympiad_reformulations": [] }, "ideas": [ { "id": "idea-ordered-pair-copy", "title": "Копировать белую клику по упорядоченным парам", "text": "Упорядочим пары начального паросочетания. На белое ребро между более ранней и более поздней парами Чингиз красит ребро между противоположными вершинами и перекрёстное ребро от исходной вершины ранней пары к противоположной вершине поздней пары.", "tags": [ "matching", "graph_symmetry", "invariant" ], "status": "ai_checked" } ], "solutions": [ { "id": "sol-ordered-perfect-matching", "title": "Единая стратегия для версий 1:2 и 1:3", "text": "Обозначим через \\(\\varphi(x)\\) партнёра вершины \\(x\\) в начальном чёрном совершенном паросочетании и линейно упорядочим его пары.\n\nПусть Белла покрасила ребро \\(xy\\), причём пара вершины \\(x\\) стоит раньше пары вершины \\(y\\). Чингиз красит чёрным рёбра\n\\[\\varphi(x)\\varphi(y)\\quad\\text{и}\\quad x\\varphi(y).\\]\nЕсли одно из них уже чёрное, освободившийся ход он делает произвольно. Оба предписанных ребра свободны или уже чёрны. Действительно, если Белла раньше покрасила \\(\\varphi(x)\\varphi(y)\\), то ответ Чингиза на тот ход уже включал бы \\(xy\\). Если она раньше покрасила \\(x\\varphi(y)\\), ответ на тот ход также включал бы \\(xy\\). В обоих случаях нынешнее ребро \\(xy\\) не могло бы быть свободным перед ходом Беллы. Значит, стратегия легальна.\n\nПусть \\(C\\) — произвольная белая клика размера \\(r\\). Она содержит не более одной вершины из каждой пары, потому что рёбра начального паросочетания чёрные. Выберем в \\(C\\) вершину \\(x\\), пара которой является самой ранней среди пар, представленных в \\(C\\), и положим\n\\[C'=\\{\\varphi(v):v\\in C\\}\\cup\\{x\\}.\\]\nДокажем, что \\(C'\\) — чёрная клика. Для любых различных \\(u,v\\in C\\) ребро \\(uv\\) белое, поэтому ответ на ход, когда оно стало белым, сделал ребро \\(\\varphi(u)\\varphi(v)\\) чёрным. Следовательно, все вершины множества \\(\\{\\varphi(v):v\\in C\\}\\) попарно соединены чёрными рёбрами. Если \\(v\\in C\\setminus\\{x\\}\\), то пара \\(x\\) стоит раньше пары \\(v\\), и ответ на белое ребро \\(xv\\) сделал \\(x\\varphi(v)\\) чёрным. Наконец, \\(x\\varphi(x)\\) — ребро начального чёрного паросочетания. Поэтому \\(C'\\) является чёрной кликой размера \\(r+1\\).\n\nМы сопоставили каждой белой клике размера \\(r\\) чёрную клику размера \\(r+1\\). В частности, для наибольшей белой клики получаем \\(\\omega(B)\\ge\\omega(W)+1\\), так что Чингиз выигрывает.\n\nВ версии 1:3 Чингиз делает те же два предписанных хода. Третье разрешённое чёрное ребро он выбирает произвольно; оно не может испортить уже доказанное неравенство кликовых чисел. Поэтому это не отдельная задача, а дословное усиление той же стратегии.", "idea_ids": [ "idea-ordered-pair-copy" ], "standard_idea_ids": [], "definition_ids": [ "complete_graph", "matching", "clique" ], "status": "ai_checked" } ], "difficulty": { "main": "national_final_medium", "local_score": 5, "comment": "Начальное совершенное паросочетание превращает задачу в явную копирующую стратегию с двумя обязательными ответными рёбрами.", "status": "ai_checked" }, "tags": [ "coloring", "matching", "graph_symmetry", "invariant", "goal_strategy_game" ], "sources": [ { "source_id": "src-yumt-2025-grand-final-problem3-official", "role": "source_problem_for_variant", "status": "source_verified" }, { "source_id": "src-lktg-2026-project2-problems-ru", "role": "related_published_generalization", "status": "source_verified" } ], "editorial": { "created_by": "ai", "created_at": "2026-08-15", "review_status": "ai_checked", "public_ready": true, "relations_status": "deep_done", "graph_theory_duplicate_removed": true, "notes": [ "Это редакторские варианты исходной игры Беллы и Чингиза, а не официальные формулировки ЮМТ или ЛКТГ.", "Под начальным паросочетанием понимается совершенное паросочетание из n/2 чёрных рёбер.", "Версии 1:2 и 1:3 объединены, поскольку третье чёрное ребро не используется и решение полностью совпадает." ], "solution_classification": { "type": "ai_original", "label": "полное решение ИИ", "status": "ai_checked", "confidence": 0.97, "basis": "полное доказательство копирующей стратегии и независимая проверка малых случаев", "notes": "Одна стратегия доказывает более сильное утверждение для обеих квот: каждой белой клике размера r соответствует чёрная клика размера r+1.", "audit_source": "bella-chingiz-perfect-matching-high-reasoning-2026-08-15" } } }