{ "id": "lktg-2026-project2-problem13-bella-chingiz-complete-graph", "title": "Белла и Чингиз: сравнение белой и чёрной клик на полном графе", "kind": { "primary": "research_project_problem", "secondary": [ "graph_in_statement", "game", "open_subproblem", "published_generalization" ] }, "language": "ru", "authors": [ { "name": "?", "status": "needs_human_review" } ], "problem_profile": { "objects": [ "complete_graph", "edge_coloring", "clique", "paired_vertices", "black_and_white_cliques", "biased_edge_coloring_game" ], "methods": [ "explicit_strategy", "pairing_construction", "forest_invariant", "oriented_forest_source", "case_analysis", "strategy", "ramsey_type_game" ], "transformations": [ "white_clique_to_larger_black_clique", "vertices_to_opposite_pairs" ], "goal": [ "winning_strategy_for_bias_four", "winning_strategy_for_bias_three", "open_bias_two_case", "winning_strategy", "prove_or_disprove_universal_winning_strategy" ], "auxiliary_graph_type": [ "forest_on_vertex_pairs", "complete_graph" ], "invariants": [ "pair_edge_black", "opposite_of_white_edge_black", "early_blocks_form_forest" ], "keywords": [ "lktg_2026_project2_problem13", "bella_chingiz_complete_graph", "yumt_2025_grand_final_problem3_generalization", "open_part_13g", "paired_blocks", "yumt", "2025_grand_final_problem3", "yumt_2025", "southern_mathematical_tournament", "no_public_solution_found", "непросто_для_ИИ", "lktg_2026_project2_problem27", "erdos_conjecture", "open_problem", "bias_one_to_two" ], "status": "ai_checked" }, "statements": { "original": [ { "id": "stmt-original", "title": "Белла и Чингиз на полном графе", "text": "Пусть \\(n\\ge3\\) и \\(k\\ge1\\) — целые числа. Белла и Чингиз играют на полном графе \\(K_n\\); начинает Белла. В каждом раунде Белла красит одно свободное ребро белым. Если после этого свободные рёбра остались, Чингиз красит \\(k\\) из них чёрным, а если их меньше \\(k\\) — все оставшиеся. Игра заканчивается сразу после окраски последнего свободного ребра. Чингиз выигрывает тогда и только тогда, когда наибольшая чёрная клика строго больше наибольшей белой.\n\nа) Пусть \\(n>3\\) чётно и \\(k=4\\). Постройте явную выигрышную стратегию Чингиза.\n\nб) Пусть \\(n>3\\) чётно и \\(k=3\\). Постройте явную выигрышную стратегию Чингиза.\n\nв) Пусть \\(n>3\\) нечётно и \\(k=3\\). Постройте явную выигрышную стратегию Чингиза.\n\nг★) Докажите или опровергните: при \\(k=2\\) Чингиз имеет выигрышную стратегию для каждого чётного \\(n>3\\).\n\nПодпункт г) отмечен в официальном PDF как открытый. Официального решения для него нет, и настоящая карточка его не предлагает.", "source_id": "src-lktg-2026-project2-problems-ru", "status": "source_verified", "self_contained": { "status": "ai_checked" }, "definition_ids": [ "complete_graph", "clique", "tree" ] }, { "id": "stmt-yumt-2025-n-2024", "title": "Версия ЮМТ для \\(K_{2024}\\)", "text": "Белла и Чингиз играют на полном графе из 2024 вершин, делая ходы по очереди; начинает Белла.\nВ свой ход Чингиз красит \\(k\\) рёбер (или все оставшиеся) в чёрный цвет, Белла — одно в белый.\nИгра кончается, когда все рёбра будут покрашены.\nЕсли максимальная чёрная клика окажется строго больше максимальной белой, то выиграет Чингиз, иначе — Белла.\nПри каких \\(k\\ge 3\\) Чингиз имеет выигрышную стратегию?", "source_id": "src-yumt-2025-grand-final-problem3-official", "status": "source_verified", "self_contained": { "status": "ai_checked" }, "definition_ids": [ "complete_graph", "clique" ], "source_note": "Сверено с официальным PDF https://adygmath.ru/content/files/umt25/problems/final_usl_grand2.pdf: XX Южный математический турнир, финал, Гранд-лига, 27.09.2025, задача 3." }, { "id": "stmt-exact-erdos-conjecture", "title": "Точная открытая гипотеза для режима 1:2", "text": "Открытая задача. Белла и Чингиз играют на рёбрах \\(K_n\\). Белла ходит первой и каждый раз красит одно свободное ребро белым; после каждого её хода Чингиз красит два свободных ребра чёрным. После окраски всех рёбер Чингиз выигрывает, если \\(\\omega(B)>\\omega(W)\\), иначе выигрывает Белла. Докажите или опровергните: Чингиз имеет выигрышную стратегию для каждого \\(n\\ge4\\). Этот пункт отмечен в официальном PDF звездой как открытый; официальное решение не приводится.", "source_id": "src-lktg-2026-project2-problems-ru", "status": "source_verified", "self_contained": { "status": "ai_checked" }, "definition_ids": [ "complete_graph", "clique" ] } ], "graph_theory": [], "olympiad_reformulations": [] }, "ideas": [ { "id": "idea-opposite-pairs-and-forest", "title": "Противоположные пары и лес ранних блоков", "text": "Чингиз объединяет затронутые вершины в пары с чёрным внутренним ребром. Первые белые рёбра между ещё не готовыми парами образуют лес на множестве пар, а каждому белому ребру сопоставляется чёрное противоположное.", "tags": [ "construction", "process_invariant" ], "status": "ai_checked" }, { "id": "idea-white-clique-to-black-clique", "title": "Белая клика переходит в большую чёрную", "text": "Из белой клики выбирается не более одной вершины каждой пары. Противоположные вершины образуют чёрную клику, а лесной подсчёт или источник ориентированного леса даёт ещё одну чёрную вершину.", "tags": [ "goal_strategy_game", "trees" ], "status": "ai_checked" }, { "id": "idea-own-edge-quota-monotonicity", "title": "Монотонность выигрышной стратегии по собственной квоте", "text": "Стратегию для меньшей чёрной квоты разыгрывают на воображаемой доске. Лишние реальные чёрные рёбра считаются подарками и не могут ухудшить монотонную цель сравнения кликовых чисел.", "tags": [ "process_invariant", "goal_strategy_game" ], "status": "ai_checked" } ], "solutions": [ { "id": "sol-official-parts-a-c", "title": "Официальные стратегии для закрытых подпунктов а–в", "text": "Во всех частях через \\(\\bar v\\) будем обозначать вершину, поставленную Чингизом в пару с \\(v\\).\n\nа) Чётное \\(n\\), \\(k=4\\). Сначала все вершины считаются свободными. Чингиз постепенно создаёт непересекающиеся пары \\(\\{x,\\bar x\\}\\) с чёрным ребром \\(x\\bar x\\). Четыре ребра между двумя парами назовём блоком. Некоторые блоки отмечаются; отмеченные блоки образуют граф \\(F\\) на множестве пар.\n\nНа белое ребро \\(xy\\) Чингиз отвечает так.\n\n1. Если \\(x,y\\) свободны, он выбирает ещё две свободные вершины \\(\\bar x,\\bar y\\), красит чёрным \\(x\\bar x,y\\bar y,\\bar x\\bar y\\), создаёт пары \\(X=\\{x,\\bar x\\}\\), \\(Y=\\{y,\\bar y\\}\\) и отмечает блок \\(XY\\).\n\n2. Если \\(x\\) уже входит в пару \\(X\\), а \\(y\\) свободна, он выбирает свободную \\(\\bar y\\), красит \\(y\\bar y,x\\bar y,\\bar x\\bar y\\), создаёт пару \\(Y\\), отмечает блок и ориентирует ребро \\(X\\to Y\\).\n\n3. Если обе вершины уже имеют пары, он красит все ещё свободные рёбра их блока. В неотмеченном блоке таких рёбер не больше трёх, в отмеченном — не больше двух.\n\nВ первых двух правилах занято не больше трёх чёрных рёбер. Если после создания пар остаются ровно две свободные вершины, четвёртым ребром Чингиз красит ребро между ними и объявляет их парой. Поэтому перед каждым ходом Беллы свободных вершин либо нет, либо хотя бы четыре; первое правило всегда выполнимо. Неиспользованные чёрные ходы делаются произвольно.\n\nГраф \\(F\\) — лес: первое правило добавляет ребро между двумя новыми вершинами, второе подвешивает новую вершину к старой, а пара, созданная дополнительным четвёртым ходом, изолирована. После партии доориентируем \\(F\\). В блоке первого правила первое белое ребро равно \\(xy\\), а \\(\\bar x\\bar y\\) чёрное; из двух остальных рёбер белым может стать не больше одного, потому что после такого хода правило 3 закрасит другое. Если \\(x\\bar y\\) чёрное, ориентируем \\(X\\to Y\\), иначе \\(Y\\to X\\). Тогда для каждого ориентированного отмеченного блока выполнено\n\\[\nX\\to Y,\\quad p\\in X,\\ q\\in Y,\\ pq\\text{ белое}\\quad\\Longrightarrow\\quad p\\bar q\\text{ чёрное}. \\tag{1}\n\\]\nДля блока второго правила это верно сразу, поскольку оба нужных ребра были окрашены чёрным.\n\nЕсли к концу остались свободные вершины, белых рёбер с их концами нет: иначе они уже получили бы пары. Следовательно, все инцидентные им рёбра чёрные; разобьём их на пары и добавим как изолированные вершины \\(F\\).\n\nПусть \\(C\\) — наибольшая белая клика, \\(|C|=s\\ge2\\). Она содержит не больше одной вершины каждой пары. Множество \\(\\bar C\\) противоположных вершин является чёрной кликой. В неотмеченном блоке после первого белого ребра все остальные стали чёрными. В отмеченном блоке Чингиз сразу красит ребро, противоположное первому белому, а правило 3 красит ребро, противоположное возможному второму белому.\n\nРассмотрим ориентированный подлес \\(F\\) на парах, представленных в \\(C\\), и выберем его источник \\(X\\). Пусть \\(c\\in C\\cap X\\). Для любого \\(q\\in C\\) ребро \\(c\\bar q\\) чёрное: для соседних пар это следует из (1) и выбора источника, для несоседних блок не отмечен и после белого \\(cq\\) все другие его рёбра чёрные. Также \\(c\\bar c\\) чёрное. Поэтому \\(\\bar C\\cup\\{c\\}\\) — чёрная клика размера \\(s+1\\), и Чингиз выигрывает.\n\nб) Чётное \\(n\\), \\(k=3\\). Пусть \\(n=2m\\). Чингиз снова создаёт противоположные пары, делая внутреннее ребро каждой пары чёрным. Блок назовём ранним, если первое белое ребро в нём появилось до создания обеих пар. Пока есть хотя бы четыре безымянные вершины, ответы таковы.\n\n1. На белое \\(uv\\) между двумя безымянными вершинами выбираются \\(\\bar u,\\bar v\\), а чёрными становятся \\(u\\bar u,\\bar u\\bar v,v\\bar v\\).\n\n2. Если \\(u\\) уже имеет пару, а \\(v\\) безымянна, выбирается \\(\\bar v\\), а чёрными становятся \\(\\bar u\\bar v,v\\bar v\\).\n\n3. Если обе пары созданы, после белого \\(uv\\) Чингиз красит все свободные среди трёх остальных рёбер блока \\(u\\bar v,\\bar uv,\\bar u\\bar v\\). Если их меньше трёх, квота дополняется произвольными свободными рёбрами.\n\nЕсли после раунда остаются ровно две безымянные вершины \\(x,y\\), далее на белое \\(xv\\) Чингиз красит свободные из \\(x\\bar v,yv,y\\bar v\\), а на белое \\(yv\\) — свободные из \\(xv,x\\bar v,y\\bar v\\). На \\(xy\\) специального ответа не нужно; между уже спаренными вершинами действует правило 3.\n\nРанние блоки образуют лес: ход между двумя безымянными вершинами создаёт отдельное ребро между двумя новыми парами, а ход между именованной и безымянной подвешивает новую пару к старой. В нераннем блоке белым бывает не больше одного ребра. В раннем первое белое ребро имеет чёрное противоположное, а после следующего белого хода правило 3 красит всё оставшееся; поэтому белых рёбер там не больше двух, и при двух они имеют общий конец.\n\nПусть белая клика \\(C\\) состоит из \\(s\\) спаренных вершин. Она берёт не больше одной вершины каждой пары, а \\(\\bar C\\) — чёрная клика, поскольку противоположное каждому белому ребру чёрное. Белое ребро между \\(C\\) и \\(\\bar C\\) возможно только в раннем блоке, соответствующем двум парам из \\(C\\), и в каждом таком блоке оно не более одно. Лес на этих \\(s\\) парах имеет не больше \\(s-1\\) рёбер, значит между \\(C\\) и \\(\\bar C\\) не больше \\(s-1\\) белых рёбер. Поэтому найдётся \\(v\\in C\\), не имеющая белых соседей в \\(\\bar C\\), и \\(\\bar C\\cup\\{v\\}\\) — чёрная клика размера \\(s+1\\).\n\nЕсли наибольшая белая клика содержит \\(x\\), но не \\(y\\), запишем её как \\(C\\cup\\{x\\}\\). По специальному правилу \\(y\\) чёрно соединена со всей \\(\\bar C\\) и с найденной вершиной \\(v\\), поэтому \\(\\bar C\\cup\\{v,y\\}\\) на одну вершину больше белой клики. Случай с \\(y\\) симметричен. Ребро \\(xy\\) не входит в белый треугольник: для каждой третьей вершины специальный ответ делает одну из двух связей чёрной. Если наибольшая белая клика состоит из \\(x,y\\), то до появления остаточной пары в спаренной части уже было белое ребро, и предыдущий лесной аргумент для \\(s=2\\) даёт чёрный треугольник. Значит, Чингиз всегда имеет строго большую клику.\n\nв) Нечётное \\(n\\), \\(k=3\\). Сначала Чингиз действует как в пункте б), создавая пары. Этот этап прекращается либо когда остаются три безымянные вершины и Белла впервые затрагивает одну из них, либо когда остаются пять безымянных вершин и Белла берёт ребро между двумя из них. Спаренную часть обозначим через \\(L\\).\n\nСлучай 1. Остались \\(a,b,c\\), а первый новый белый ход равен \\(av_0\\), где \\(v_0\\in L\\). Чингиз красит чёрным треугольник \\(abc\\). Затем на белое \\(dv\\), где \\(d\\in\\{a,b,c\\}\\), \\(v\\in L\\), он красит все свободные из \\(a\\bar v,b\\bar v,c\\bar v\\); внутри \\(L\\) действует правило 3 пункта б). Для начального ребра \\(av_0\\), если оно встретилось бы в предписанном ответе, его просто пропускают. Белая клика содержит не больше одной из \\(a,b,c\\). Если она равна \\(C\\cup\\{d\\}\\), где \\(C\\subset L\\), \\(|C|=s\\), то\n\\[\n(\\bar C\\setminus\\{v_0,\\bar v_0\\})\\cup\\{a,b,c\\}\n\\]\n— чёрная клика размера не меньше \\(s+2\\), то есть строго больше. Для клики внутри \\(L\\) работает пункт б).\n\nСлучай 2. Остались \\(a,b,c\\), а первый белый ход — \\(ab\\). Чингиз красит \\(ac,bc\\). Далее на \\(av\\) он красит свободные из \\(bv,b\\bar v,c\\bar v\\); на \\(bv\\) — из \\(av,a\\bar v,c\\bar v\\); на \\(cv\\) — из \\(a\\bar v,b\\bar v,c\\bar v\\). Внутри \\(L\\) действует прежнее правило. Если белая клика равна \\(C\\cup\\{a\\}\\), то \\(\\bar C\\cup\\{b,c\\}\\) — чёрная клика на одну вершину больше; для \\(b\\) рассуждение симметрично, а для \\(c\\) подходит \\(\\bar C\\cup\\{a,c\\}\\). Белая клика не может содержать одновременно \\(a,b\\) и вершину \\(L\\), что следует из первого специального ответа. Само ребро \\(ab\\) также не опасно. При \\(n\\ge7\\) до появления трёх остаточных вершин был обычный спаривающий ход, и лесной аргумент с \\(s=2\\) даёт чёрный треугольник внутри \\(L\\); при \\(n=5\\) возникает следующий случай.\n\nСлучай 3. Остались пять вершин. Концы первого белого ребра назовём \\(x,y\\), остальные — \\(a,b,c\\). Чингиз красит чёрным треугольник \\(abc\\). Далее: на белое ребро из \\(a,b,c\\) к \\(v\\in L\\) он красит свободные \\(a\\bar v,b\\bar v,c\\bar v\\); на \\(xv\\) или \\(yv\\) — три остальных ребра между \\(\\{x,y\\}\\) и \\(\\{v,\\bar v\\}\\). Если, например, Белла красит \\(ax\\), Чингиз красит свободные из \\(ay,by,cy\\); если позднее Белла берёт \\(bx\\) или \\(cx\\), он красит оставшееся из этих двух рёбер. Остальные варианты получаются переименованием; внутри \\(L\\) действует старое правило.\n\nБелая клика с не более чем одной особой вершиной разбирается как в пункте б), причём чёрный треугольник даёт запас для \\(a,b,c\\). Ребро \\(xy\\) не входит в белый треугольник. Если белая клика содержит две особые вершины, то после переименования она имеет вид \\(C\\cup\\{a,x\\}\\), и \\(\\bar C\\cup\\{b,c,y\\}\\) является чёрной кликой на одну вершину больше.\n\nПроверим легальность специальных ответов. Правило 3 берёт только свободные рёбра, а в раннем блоке после второго белого хода всё остальное уже чёрное. Если требуемое ребро от особой вершины к \\(\\bar v\\) раньше стало белым, ответ на тот прежний ход уже сделал нынешнее ребро к \\(v\\) чёрным. Аналогично, если одно из \\(ay,by,cy\\) стало белым раньше, симметричный ответ уже сделал \\(ax\\) чёрным, так что ход \\(ax\\) не мог бы возникнуть. Следовательно, белое ребро перекрашивать не требуется; уже чёрные предписанные рёбра не входят в квоту, а недостающие ходы добираются произвольно. Все случаи исчерпаны, и при каждом нечётном \\(n>3\\) Чингиз выигрывает.\n\nПодпункт г) с \\(k=2\\) открыт и в официальный раздел решений не входит.", "idea_ids": [ "idea-opposite-pairs-and-forest", "idea-white-clique-to-black-clique" ], "source_id": "src-lktg-2026-project2-solutions-ru", "standard_idea_ids": [], "definition_ids": [ "complete_graph", "clique", "tree" ], "status": "ai_checked" }, { "id": "sol-ai-yumt-all-k-at-least-three", "title": "ИИ-дополнение: монотонность по числу чёрных рёбер за ход", "text": "Докажем общую лемму. Пусть при квоте \\(k_0\\) у Чингиза есть выигрышная стратегия, а условие его победы сохраняется при добавлении чёрных и удалении белых рёбер. Тогда та же сторона выигрывает при любой квоте \\(k\\ge k_0\\).\n\nЧингиз ведёт воображаемую партию с квотой \\(k_0\\). До окончания реальной партии он поддерживает два инварианта: каждое воображаемое чёрное ребро чёрно и в реальности, а множества белых рёбер в двух партиях совпадают. Поэтому каждый реальный белый ход можно повторить в воображаемой партии: выбранное ребро не является там ни чёрным, ни белым. Затем воображаемая стратегия называет не более \\(k_0\\) свободных рёбер. Чингиз объявляет их чёрными в воображаемой партии и красит в реальной те из них, которые там ещё свободны. Ребро, уже чёрное в реальной партии, было одним из прежних лишних ходов Чингиза, поэтому повторно красить его не нужно. Оставшуюся часть реальной квоты до \\(k\\) он добирает произвольными свободными рёбрами; воображаемая партия пока считает эти подарочные рёбра свободными. Оба инварианта восстановлены.\n\nКогда реальная доска заполнится, продолжим только воображаемую партию до конца: Белла произвольно красит оставшиеся воображаемо свободные рёбра белым, а Чингиз отвечает своей стратегией. Все эти оставшиеся рёбра в реальности уже чёрные. Поэтому для итоговых графов имеем \\(B_{\\rm imag}\\subseteq B_{\\rm real}\\) и \\(W_{\\rm real}\\subseteq W_{\\rm imag}\\). Воображаемая стратегия даёт \\(\\omega(B_{\\rm imag})>\\omega(W_{\\rm imag})\\), откуда тем более \\(\\omega(B_{\\rm real})>\\omega(W_{\\rm real})\\). Лемма доказана.\n\nВ задаче ЮМТ \\(n=2024\\). Официальная стратегия пункта б проектной формулировки выигрывает при \\(k_0=3\\). По лемме Чингиз выигрывает при каждом \\(k\\ge3\\). Следовательно, ответ ЮМТ: все целые \\(k\\ge3\\).", "idea_ids": [ "idea-own-edge-quota-monotonicity" ], "standard_idea_ids": [], "definition_ids": [ "complete_graph", "clique" ], "status": "ai_checked", "review_notes": "Это отдельное ИИ-дополнение к официальному решению закрытых подпунктов ЛКТГ; источник ЮМТ содержит только условие." } ], "difficulty": { "main": "national_final_hard", "local_score": 10, "comment": "Официальная сложность: а) 3/5; б) 4/5; в) 5/5; г) открытая.", "status": "source_verified" }, "tags": [ "coloring", "goal_strategy_game", "construction", "process_invariant", "trees", "extremal_graph_theory", "ramsey_theory", "goal_proof" ], "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-yumt-2025-grand-final-problem3-official", "role": "source_problem", "status": "source_verified", "statement_ids": [ "stmt-yumt-2025-n-2024" ] } ], "editorial": { "created_by": "ai", "created_at": "2026-08-15", "review_status": "ai_checked", "public_ready": true, "notes": [ "Фиксированная формулировка ЮМТ 2025 и параметрическое продолжение ЛКТГ 2026 объединены в одной карточке.", "Официальная стратегия ЛКТГ решает случай k=3; отдельная доказанная ИИ-лемма монотонности даёт ответ ЮМТ для всех k не меньше 3.", "Режим k=2 в параметрической формулировке остаётся официально открытым и не получил вымышленного решения.", "Точная гипотеза Эрдёша для режима 1:2 включена как открытая граничная формулировка той же игры, а не как отдельная карточка." ], "relations_status": "deep_done", "graph_theory_duplicate_removed": true, "solution_classification": { "type": "official_partial_with_open_subproblems", "label": "официальные полные решения закрытых подпунктов; пункт г открыт", "status": "ai_checked", "confidence": 0.94, "basis": "официальный PDF решений, русская редакция 7", "notes": "Официальные стратегии полностью покрывают закрытые подпункты а-в; ответ фиксированной версии ЮМТ для всех k не меньше 3 дополнен ИИ-леммой монотонности; режим k=2 остаётся открытым." }, "updated_at": "2026-08-15" } }