{ "id": "yumt-2017-start-high-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", "graph_distance", "edge_deletion_game" ], "methods": [ "extremal_edge_counting", "explicit_construction", "strategy_stealing_prevention" ], "transformations": [], "goal": [ "find_maximum_number_of_edges_for_winning_strategy" ], "auxiliary_graph_type": [], "invariants": [ "distance_between_start_and_target_before_first_move", "number_of_missing_edges" ], "keywords": [ "yumt", "2017_start_high_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-high-round1-problem3-official", "status": "ai_checked", "self_contained": { "status": "ai_checked" }, "definition_ids": [] } ], "graph_theory": [], "olympiad_reformulations": [] }, "ideas": [ { "id": "idea-distance-three-missing-edges", "title": "До первого разрушения нужна пара городов на расстоянии хотя бы 3", "text": "Вася ходит первым, поэтому если выбранные Петей города A и B находятся на расстоянии не больше 2 в исходном графе, Вася сразу попадает в B. Значит для выигрыша Пети нужна пара на расстоянии хотя бы 3; это заставляет отсутствовать ребро AB и, для каждого другого города, хотя бы одно из ребер к A и B.", "status": "ai_checked" }, { "id": "idea-delete-leaf-bridge-after-first-move", "title": "Почти полный граф с листом на расстоянии 3", "text": "Оценка достигается графом: на n-1 вершинах взять полный граф без одного ребра Ax, а последнюю вершину B сделать листом, соединенным только с x. После первого хода Васи Петя удаляет ребро xB, и B становится недостижимым.", "status": "ai_checked" } ], "solutions": [ { "id": "sol-ai-distance-three-extremal", "title": "ИИ-решение: расстояние 3 и подсчет недостающих рёбер", "text": "Ответ: \\(k_max\\) = C(n-1,2).\n\nСначала докажем верхнюю оценку. Пусть Петя может выиграть на некотором исходном графе с k ребрами и выбранными городами A,B. До первого хода Васи Петя еще не разрушил ни одной дороги. Поэтому если в исходном графе расстояние от A до B не больше 2, Вася первым же ходом переходит в B и выигрывает. Следовательно, для выигрышной стратегии Пети необходимо, чтобы расстояние между A и B было хотя бы 3.\n\nЭто условие сразу ограничивает число ребер. Во-первых, ребра AB нет. Во-вторых, ни один город v, отличный от A и B, не может быть соединен дорогами одновременно с A и с B: иначе был бы путь A-v-B длины 2. Значит для каждого из n-2 таких городов отсутствует хотя бы одно из двух ребер Av и Bv. Все эти отсутствующие ребра различны, и вместе с отсутствующим ребром AB их не меньше n-1. В полном графе на n вершинах C(n,2) ребер, поэтому\nk <= C(n,2) - (n-1) = C(n-1,2).\n\nОсталось показать, что эта оценка достижима. Возьмем вершины A,B,x и еще n-3 вершин. На множестве из n-1 вершин, состоящем из A,x и этих n-3 вершин, проведем все ребра, кроме ребра Ax. Вершину B соединим единственным ребром с x. Граф связен, так как n>10, а число ребер равно\n(C(n-1,2)-1)+1 = C(n-1,2).\nРасстояние от A до B равно 3: например, A-s-x-B для любой из дополнительных вершин s, а более короткого пути нет, поскольку B соединена только с x, а ребра Ax нет.\n\nПетя выбирает эти A и B. Первым ходом Вася не может попасть в B, потому что до B нужно проехать три дороги. После этого Петя разрушает единственную дорогу xB. Город B становится изолированным, поэтому при дальнейшей игре Вася уже никогда не сможет попасть в B. Значит Петя выигрывает при k=C(n-1,2), и вместе с верхней оценкой это дает требуемый максимум.", "idea_ids": [ "idea-distance-three-missing-edges", "idea-delete-leaf-bridge-after-first-move" ], "standard_idea_ids": [], "status": "ai_checked", "definition_ids": [ "connected_graph", "path" ] } ], "difficulty": { "main": "regional", "local_score": 6, "comment": "Импортировано из проверенной архивной карточки ЮМТ 2017_start_high_round1_problem3.md; этап: Старт, высшая лига, первый тур.", "status": "ai_checked" }, "tags": [ "goal_strategy_game" ], "sources": [ { "source_id": "src-yumt-2017-start-high-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": [ "2026-05-05: добавлено ИИ-решение; публичный официальный разбор и автор в открытом поиске не найдены. Решение элементарное: расстояние до первого хода, подсчет недостающих ребер и явная конструкция.", "Импортировано из проверенной рабочей карточки ЮМТ 2017_start_high_round1_problem3.md.", "Есть внутренний родственник в первой старт-лиге 2017 с более общим вариантом игры.", "2026-04-27: сверено с распакованной рабочей карточкой ЮМТ; формулировка уточнена для явного порядка ходов/условия гарантии без изменения математического смысла источника." ], "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" } } }