{ "id": "yumt-2017-premier-round1-problem2", "title": "Министры Петя и Вася на карте городов, ЮМТ 2017", "kind": { "primary": "olympiad_problem", "secondary": [ "graph_in_statement", "application" ] }, "language": "ru", "authors": [ { "name": "?", "status": "needs_human_review" } ], "problem_profile": { "objects": [ "simple_connected_graph", "target_vertex_game", "distance_at_most_two_move", "edge_deletion_strategy" ], "methods": [ "first_move_distance_obstruction", "extremal_edge_count_with_no_common_neighbor", "isolating_leaf_target" ], "transformations": [], "goal": [ "maximize_initial_number_of_edges_for_peter_win" ], "auxiliary_graph_type": [], "invariants": [ "distance_between_start_and_target_before_first_move" ], "keywords": [ "yumt", "2017_premier_round1_problem2", "yumt_2017" ], "status": "needs_human_review" }, "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-premier-round1-problem2-official", "status": "ai_checked", "self_contained": { "status": "ai_checked" }, "definition_ids": [] } ], "graph_theory": [], "olympiad_reformulations": [] }, "ideas": [ { "id": "idea-first-move-distance-and-leaf-target", "title": "Первый ход Васи и листовая цель", "text": "Если расстояние от начального города \\(A\\) до цели \\(B\\) не больше 2, Вася выигрывает первым ходом. Поэтому для выигрышной позиции Пети вершины \\(A\\) и \\(B\\) не смежны и не имеют общего соседа, что сразу ограничивает число рёбер. Равенство достигается почти полным графом: \\(B\\) является листом, а из полного графа на остальных вершинах удалено только ребро от \\(A\\) к соседу \\(B\\).", "tags": [ "goal_strategy_game", "construction" ], "status": "ai_checked" } ], "solutions": [ { "id": "sol-ai-first-move-distance-leaf", "title": "ИИ-решение: расстояние до первого хода и листовая цель", "text": "Ответ: \\(\\binom{n-1}{2}=\\frac{(n-1)(n-2)}2\\).\n\nСначала докажем верхнюю оценку. Пусть Петя выбрал карту, города \\(A,B\\) и рассчитывает выиграть. Перед первым ходом Васи расстояние от \\(A\\) до \\(B\\) обязано быть больше 2: иначе Вася сразу за один ход переместил бы фишку в \\(B\\) и победил бы.\n\nЗначит, ребра \\(AB\\) нет, и у \\(A\\) и \\(B\\) нет общего соседа. Поэтому каждый из остальных \\(n-2\\) городов может быть соединён дорогой не более чем с одним из городов \\(A,B\\). Между самими остальными \\(n-2\\) городами дорог не больше, чем в полном графе. Следовательно,\n\\[\nk\\le \\binom{n-2}{2}+(n-2)=\\binom{n-1}{2}.\n\\]\n\nОсталось показать, что эта оценка достижима. Возьмём города \\(A,B,C\\) и ещё \\(n-3\\) городов. На всех городах, кроме \\(B\\), проведём полный граф, но удалим из него ребро \\(AC\\). После этого добавим единственную дорогу \\(BC\\). Тогда всего дорог\n\\[\n\\binom{n-1}{2}-1+1=\\binom{n-1}{2}.\n\\]\nГраф связен, прост, а расстояние от \\(A\\) до \\(B\\) равно 3: например, путь \\(A-D-C-B\\) существует для любого другого города \\(D\\), а пути длины 1 или 2 нет, потому что единственный сосед \\(B\\) — это \\(C\\), и ребро \\(AC\\) удалено.\n\nПетя отмечает эти города \\(A\\) и \\(B\\). Первым ходом Вася не может попасть в \\(B\\), поскольку до \\(B\\) из \\(A\\) нужно пройти три дороги. После первого хода Васи Петя разрушает единственную дорогу \\(BC\\), и город \\(B\\) становится изолированным. Поэтому дальше Вася уже никогда не сможет оказаться в \\(B\\), как бы он ни играл. Значит, Петя выигрывает при \\(k=\\binom{n-1}{2}\\), и это наибольшее возможное значение.", "idea_ids": [ "idea-first-move-distance-and-leaf-target" ], "standard_idea_ids": [ "extremal_choice", "delete_to_simplify" ], "status": "ai_checked", "definition_ids": [ "simple_graph", "connected_graph", "distance" ], "source_id": "src-yumt-2017-premier-round1-problem2-official", "review_notes": "ИИ-решение; официальный PDF с условием проверен, готовый опубликованный разбор и автор в быстром открытом поиске не найдены. Внешние теоремы не используются." } ], "difficulty": { "main": "regional", "local_score": 6, "comment": "Импортировано из проверенной архивной карточки ЮМТ 2017_premier_round1_problem2.md; этап: Премьер-лига, первый тур.", "status": "ai_checked" }, "tags": [ "goal_strategy_game", "construction", "goal_exact_bound" ], "sources": [ { "source_id": "src-yumt-2017-premier-round1-problem2-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_premier_round1_problem2.md.", "2026-04-27: сверено с распакованной рабочей карточкой ЮМТ; формулировка уточнена для явного порядка ходов/условия гарантии без изменения математического смысла источника.", "2026-05-05: официальный PDF adygmath содержит условие; готовый опубликованный разбор и автор быстрым открытым поиском не найдены.", "2026-05-05: добавлено самодостаточное ИИ-решение без внешних теорем. Ответ C(n-1,2); верхняя оценка следует из того, что перед первым ходом Васи расстояние от A до B должно быть больше 2, а равенство даёт почти полный граф с листовой целью 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" } } }