{ "id": "spbmo-2018-10-p1-complete-graph-road-destruction-path", "title": "Маршрут в полном графе при разрушении дорог, СПбМО 2018, 10 класс, II тур, задача 1", "kind": { "primary": "olympiad_problem", "secondary": [ "graph_in_statement", "game" ] }, "language": "ru", "authors": [ { "name": "П. Ходунов", "status": "source_verified" }, { "name": "А. Кузнецов", "status": "source_verified" }, { "name": "И. Лосев", "status": "source_verified" } ], "problem_profile": { "objects": [ "complete_graph", "simple_path", "edge_deletion_process" ], "methods": [ "greedy_strategy", "adversary_strategy", "local_edge_counting" ], "transformations": [ "cities_to_vertices", "roads_to_edges", "route_to_simple_path", "road_destruction_to_edge_deletion" ], "goal": [ "exact_guaranteed_path_order" ], "auxiliary_graph_type": [ "complete_graph", "path" ], "invariants": [ "unvisited_edges_from_new_city_are_fresh_before_arrival_deletion", "president_can_delete_at_most_k_candidate_next_edges", "route_has_no_repeated_vertices" ], "keywords": [ "spbmo_2018_10_p1", "complete_graph", "road_destruction", "adversarial_path", "local_edge_deletion", "max_2_n_minus_k" ], "status": "ai_checked" }, "statements": { "original": [ { "id": "stmt-original", "title": "Условие", "text": "Миша приехал в страну, в которой \\(n\\) городов и каждые два напрямую соединены дорогой. Он собирается, начав с некоторого города, объехать несколько городов, не заезжая ни в один город дважды. Каждый раз, пока Миша едет по дороге, президент разрушает \\(k\\) дорог, ведущих из города, в который ведет эта дорога. (А если там нет такого количества уцелевших дорог, разрушает все оставшиеся, кроме той, по которой едет Миша.) Какое наибольшее количество городов сможет объехать Миша, независимо от действия президента?", "source_id": "src-spbmo-2018-city-911", "status": "ai_checked", "self_contained": { "status": "ai_checked" }, "definition_ids": [ "complete_graph", "path" ], "distinct_from": [ "stmt-graph" ] } ], "graph_theory": [ { "id": "stmt-graph", "title": "Маршрут в полном графе при разрушении дорог", "text": "В полном графе \\(K_n\\) два игрока играют в следующую игру. Первый игрок выбирает начальную вершину и затем каждый раз переходит из текущей вершины в еще не посещенную вершину по сохранившемуся ребру. После каждого такого перехода во второй конец выбранного ребра второй игрок удаляет до \\(k\\) сохранившихся ребер, инцидентных новой текущей вершине, но не удаляет ребро, по которому только что был сделан переход. Если таких ребер меньше \\(k\\), он может удалить все, кроме только что использованного. Определите наибольшее число вершин простого пути, которое первый игрок может гарантировать при любой игре второго.", "status": "ai_checked", "self_contained": { "status": "ai_checked" }, "definition_ids": [ "complete_graph", "path" ], "distinct_from": [ "stmt-original" ] } ], "olympiad_reformulations": [] }, "ideas": [ { "id": "idea-fresh-unvisited-edges", "title": "Ребра из нового города к непосещенным городам раньше не могли быть разрушены", "text": "Если Миша впервые приехал в город \\(v\\), а город \\(u\\) еще не посещен, то дорога \\(vu\\) до этого момента не могла быть разрушена как дорога из текущего города: ни \\(v\\), ни \\(u\\) еще не были текущими после приезда. Значит, президент может запретить продолжение из \\(v\\) только текущим удалением не более \\(k\\) таких дорог.", "tags": [ "process_invariant", "graph_model" ], "status": "ai_checked" }, { "id": "idea-more-unvisited-than-deletions", "title": "Если непосещенных городов больше \\(k\\), маршрут продолжается", "text": "После посещения \\(t\\) городов из текущего города ведут дороги во все \\(n-t\\) непосещенных городов, и перед текущим ходом президента они целы. Если \\(n-t>k\\), после удаления не более \\(k\\) дорог хотя бы одна дорога к новому городу останется.", "tags": [ "pigeonhole_principle", "goal_strategy_game" ], "status": "ai_checked" }, { "id": "idea-threshold-stop", "title": "На пороге \\(n-t\\le k\\) президент может остановить маршрут", "text": "Когда из текущего города осталось не больше \\(k\\) дорог к непосещенным городам, президент удаляет все эти дороги. Тогда продолжить простой маршрут невозможно. Это дает точную верхнюю оценку, а при очень большом \\(k\\) Миша все равно успевает сделать первый переезд.", "tags": [ "extremal_choice", "goal_exact_bound" ], "status": "ai_checked" } ], "solutions": [ { "id": "sol-local-deletion-threshold", "title": "Порог числа непосещенных городов", "text": "Ответ: если \\(n=1\\), то \\(1\\); если \\(n\\ge 2\\), то \\(\\max(2,n-k)\\). В обычной записи это означает: при \\(k\\le n-2\\) Миша гарантирует ровно \\(n-k\\) городов, а при \\(k\\ge n-1\\) - ровно \\(2\\) города.\n\nСначала докажем нижнюю оценку. Начать Миша может в любом городе. Предположим, что он уже посетил \\(t\\) городов и находится в городе \\(v\\), причем \\(tk\\). До приезда Миши в \\(v\\) ни одна дорога из \\(v\\) в еще непосещенный город не могла быть разрушена президентом: президент разрушает дороги только из того города, в который Миша только что приехал, а \\(v\\) раньше текущим городом не был; непосещенные города тоже еще не были текущими. Значит, перед действием президента из \\(v\\) ведут целые дороги во все \\(n-t\\) непосещенных городов. Президент может разрушить среди них не более \\(k\\), поэтому хотя бы одна такая дорога останется, и Миша сможет по ней продолжить маршрут. Следовательно, при \\(k\\le n-2\\) он может дойти до \\(t=n-k\\) посещенных городов. Если же \\(k\\ge n-1\\) и \\(n\\ge2\\), он по крайней мере выбирает начальный город и делает первый переезд, то есть посещает два города.\n\nТеперь докажем, что большего гарантировать нельзя. При \\(k\\le n-2\\) президент действует так: как только Миша приехал в очередной город и всего уже посещено \\(n-k\\) городов, непосещенных осталось ровно \\(k\\). Президент разрушает все дороги из текущего города к этим непосещенным городам. Ребро, по которому Миша приехал, не трогается, но оно ведет в уже посещенный город, а туда Мише возвращаться нельзя. Значит, продолжить маршрут невозможно, и больше \\(n-k\\) городов Миша гарантировать не может.\n\nПри \\(k\\ge n-1\\) президент после первого переезда Миши разрушает все еще уцелевшие дороги из нового города, кроме дороги, по которой Миша приехал. Все возможные продолжения ведут в непосещенные города и уничтожены, а возвращаться по старой дороге нельзя. Поэтому гарантировать больше двух городов невозможно. Совмещая нижнюю и верхнюю оценки, получаем указанную формулу.", "idea_ids": [ "idea-fresh-unvisited-edges", "idea-more-unvisited-than-deletions", "idea-threshold-stop" ], "standard_idea_ids": [ "pigeonhole_principle", "greedy_ordering", "extremal_choice" ], "status": "ai_checked", "definition_ids": [ "complete_graph", "path" ] } ], "difficulty": { "main": "regional", "local_score": 3, "comment": "СПбМО 2018, 10 класс, II тур, задача 1. Точная граница получается из одной локальной идеи: при первом попадании в город все дороги из него к еще непосещенным городам свежие, поэтому важен только текущий запас из \\(k\\) разрушений.", "status": "ai_checked" }, "tags": [ "goal_strategy_game", "goal_exact_bound", "pigeonhole_principle", "process_invariant", "graph_model" ], "properties": { "central_method": { "value": [ "local_edge_deletion_threshold", "fresh_unvisited_edges_invariant", "adversary_stopping_strategy" ], "status": "ai_checked" }, "typical_olympiad_use": { "value": "В динамическом графовом процессе нужно считать не все разрушенные дороги, а только те, которые могли затронуть текущий набор возможных продолжений.", "status": "ai_checked" } }, "sources": [ { "source_id": "src-spbmo-2018-city-911", "role": "official_problem_statement", "status": "source_verified", "statement_ids": [ "stmt-original" ], "note": "Сверено с официальным PDF PDMI c_911_18.pdf и локальной копией TeX audit/spbmo/pdmi_downloads/2018_c_911_18.tex; TeX использует cp866." } ], "editorial": { "created_by": "ai", "created_at": "2026-05-03", "review_status": "ai_checked", "public_ready": true, "notes": [ "2026-05-04: исходная condition-only заготовка с поврежденной кириллицей заменена на точное условие 10 класса, II тура, задачи 1 из официального PDF SPbMO/PDMI.", "Авторы подтверждены по подписи в официальном PDF и TeX: П. Ходунов, А. Кузнецов, И. Лосев.", "Роль полного графа, пути и разрушения проверена: страна является \\(K_n\\), маршрут без повторов является простым путём, а разрушение дорог - локальным удалением рёбер из только что достигнутой вершины.", "Официальное решение в найденном источнике не опубликовано; добавлено самостоятельное полное решение с нижней и верхней оценками." ], "relations_status": "deep_done", "solution_classification": { "type": "ai_original", "label": "ИИ-решение с нуля", "status": "ai_checked", "confidence": 0.78, "basis": "агентский аудит средней сложности", "notes": "solution appears AI-авторed/reconstructed, with no официальное решение marker", "audit_source": "agent-russian-archives.json" } } }