{ "id": "yumt-2017-start-first-round1-problem3", "title": "Петя разрушает дороги, Вася ведёт фишку, ЮМТ 2017", "kind": { "primary": "olympiad_problem", "secondary": [ "graph_in_statement", "application" ] }, "language": "ru", "authors": [ { "name": "?", "status": "needs_human_review" } ], "problem_profile": { "objects": [ "connected_simple_graph", "marked_vertices", "edge_deletion_game", "target_vertex_game" ], "methods": [ "complete_graph_minus_edge_construction", "invariant_after_each_deletion", "extremal_edge_counting" ], "transformations": [], "goal": [ "find_maximum_number_of_edges_for_winning_strategy" ], "auxiliary_graph_type": [], "invariants": [ "current_vertex_is_not_adjacent_to_target_after_petya_move" ], "keywords": [ "yumt", "2017_start_first_round1_problem3", "yumt_2017" ], "status": "ai_checked" }, "statements": { "original": [ { "id": "stmt-original", "title": "Оригинальная формулировка", "text": "Дано натуральное число n > 10. Министры Петя и Вася играют в игру.\nУ них есть карта с n городами. В начале Петя соединяет их k ≥ n дорогами так, чтобы от любого города по дорогам можно было доехать до любого другого. Любые два города можно соединить не более чем одной дорогой.\nЗатем Петя отмечает два города A и B и помещает в город A фишку.\nДалее игроки ходят по очереди, начиная с Васи: каждым своим ходом Вася перемещает фишку в город, куда от текущего положения фишки можно пройти по одной имеющейся дороге. Петя же своим ходом разрушает одну дорогу.\nЕсли Вася в некоторый момент оказывается в городе B, то он побеждает. Иначе, то есть если Вася не может добиться попадания в B до остановки игры, выигрывает Петя.\nПри каком наибольшем k Петя может выиграть, как бы ни играл Вася?", "source_id": "src-yumt-2017-start-first-round1-problem3-official", "status": "ai_checked", "self_contained": { "status": "ai_checked" }, "definition_ids": [] } ], "graph_theory": [], "olympiad_reformulations": [] }, "ideas": [ { "id": "idea-complete-graph-minus-target-edge", "title": "Полный граф без ребра между стартом и целью", "text": "Полный граф сразу проигрышен для Пети: какие бы A и B он ни выбрал, Вася первым ходом переходит по ребру AB. Но если взять полный граф без одного ребра AB и выбрать его концы стартом и целью, Петя после каждого хода Васи удаляет ребро из текущего города фишки в B. Тогда перед каждым ходом Васи фишка стоит в городе, не смежном с B.", "tags": [ "construction", "goal_strategy_game", "invariant" ], "status": "ai_checked" } ], "solutions": [ { "id": "sol-ai-complete-minus-edge-invariant", "title": "ИИ-решение: полный граф без одного ребра и инвариант", "text": "Ответ: \\(\\binom n2-1\\).\n\nСначала получим верхнюю оценку. В простом графе на \\(n\\) вершинах не больше \\(\\binom n2\\) рёбер. Если \\(k=\\binom n2\\), граф полный. Тогда какие бы два города \\(A\\) и \\(B\\) Петя ни отметил, они соединены дорогой, и Вася первым же ходом переводит фишку из \\(A\\) в \\(B\\). Значит при полном графе Петя выиграть не может, поэтому \\(k\\le \\binom n2-1\\).\n\nПокажем, что \\(\\binom n2-1\\) достижимо. Петя строит полный граф на всех \\(n\\) городах, но не проводит одно ребро \\(AB\\). Такой граф связен при \\(n>2\\), в частности при данном \\(n>10\\), а число дорог равно \\(\\binom n2-1\\). Затем Петя отмечает именно эти города \\(A\\) и \\(B\\), фишка стоит в \\(A\\).\n\nСтратегия Пети такова. После каждого хода Васи, если текущий город фишки соединён дорогой с \\(B\\), Петя разрушает именно эту дорогу; если такой дороги уже нет, он разрушает любую оставшуюся дорогу. Перед первым ходом Васи ребра \\(AB\\) нет, поэтому Вася не может сразу попасть в \\(B\\). Далее после каждого хода Пети выполняется инвариант: текущий город фишки не соединён дорогой с \\(B\\). Следовательно, следующим ходом Вася не может перейти в \\(B\\) по одной дороге. Инвариант снова восстанавливается Петей после хода Васи.\n\nТак как дорог конечное число и Петя каждый свой ход разрушает одну дорогу до остановки игры, игра не может дать Васе возможность попасть в \\(B\\). Значит Петя выигрывает при \\(k=\\binom n2-1\\), и вместе с верхней оценкой это даёт максимум.", "idea_ids": [ "idea-complete-graph-minus-target-edge" ], "standard_idea_ids": [], "status": "ai_checked", "definition_ids": [ "complete_graph", "connected_graph", "simple_graph" ], "review_notes": "ИИ-решение; готовый опубликованный разбор и автор в быстром открытом поиске не найдены. Внешние теоремы не используются." } ], "difficulty": { "main": "regional", "local_score": 6, "comment": "Импортировано из проверенной архивной карточки ЮМТ 2017_start_first_round1_problem3.md; этап: Старт, первая лига, первый тур.", "status": "ai_checked" }, "tags": [ "goal_strategy_game", "construction", "goal_exact_bound" ], "sources": [ { "source_id": "src-yumt-2017-start-first-round1-problem3-official", "role": "problem_and_solutions_official", "status": "source_verified" } ], "editorial": { "created_by": "ai", "created_at": "2026-04-25", "review_status": "ai_checked", "public_ready": true, "notes": [ "Импортировано из проверенной рабочей карточки ЮМТ 2017_start_first_round1_problem3.md.", "Есть внутренний родственник в высшей старт-лиге 2017 с усиленным ограничением на путь.", "2026-04-27: сверено с распакованной рабочей карточкой ЮМТ; формулировка уточнена для явного порядка ходов/условия гарантии без изменения математического смысла источника.", "2026-05-05: добавлено самодостаточное ИИ-решение. Готовый опубликованный разбор и автор в открытом поиске не найдены; официальная страница adygmath содержит материалы ЮМТ 2017.", "2026-05-05: ответ C(n,2)-1; верхняя оценка следует из проигрыша Пети на полном графе, а конструкция — полный граф без ребра AB с удалением ребра из текущего города фишки в B после каждого хода Васи. Внешние теоремы не используются." ], "relations_status": "deep_done", "graph_theory_duplicate_removed": true, "solution_classification": { "type": "official_complete_or_near_complete", "label": "официальное полное/почти полное", "status": "ai_checked", "confidence": 0.78, "basis": "агентский аудит средней сложности", "notes": "Метаданные источника указывают на архивное или официальное решение; решение проверено.", "audit_source": "agent-russian-archives.json" } } }