{ "id": "lktg-2026-project2-problem11-symmetric-erdos-game", "title": "Симметричная игра Эрдёша по кликовым числам, ЛКТГ 2026", "kind": { "primary": "research_project_problem", "secondary": [ "graph_in_statement", "game", "open_subproblems" ] }, "language": "ru", "authors": [], "problem_profile": { "objects": [ "complete_graph", "edge_coloring", "clique_number", "arbitrary_finite_board" ], "methods": [ "strategy_stealing", "color_swap", "imaginary_edges", "pairing_strategy", "ramsey_bound" ], "transformations": [ "swap_player_roles_and_colors", "reduce_to_induced_complete_subgraph" ], "goal": [ "compare_clique_numbers", "transfer_winning_strategy", "open_classification" ], "auxiliary_graph_type": [], "invariants": [ "one_extra_edge_changes_clique_number_by_at_most_one", "paired_edges_at_special_vertices" ], "keywords": [ "lktg_2026_project2_problem11", "symmetric_erdos_game", "open_parts_11zh_11z", "malekshahian_spiro_2026", "cambie_provoost_2025" ], "status": "ai_checked" }, "statements": { "original": [ { "id": "stmt-original", "title": "Симметричная игра Эрдёша", "text": "Пусть \\(n\\ge 3\\). На рёбрах \\(K_n\\) Красный и Синий по очереди выбирают по одному свободному ребру и красят его в свой цвет; начинает Красный. После окраски всех рёбер Красный выигрывает, если его наибольшая клика строго больше синей; при равенстве или меньшем размере выигрывает Синий. Обозначим графы красных и синих рёбер через \\(R\\) и \\(B\\).\n\nа) Докажите, что Красный всегда может гарантировать \\(\\omega(R)\\ge\\omega(B)\\).\n\nб) Докажите, что Синий всегда может гарантировать \\(\\omega(R)\\le\\omega(B)+1\\).\n\nв) Пусть вместо полного графа доской служит произвольный конечный граф \\(G\\) хотя бы с одним ребром. Докажите те же две гарантии. В частности, при правильной игре разность кликовых чисел равна 0 или 1.\n\nг) Предположим, что на \\(K_n\\) Красный может гарантировать строгую победу. Докажите, что на \\(K_{n+1}\\) Синий имеет выигрышную стратегию.\n\nд) При том же предположении докажите, что на \\(K_{n+2}\\) Синий имеет выигрышную стратегию.\n\nе) Пусть \\(n>100\\), и предположим, что на \\(K_n\\) Красный может гарантировать строгую победу. Докажите, что на \\(K_{n+3}\\) Синий имеет выигрышную стратегию.\n\nж★) Докажите или опровергните: существует натуральное \\(N\\), такое что для каждого \\(n\\ge N\\), если на \\(K_n\\) Красный может гарантировать строгую победу, то на \\(K_{n+4}\\) Синий имеет выигрышную стратегию.\n\nз★) Докажите или опровергните: для каждого \\(n\\ge 3\\) при правильной игре выигрывает Синий.\n\nПодпункты ж) и з) отмечены в официальном PDF звёздочкой как открытые. Решения для них в официальном сборнике нет; настоящая карточка не утверждает, что они решены.", "source_id": "src-lktg-2026-project2-problems-ru", "status": "source_verified", "self_contained": { "status": "ai_checked" }, "definition_ids": [ "simple_graph", "complete_graph", "clique", "ramsey_number" ] } ], "graph_theory": [], "olympiad_reformulations": [] }, "ideas": [ { "id": "idea-color-swapped-strategy", "title": "Кража стратегии с перестановкой цветов", "text": "Первый игрок после произвольного начального ребра может мысленно стать вторым игроком в партии с переставленными цветами. Цена лишнего ребра контролируется тем, что добавление или удаление одного ребра меняет кликовое число не более чем на единицу.", "tags": [ "graph_symmetry", "goal_strategy_game" ], "status": "ai_checked" }, { "id": "idea-special-vertex-pairing", "title": "Спаривание рёбер у добавленных вершин", "text": "При переходах к \\(K_{n+1}\\), \\(K_{n+2}\\) и \\(K_{n+3}\\) Синий изолирует чистую копию \\(K_n\\), играет там выигрышную стратегию первого игрока и попарно отвечает на рёбра, инцидентные новым вершинам, ограничивая прирост красной клики.", "tags": [ "goal_strategy_game", "graph_symmetry" ], "status": "ai_checked" } ], "solutions": [ { "id": "sol-official-parts-a-e", "title": "Решение закрытых подпунктов а–е", "text": "Будем пользоваться приёмом воображаемых рёбер. Если стратегия выигрывает даже после того, как несколько свободных рёбер заранее отданы противнику, то она выигрывает и в исходной игре: реальный ход противника по подаренному ребру считается пропуском в воображаемой партии, а освободившийся собственный ход можно сделать где угодно. Дополнительное ребро своего цвета не уменьшает собственную клику и не увеличивает клику соперника.\n\nа) Предположим, что Синий умеет при любой игре Красного обеспечить \\(\\omega(B)>\\omega(R)\\). Красный первым ходом красит произвольное ребро \\(e\\), затем меняет названия цветов и применяет эту же стратегию как второй игрок. В воображаемой партии настоящие синие рёбра играют роль рёбер первого игрока, а красные рёбра, кроме \\(e\\), — второго. Стратегия тогда обещает \\(\\omega(R-e)>\\omega(B)\\). Ребро \\(e\\) может лишь увеличить красное кликовое число, поэтому та же стратегия обещала бы победу обеим сторонам, что невозможно. Значит, Красный гарантирует \\(\\omega(R)\\ge\\omega(B)\\).\n\nб) Конечность дерева игры означает: либо Синий может обеспечить \\(\\omega(R)\\le\\omega(B)+1\\), либо Красный может обеспечить \\(\\omega(R)\\ge\\omega(B)+2\\). Допустим второе и обозначим предполагаемую стратегию Красного через \\(S\\), а её первый ход через \\(f\\). Пусть настоящий первый ход Красного — \\(e\\). Синий будет разыгрывать \\(S\\) с переставленными цветами.\n\nЕсли \\(e\\ne f\\), Синий красит \\(f\\) и далее буквально следует \\(S\\). Тогда стратегия, применённая к синим рёбрам и красным рёбрам без \\(e\\), дала бы\n\\[\n\\omega(B)\\ge\\omega(R-e)+2\\ge\\omega(R)+1,\n\\]\nпоскольку удаление одного ребра уменьшает кликовое число не более чем на один. Это несовместимо с обещанием \\(\\omega(R)\\ge\\omega(B)+2\\).\n\nЕсли \\(e=f\\), Синий делает произвольный свободный ход \\(g\\), не учитывает его и затем считает \\(e\\) первым синим ребром воображаемой партии. Настоящие красные ходы со второго играют роль ходов соперника стратегии, а настоящие синие ходы со второго — её ответов. Поэтому\n\\[\n\\omega((B-g)+e)\\ge\\omega(R-e)+2.\n\\]\nДобавление одного ребра увеличивает кликовое число не более чем на один, а удаление одного уменьшает не более чем на один. Левая часть не превосходит \\(\\omega(B)+1\\), правая не меньше \\(\\omega(R)+1\\), откуда \\(\\omega(B)\\ge\\omega(R)\\), снова противоречие. Если после \\(e\\) свободно не более одного ребра, нужная оценка очевидна, так что нехватки хода \\(g\\) нет. Следовательно, Синий гарантирует \\(\\omega(R)\\le\\omega(B)+1\\).\n\nв) В двух предыдущих доказательствах использовались только конечность игры и факт, что одно ребро меняет кликовое число не более чем на один. Поэтому они без изменений работают на любой конечной доске \\(G\\) хотя бы с одним ребром. Красный гарантирует разность не меньше нуля, Синий — не больше единицы; при правильной игре она равна 0 или 1.\n\nг) Пусть первый красный ход на \\(K_{n+1}\\) — \\(uv\\). Мысленно подарим Красному все остальные рёбра из \\(v\\). На остальных \\(n\\) вершинах остаётся чистая доска \\(K_n\\), и первым на ней ходит Синий. Он применяет выигрышную стратегию первого игрока, существующую по предположению. Красные ходы вне этой доски считаются пропусками; после заполнения внутренней доски Синий берёт любое свободное ребро. Если внутри \\(K_n\\) красное и синее кликовые числа равны \\(r\\) и \\(b\\), то \\(b\\ge r+1\\). В полном графе красная клика может дополнительно использовать универсальную красную вершину \\(v\\), синяя — нет. Поэтому \\(\\omega(R)=r+1\\le b=\\omega(B)\\), и по правилу задачи выигрывает Синий.\n\nд) Пусть Красный начал ребром \\(xy\\), а \\(H=K_{n+2}-\\{x,y\\}\\cong K_n\\). Первым ходом Синий начинает на \\(H\\) выигрышную стратегию первого игрока. На красный ход внутри \\(H\\) он отвечает по этой стратегии; на ход \\(xz\\), где \\(z\\in H\\), отвечает \\(yz\\), и наоборот. Ответ свободен, потому что два ребра пары \\(\\{xz,yz\\}\\) до этого могли окрашиваться только вместе. Лишний или уже не требующийся внутренний ответ заменяется произвольным свободным ходом, что корректно по приёму воображаемых рёбер. Внутри \\(H\\) получаем \\(b\\ge r+1\\). Красная клика размера хотя бы три не содержит одновременно \\(x\\) и \\(y\\): для любой третьей вершины одно из рёбер к ним синее. Значит, \\(\\omega(R)\\le r+1\\le b\\le\\omega(B)\\), и Синий выигрывает.\n\nе) Зафиксируем выигрышную стратегию \\(S\\) первого игрока на \\(K_n\\). Сначала опишем целевую позицию. Вершины разбиты на \\(H\\cong K_n\\) и особые \\(u,v_1,v_2\\). Внутри \\(H\\) Синий играет первым по \\(S\\) и имеет на один ход больше Красного; все рёбра из \\(u\\) в \\(H\\) красные, а \\(uv_1,uv_2\\) синие; ребро \\(v_1v_2\\) красное; общие красные соседи \\(v_1,v_2\\) в \\(H\\) лежат в множестве \\(T\\), где \\(|T|\\le3\\).\n\nИз этой позиции на красный ход внутри \\(H\\) Синий отвечает по \\(S\\), а на \\(v_1w\\) отвечает \\(v_2w\\) и наоборот; подаренные Красному рёбра учитываются как выше. Если внутренние кликовые числа равны \\(r,b\\), то \\(b\\ge r+1\\). Красная клика с не более чем одной особой вершиной имеет размер не больше \\(r+1\\). Клика с двумя особыми вершинами не содержит \\(u\\) вместе с \\(v_1\\) или \\(v_2\\), поэтому может состоять лишь из \\(v_1,v_2\\) и не более трёх их общих красных соседей. Следовательно,\n\\[\n\\omega(R)\\le\\max\\{r+1,5\\}.\n\\]\nДокажем нужную рамсеевскую оценку: в любой двухцветной раскраске \\(K_{70}\\) есть одноцветный \\(K_5\\). Вообще, среди \\(\\binom{a+b-2}{a-1}\\) вершин есть красный \\(K_a\\) или синий \\(K_b\\). Индукция по \\(a+b\\): у выбранной вершины либо не меньше \\(\\binom{a+b-3}{a-2}\\) соседей одного цвета, либо не меньше \\(\\binom{a+b-3}{a-1}\\) другого; применяем индукцию к соответствующему множеству соседей и добавляем выбранную вершину, когда цвет совпадает. Для \\(a=b=5\\) получаем \\(\\binom84=70\\). Так как \\(n>100\\), внутри \\(H\\) есть одноцветный \\(K_5\\). Если он синий, то \\(b\\ge5\\); если красный, то \\(r\\ge5\\), а значит \\(b\\ge r+1\\ge6\\). В любом случае \\(b\\ge5\\), и предыдущая оценка даёт \\(\\omega(R)\\le\\omega(B)\\).\n\nОсталось получить целевую позицию. Пусть первое красное ребро имеет конец \\(x\\). Синий красит \\(xy\\) с новым концом \\(y\\). После второго красного хода выберем вершину \\(z\\), не соединённую красным ни с \\(x\\), ни с \\(y\\), причём если уже есть красное ребро вне \\(\\{x,y\\}\\), возьмём подходящий его конец; таких рёбер пока не более одного, поэтому выбор возможен. Тогда внутри \\(H=K_{n+3}-\\{x,y,z\\}\\) окрашенных рёбер нет. Синий начинает там стратегию \\(S\\) и отвечает ею, пока Красный впервые не возьмёт ребро вне \\(H\\). После такого хода Синий берёт свободное ребро из \\(\\{xz,yz\\}\\), отличное от только что взятого. До этого оба были свободны, поэтому ход возможен. Вершину из \\(x,y\\), имеющую теперь две синие связи с остальными особыми вершинами, назовём \\(u\\), две другие — \\(v_1,v_2\\). Если Красный только что взял последнее ребро \\(H\\), Синий сразу делает тот же внешний ход; целевая позиция всё равно получена.\n\nК этому моменту Красный сделал не более трёх рёбер вне \\(H\\), поэтому все уже возникшие общие красные соседи \\(v_1,v_2\\) в \\(H\\) входят в некоторое \\(T\\) размера не более трёх. Мысленно подарим Красному недостающие рёбра из \\(u\\) в \\(H\\), оба ребра из каждой вершины \\(T\\) к \\(v_1,v_2\\) и ребро \\(v_1v_2\\). Ни одно из них не синее. Получена целевая позиция, которая, как доказано выше, выигрышна для Синего.\n\nПодпункты ж) и з) являются открытыми и в официальный раздел решений не входят.", "idea_ids": [ "idea-color-swapped-strategy", "idea-special-vertex-pairing" ], "source_id": "src-lktg-2026-project2-solutions-ru", "standard_idea_ids": [], "definition_ids": [ "simple_graph", "complete_graph", "clique", "ramsey_number" ], "status": "ai_checked" } ], "difficulty": { "main": "national_final_hard", "local_score": 10, "comment": "Официальная шкала по подпунктам: а–в — 2/5, г–д — 3/5, е — 5/5; ж и з — открытые.", "status": "source_verified" }, "tags": [ "coloring", "graph_symmetry", "goal_strategy_game" ], "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_solutions_for_closed_parts", "status": "source_verified" }, { "source_id": "src-malekshahian-spiro-clique-building-game", "role": "related_primary_paper", "status": "source_verified" } ], "editorial": { "created_by": "ai", "created_at": "2026-08-15", "review_status": "ai_checked", "public_ready": true, "notes": [ "Условие сверено со страницей 4 официального PDF; решения закрытых подпунктов а–е — со страницами 17–20 PDF решений.", "Подпункты 11ж и 11з входят в число пяти открытых пунктов проекта. Для них не создано ни решения, ни предположительного наброска.", "В строке источника PDF перечислены Erdős, Malekshahian–Spiro (2026) и Cambie–Provoost (2025), но автор конкретной проектной задачи не указан; authors оставлен пустым.", "Рамсеевская оценка, используемая в пункте е, доказана внутри решения, поэтому внешняя теорема не оставлена чёрным ящиком." ], "relations_status": "deep_done", "graph_theory_duplicate_removed": true, "solution_classification": { "type": "official_partial_with_open_subproblems", "label": "официальные полные решения закрытых подпунктов; два пункта открыты", "status": "ai_checked", "confidence": 0.96, "basis": "официальный PDF решений, русская редакция 7", "notes": "Закрытые подпункты а–е перенесены полностью; ж и з честно сохранены без решения как открытые." } } }