{ "id": "lktg-2026-project2-problem16-biconnected-red-board", "title": "Двусвязная доска произвольного размера для победы Красного, ЛКТГ 2026", "kind": { "primary": "olympiad_problem", "secondary": [ "graph_in_statement", "game", "construction" ] }, "language": "ru", "authors": [], "problem_profile": { "objects": [ "biconnected_graph", "book_of_k4_pages", "edge_coloring", "clique" ], "methods": [ "explicit_construction", "pairing_strategy", "local_defense", "target_page" ], "transformations": [ "large_board_to_pages_sharing_an_edge" ], "goal": [ "construct_arbitrarily_large_board", "first_player_winning_strategy" ], "auxiliary_graph_type": [], "invariants": [ "every_triangle_lies_in_one_page", "no_blue_triangle", "red_triangle_in_target_page" ], "keywords": [ "lktg_2026_project2_problem16", "biconnected_red_board", "k4_book", "malekshahian_spiro_2026" ], "status": "ai_checked" }, "statements": { "original": [ { "id": "stmt-original", "title": "Двусвязная доска для Красного", "text": "Красный и Синий по очереди красят свободные рёбра заранее выбранного конечного графа \\(H\\), начинает Красный. После окраски всех рёбер Красный выигрывает, если его наибольшая клика строго больше синей; иначе выигрывает Синий.\n\nДля каждого натурального \\(M\\) постройте двусвязный граф \\(H\\) хотя бы на \\(M\\) вершинах, на котором Красный имеет выигрышную стратегию. Здесь двусвязность означает, что граф связен и остаётся связным после удаления любой одной вершины.", "source_id": "src-lktg-2026-project2-problems-ru", "status": "source_verified", "self_contained": { "status": "ai_checked" }, "definition_ids": [ "simple_graph", "connected_graph", "complete_graph", "clique", "triangle" ] } ], "graph_theory": [], "olympiad_reformulations": [] }, "ideas": [ { "id": "idea-k4-book-board", "title": "Книга из страниц \\(K_4\\)", "text": "Все страницы \\(K_4\\) имеют общее ребро \\(uv\\). Граф остаётся связным после удаления любой вершины, а всякий треугольник целиком лежит в одной странице.", "tags": [ "goal_construction", "connectivity" ], "status": "ai_checked" }, { "id": "idea-local-pairing-defense", "title": "Локальные пары против синих треугольников", "text": "Красный защищает каждую затронутую страницу отдельным правилом парных ответов, а свободные ходы направляет в целевую страницу, где гарантированно собирает красный треугольник.", "tags": [ "goal_strategy_game", "coloring" ], "status": "ai_checked" } ], "solutions": [ { "id": "sol-official-k4-book", "title": "Книга из \\(K_4\\) и локальная стратегия Красного", "text": "Для \\(t\\ge2\\) построим граф \\(H_t\\) из \\(t\\) копий \\(K_4\\), имеющих ровно одно общее ребро \\(uv\\). В \\(i\\)-й копии две остальные вершины обозначим \\(a_i,b_i\\), а копию назовём страницей \\(C_i\\). Возьмём\n\\[\nt\\ge\\max\\left\\{2,\\left\\lceil\\frac{M-2}{2}\\right\\rceil\\right\\}.\n\\]\nТогда \\(|V(H_t)|=2+2t\\ge M\\).\n\nПроверим двусвязность. После удаления \\(u\\) вершина \\(v\\) соединяет все оставшиеся вершины; после удаления \\(v\\) ту же роль играет \\(u\\). После удаления одной из \\(a_i,b_i\\) общее ребро \\(uv\\) продолжает связывать все страницы. Значит, удаление любой вершины оставляет граф связным.\n\nТеперь стратегия. Первым ходом Красный красит \\(uv\\). Первый синий ход лежит в некоторой странице; назовём её \\(C_2\\). Красный выбирает другую, ещё не затронутую страницу \\(C_1\\), и вторым ходом красит противоположное ребро \\(a_1b_1\\).\n\nОпишем локальные ответы. В странице \\(C_2\\) уже есть первое синее ребро \\(e\\). Если \\(e=a_2b_2\\), Красный объявляет парами \\(\\{ua_2,ub_2\\}\\) и \\(\\{va_2,vb_2\\}\\). Если, например, \\(e=ua_2\\), пары равны \\(\\{a_2b_2,ub_2\\}\\) и \\(\\{va_2,vb_2\\}\\); остальные случаи симметричны. На синий ход в паре Красный, если нужно, берёт второе ребро пары.\n\nПусть Синий впервые входит в новую страницу \\(C_i\\). Если он красит \\(a_ib_i\\), Красный красит \\(ua_i\\), а рёбра \\(va_i,vb_i\\) объявляет парой и отвечает одним на другое. Если первый синий ход — луч, например \\(ua_i\\), Красный сразу красит \\(a_ib_i\\). После этого синий треугольник в странице невозможен. Все варианты получаются переименованием.\n\nОбязательный локальный ответ имеет приоритет. Если его нет, Красный работает в целевой странице \\(C_1\\). Её четыре луча разбиты на пары противоположных рёбер\n\\[\nP=\\{ua_1,vb_1\\},\\qquad Q=\\{ub_1,va_1\\}.\n\\]\nКрасный берёт свободное ребро из той пары, из которой у него ещё нет ребра. Когда обе пары представлены, свободным ходом можно красить, например, \\(a_ib_i\\) в нетронутой странице, сразу делая её безопасной для Синего.\n\nКрасный обязательно получит ребро из каждой пары \\(P,Q\\). Если Синий первым входит в такую пару, локального ответа в \\(C_1\\) нет и Красный сразу берёт другое её ребро. Если Синий избегает \\(C_1\\), то конечное число рёбер остальных страниц в конце концов исчерпается и ему придётся войти в \\(C_1\\). Любые два красных ребра, по одному из \\(P,Q\\), имеют общий конец; вместе с одним из уже красных противоположных рёбер \\(uv,a_1b_1\\) они образуют красный треугольник.\n\nОстаётся доказать, что синего треугольника нет. Всякий треугольник \\(H_t\\) целиком лежит в одной странице, поскольку вершины разных страниц, кроме \\(u,v\\), не смежны. В \\(C_1\\) оба противоположных ребра \\(uv,a_1b_1\\) красные. В \\(C_2\\) каждый возможный синий треугольник требует обоих рёбер одной из объявленных пар. В новой странице после первого синего луча ребро \\(a_ib_i\\) красное; после первого синего \\(a_ib_i\\) треугольник через \\(u\\) закрыт красным \\(ua_i\\), а треугольник через \\(v\\) требует оба ребра пары \\(\\{va_i,vb_i\\}\\). Треугольник через общее ребро \\(uv\\) невозможен, потому что оно красное. Таким образом, \\(\\omega(R)\\ge3\\), а \\(\\omega(B)\\le2\\), и Красный строго выигрывает.", "idea_ids": [ "idea-k4-book-board", "idea-local-pairing-defense" ], "source_id": "src-lktg-2026-project2-solutions-ru", "standard_idea_ids": [], "definition_ids": [ "simple_graph", "connected_graph", "complete_graph", "clique", "triangle" ], "status": "ai_checked" } ], "difficulty": { "main": "national_final_hard", "local_score": 8, "comment": "В официальном PDF проекта указана сложность 4/5.", "status": "source_verified" }, "tags": [ "coloring", "goal_construction", "goal_strategy_game", "connectivity" ], "sources": [ { "source_id": "src-lktg-2026-project2-page", "role": "official_project_page", "status": "source_verified" }, { "source_id": "src-lktg-2026-project2-problems-ru", "role": "official_problem_statement", "status": "source_verified" }, { "source_id": "src-lktg-2026-project2-solutions-ru", "role": "official_solution", "status": "source_verified" }, { "source_id": "src-malekshahian-spiro-clique-building-game", "role": "primary_source_named_by_project", "status": "source_verified" } ], "editorial": { "created_by": "ai", "created_at": "2026-08-15", "review_status": "ai_checked", "public_ready": true, "notes": [ "Условие сверено со страницей 6 официального PDF; решение — со страницами 31–32 PDF решений.", "PDF указывает источник «Malekshahian–Spiro, 2026», но не называет автора проектной задачи, поэтому authors оставлен пустым.", "Текст не зависит от рисунка: строение страниц, пары ответов и проверка каждого типа синего треугольника описаны явно." ], "relations_status": "deep_done", "graph_theory_duplicate_removed": true, "solution_classification": { "type": "official_complete_or_near_complete", "label": "официальное полное решение", "status": "ai_checked", "confidence": 0.97, "basis": "официальный PDF решений, русская редакция 7", "notes": "Конструкция, двусвязность и полная локальная стратегия перенесены самодостаточно." } } }