{ "id": "lktg-2026-project2-problem02-coins-on-graph", "title": "Монеты на графе: выигрышный старт на пути, дереве и цикле", "kind": { "primary": "problem", "secondary": [ "game", "weighted_graph" ] }, "language": "ru", "problem_profile": { "objects": [ "vertex_weighted_graph", "self_avoiding_token_game", "path", "tree", "cycle" ], "methods": [ "alternating_sum", "dynamic_programming_on_tree", "finite_descent", "counterexample_construction" ], "transformations": [ "rooted_branch_to_game_value", "winning_start_to_nonnegative_value" ], "goal": [ "find_nonlosing_start", "disprove_generalization" ], "auxiliary_graph_type": [ "directed_edge_state_tree" ], "invariants": [ "recursive_branch_value", "alternating_score_difference" ], "keywords": [ "coins_on_graph", "weighted_path_game", "tree_game_recursion", "seven_vertex_counterexample" ], "status": "ai_checked" }, "statements": { "original": [ { "id": "stmt-problem02", "title": "Игра с монетами и непосещёнными вершинами", "text": "В каждой вершине конечного связного графа \\(G\\) лежит неотрицательное целое число монет. Петя выбирает стартовую вершину, ставит туда фишку, объявляет вершину посещённой и забирает все монеты из неё. После этого первым передвигает фишку Вася. За ход нужно перейти по ребру в ещё не посещённую вершину и забрать из неё все монеты. Игра заканчивается, когда очередной игрок не может сделать ход. Побеждает набравший больше монет; при равенстве объявляется ничья.\n\nа) Пусть \\(G\\) является путём. Докажите, что Петя может выбрать стартовую вершину и затем играть так, чтобы не проиграть.\n\nб) Докажите то же, если \\(G\\) - произвольное конечное дерево.\n\nв) Докажите то же, если \\(G\\) - цикл.\n\nг) Верно ли это для произвольного конечного связного графа \\(G\\)?", "source_id": "src-lktg-2026-project2-problems-ru", "status": "source_verified", "self_contained": { "status": "ai_checked" }, "definition_ids": [ "connected_graph", "path", "tree", "cycle" ] } ] }, "ideas": [ { "id": "idea-path-alternating-sums", "title": "Первое отрицательное чередующееся слагаемое", "text": "На пути старт выбирается по знаку полной чередующейся суммы; если она отрицательна, берётся первый отрицательный префикс, чей индекс обязательно чётен.", "tags": [ "extremal_choice", "invariant" ], "status": "ai_checked" }, { "id": "idea-tree-recursion", "title": "Цена ориентированной ветви дерева", "text": "Для состояния \\(x\\mid y\\) цена удовлетворяет рекурсии \\(m(x\\mid y)=w(x)-\\max_{z\\sim x,\\ z\\ne y}m(z\\mid x)\\). Предположение, что хорошего старта нет, создаёт чередующийся бесконечный спуск по конечному дереву.", "tags": [ "trees", "minimal_counterexample" ], "status": "ai_checked" }, { "id": "idea-cycle-parity", "title": "Чередующиеся классы и нечётный цикл знаков", "text": "На чётном цикле Петя выбирает более тяжёлый из двух чередующихся классов; на нечётном используются соседние разности \\(D_i+D_{i+1}=2a_i\\ge0\\).", "tags": [ "parity_coloring", "invariant" ], "status": "ai_checked" }, { "id": "idea-seven-vertex-counterexample", "title": "Симметричный контрпример на семи вершинах", "text": "Вершина веса 2, три вершины веса 1 и треугольник из трёх нулевых вершин образуют граф, где Вася при любом старте получает вес 3, а Петя не более 2.", "tags": [ "construction", "goal_impossibility" ], "status": "ai_checked" } ], "solutions": [ { "id": "sol-problem02-complete", "title": "Полное решение пунктов а-г", "text": "Обозначим число монет в вершине \\(v\\) через \\(w(v)\\).\n\nа) Пусть вершины пути идут в порядке \\(v_1,\\ldots,v_n\\), а \\(a_i=w(v_i)\\). Положим \\(S_0=0\\) и \\(S_r=a_1-a_2+a_3-\\cdots+(-1)^{r-1}a_r\\). Если \\(S_n\\ge0\\), Петя начинает в \\(v_1\\). Дальнейший путь единственен, и разность его счёта и счёта Васи равна \\(S_n\\ge0\\). Пусть \\(S_n<0\\), а \\(r\\) - наименьший индекс, для которого \\(S_r<0\\). Тогда \\(S_{r-1}\\ge0\\), а \\(r\\) чётно: на нечётном шаге прибавляется неотрицательное число, поэтому впервые стать отрицательной сумма не может. Петя начинает в \\(v_r\\). После первого хода Васи фишка уже не может перейти через посещённую \\(v_r\\), поэтому идёт до одного из концов пути. Если Вася пошёл влево, итоговая разность равна \\(a_r-a_{r-1}+\\cdots-a_1=-S_r>0\\). Если он пошёл вправо, она равна \\(a_r-a_{r+1}+a_{r+2}-\\cdots=S_{r-1}-S_n>0\\). Значит, Петя не проигрывает.\n\nб) Для соседних вершин \\(x,y\\) удалим ребро \\(xy\\) и рассмотрим компоненту с \\(x\\). Обозначим через \\(m(x\\mid y)\\) наилучшую итоговую разность между монетами игрока, только что взявшего \\(x\\), и монетами его соперника, когда \\(y\\) уже недоступна, а следующим ходит соперник. В дереве все ранее посещённые вершины отделены от \\(x\\) ребром \\(xy\\), поэтому состояние определяется этой ориентированной ветвью. Имеем рекурсию\n\\[m(x\\mid y)=w(x)-\\max_{z\\sim x,\\ z\\ne y}m(z\\mid x),\\]\nгде максимум по пустому множеству равен нулю. Формула вычисляется от листьев и одновременно задаёт оптимальные стратегии. Если Петя начинает в \\(v\\), его гарантированная разность равна\n\\[w(v)-\\max_{u\\sim v}m(u\\mid v).\\]\nНазовём \\(v\\) хорошей, если это выражение неотрицательно.\n\nПредположим, что хороших вершин нет. Тогда для каждой \\(v\\) есть сосед \\(u\\), такой что \\(m(u\\mid v)>w(v)\\); скажем, что \\(u\\) угрожает \\(v\\). Если \\(u\\) угрожает \\(v\\), то из рекурсии следует \\(\\max_{x\\sim u,\\ x\\ne v}m(x\\mid u)0\\). Ребро \\(vv^*\\) назовём парным, остальные - поперечными. Если \\(uv\\) поперечное, то при вычислении \\(m(u\\mid v)\\) среди продолжений из \\(u\\) остаётся единственная угрожающая вершина \\(u^*\\), поэтому\n\\[m(u\\mid v)=w(u)-m(u^*\\mid u)=-d_u.\\]\nОпределим \\(h_v=0\\), если у \\(v\\) нет поперечных рёбер, и \\(h_v=\\min\\{d_u:uv\\text{ - поперечное ребро}\\}\\) иначе. Подставляя последнюю формулу в рекурсию для парного ребра, получаем \\(m(v\\mid v^*)=w(v)+h_v\\). Для обоих концов пары это даёт \\(d_v+d_{v^*}=h_v+h_{v^*}\\). Если \\(\\varepsilon_v=d_v-h_v\\), то \\(\\varepsilon_{v^*}=-\\varepsilon_v\\).\n\nВозьмём лист \\(a\\). Его единственное ребро парное, поэтому \\(h_a=0\\) и \\(\\varepsilon_a=d_a>0\\). Тогда \\(\\varepsilon_{a^*}<0\\), то есть \\(h_{a^*}>d_{a^*}\\). Следовательно, у \\(a^*\\) есть поперечный сосед \\(b\\), для которого \\(d_b=h_{a^*}>d_{a^*}\\). Так как \\(a^*b\\) поперечное, \\(h_b\\le d_{a^*}0\\). Переходим по парному ребру к \\(b^*\\) и повторяем рассуждение. Получается бесконечный маршрут, в котором парные и поперечные рёбра чередуются. Немедленно назад он не возвращается, а повтор вершины создал бы цикл. Это невозможно в конечном дереве. Значит, хорошая вершина существует; Петя начинает в ней и использует стратегию из рекурсии, гарантируя неотрицательную разность.\n\nв) Пусть веса на цикле равны \\(a_1,\\ldots,a_n\\). Если \\(n\\) чётно, разобьём вершины на два чередующихся класса. Петя выбирает вершину класса с не меньшей суммой весов. В какую бы сторону ни пошёл Вася, дальше цикл проходится в выбранном направлении, а Петя получает ровно выбранный класс, поэтому не проигрывает. Если \\(n\\) нечётно, индексы считаются по модулю \\(n\\). Пусть \\(D_i=a_i-a_{i+1}+a_{i+2}-\\cdots+a_{i+n-1}\\) - разность счёта при старте в \\(i\\) и движении по часовой стрелке. При движении против часовой стрелки получается \\(D_{i+1}\\), причём \\(D_i+D_{i+1}=2a_i\\ge0\\). Два соседних \\(D_i\\) не могут быть отрицательными одновременно. Более того, где-то два соседних значения одновременно неотрицательны: иначе знаки \"отрицательно\" и \"неотрицательно\" строго чередовались бы на нечётном цикле. Петя стартует в соответствующей вершине, и оба выбора направления Васи дают неотрицательную разность.\n\nг) Для общего связного графа ответ отрицателен. Построим граф на семи вершинах. Вершина \\(z\\) имеет вес 2; вершины \\(x_1,x_2,x_3\\) имеют вес 1; вершины \\(y_1,y_2,y_3\\) имеют вес 0. Вершина \\(z\\) соединена со всеми \\(x_i\\); вершина \\(x_i\\) соединена с \\(y_j\\) тогда и только тогда, когда \\(i\\ne j\\); вершины \\(y_1,y_2,y_3\\) образуют треугольник. Покажем стратегию Васи, где \\(i,j,k\\) - три различных индекса. Если Петя начал в \\(z\\), Вася идёт в любое \\(x_i\\); затем возможна последовательность \\(z,x_i,y_j,x_k,y_i,x_j\\), и Вася забирает все три единичные вершины. Если Петя начал в \\(x_i\\), Вася идёт в \\(z\\). После хода Пети в \\(x_j\\) Вася идёт в \\(y_k\\); какую бы из \\(y_i,y_j\\) ни выбрал Петя, Вася заканчивает в \\(x_k\\), получая веса \\(2+1\\). Если Петя начал в \\(y_i\\), Вася идёт в соседнюю \\(x_j\\). Если Петя затем идёт в \\(z\\), Вася идёт в \\(x_k\\), после чего ходы вынуждены: \\(y_j,x_i\\). Если Петя идёт в \\(y_k\\), Вася идёт в \\(x_i\\); затем Петя может пойти лишь в \\(z\\) или \\(y_j\\), и в обоих случаях Вася идёт в \\(x_k\\). Во всех ветвях Вася получает 3 монеты, а Петя может получить положительные вершины суммарного веса не более 2. Следовательно, Петя всегда проигрывает на этом связном графе.", "idea_ids": [ "idea-path-alternating-sums", "idea-tree-recursion", "idea-cycle-parity", "idea-seven-vertex-counterexample" ], "standard_idea_ids": [ "extremal_choice", "invariant" ], "status": "ai_checked", "definition_ids": [ "connected_graph", "path", "tree", "cycle" ], "source_id": "src-lktg-2026-project2-solutions-ru" } ], "difficulty": { "main": "national_final_medium", "local_score": 8, "comment": "Официальная шкала проекта: а) 2/5, б) 4/5, в) 2/5, г) 3/5. Главная трудность - доказательство существования хорошего старта на дереве через рекурсию и конечный спуск.", "status": "source_verified" }, "tags": [ "trees", "invariant", "extremal_choice", "construction", "goal_strategy_game", "goal_impossibility" ], "sources": [ { "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": "Официальные условия, задача 2", "statement_ids": [ "stmt-problem02" ], "note": "PDF называет исходную постановку предложением соавтора, а пункты в, г - составительскими; имя соавтора не указано." }, { "source_id": "src-lktg-2026-project2-solutions-ru", "role": "official_complete_solution", "status": "source_verified", "title": "Официальные решения, задача 2" } ], "editorial": { "created_by": "ai", "created_at": "2026-08-15", "review_status": "ai_checked", "public_ready": true, "graph_theory_duplicate_removed": true, "notes": [ "Исходное условие уже графовое; отдельная эквивалентная формулировка не нужна.", "Контрпример пункта г описан комбинаторно, поэтому решение не зависит от рисунка в PDF.", "Неизвестный по PDF соавтор не назван." ], "relations_status": "deep_done", "solution_classification": { "type": "official_complete_or_near_complete", "label": "официальное полное решение", "status": "ai_checked", "confidence": 0.97, "basis": "Официальный PDF решений содержит полные доказательства всех четырёх пунктов, включая рекурсию на дереве и явный контрпример.", "notes": "Скрытая в рисунке структура контрпримера полностью перенесена в текст." } } }