{ "id": "spbmo-2010-9-p5-k2010-cycle-game", "title": "Игра на полном графе \\(K_{2010}\\) и цикл длины 11, СПбМО 2010, 9 класс, II тур, задача 5", "kind": { "primary": "olympiad_problem", "secondary": [ "graph_in_statement", "game" ] }, "language": "ru", "authors": [ { "name": "Берлов С.Л.", "status": "source_verified", "note": "В официальном TeX-архиве после задачи стоит макрос \\be, определенный как подпись С. Берлова." } ], "problem_profile": { "objects": [ "complete_graph", "cycle", "edge_claiming_game", "subdivided_star" ], "methods": [ "greedy_strategy", "reserve_set", "pigeonhole_counting" ], "transformations": [ "cities_to_vertices", "roads_to_edges", "privatized_roads_to_maker_edges", "destroyed_roads_to_blocked_edges" ], "goal": [ "winning_strategy" ], "auxiliary_graph_type": [ "complete_graph", "path", "cycle", "tree" ], "invariants": [ "at_most_ten_new_blocked_edges_per_evening", "fresh_vertices_remain_for_greedy_extension", "eleven_final_closing_edges_before_ministry_move" ], "keywords": [ "spbmo_2010_9_p5", "maker_breaker_cycle_game", "complete_graph_2010", "cycle_length_11", "ten_deleted_edges", "subdivided_star_strategy" ], "status": "ai_checked" }, "statements": { "original": [ { "id": "stmt-original", "title": "Условие", "text": "В стране 2010 городов и любые два из них соединены дорогой (не проходящей через другие города). Бизнесмен и Министерство Дорожного Строительства играют в игру. Бизнесмен каждое утро приватизирует одну из дорог, а Министерство каждый вечер разрушает по десять еще не приватизированных дорог. Сможет ли Бизнесмен, несмотря на козни Министерства, создать циклический маршрут по приватизированным дорогам, проходящий по одному разу по 11 разным городам?", "source_id": "src-spbmo-2010-city-911-tex", "status": "ai_checked", "self_contained": { "status": "ai_checked" }, "definition_ids": [ "complete_graph", "cycle" ], "distinct_from": [ "stmt-graph" ] } ], "graph_theory": [ { "id": "stmt-graph", "title": "Игра на полном графе \\(K_{2010}\\) и цикл длины 11", "text": "На ребрах полного графа \\(K_{2010}\\) играют два игрока. За ход первого игрока выбирается одно еще не выбранное и не заблокированное ребро; после этого второй игрок блокирует десять еще не выбранных первым игроком ребер. Выбранные первым игроком ребра уже нельзя заблокировать. Докажите, что первый игрок может гарантированно получить среди своих ребер простой цикл длины ровно 11.", "status": "ai_checked", "self_contained": { "status": "ai_checked" }, "definition_ids": [ "complete_graph", "cycle" ], "distinct_from": [ "stmt-original" ] } ], "olympiad_reformulations": [] }, "ideas": [ { "id": "idea-subdivided-star", "title": "Луч длины 5 превращает два конца в цикл длины 11", "text": "Если из одного центра построены два непересекающихся внутри луча длины 5, то их концы соединены приватизированным путем длины 10 через центр. Достаточно затем приватизировать дорогу между этими концами, чтобы получить простой цикл длины 11.", "tags": [ "trees", "goal_strategy_game" ], "status": "ai_checked" }, { "id": "idea-eleven-closing-options", "title": "Одиннадцать замыкающих дорог сильнее десяти разрушений", "text": "После построения 11 старых лучей можно выбрать конец нового луча так, чтобы дороги от него ко всем 11 старым концам были целы. Вечером Министерство может разрушить только 10 таких дорог, поэтому утром у Бизнесмена останется хотя бы одна дорога, замыкающая цикл.", "tags": [ "pigeonhole_principle", "goal_strategy_game" ], "status": "ai_checked" }, { "id": "idea-global-destroyed-edge-count", "title": "Глобальный счет разрушенных дорог оставляет свежий выбор", "text": "До решающего выбора сделано меньше 60 ходов Бизнесмена, значит Министерство разрушило меньше 600 дорог. Одна разрушенная дорога может запретить не более одного кандидата на новый конец луча, поэтому среди почти двух тысяч еще не использованных городов остается много подходящих кандидатов.", "tags": [ "pigeonhole_principle", "graph_model" ], "status": "ai_checked" } ], "solutions": [ { "id": "sol-subdivided-star-eleven-threats", "title": "Двенадцатый луч и одиннадцать угроз замыкания", "text": "Ответ: сможет.\n\nВыберем город \\(c\\). Бизнесмен сначала построит из \\(c\\) 11 попарно не пересекающихся внутри приватизированных путей длины 5. Будем называть их лучами, а их последние города - концами лучей. Это можно делать жадно: перед каждым из первых 55 утренних ходов Министерство успело разрушить не более \\(10\\cdot 54=540\\) дорог, а использовано меньше 56 городов. Поэтому из текущего конца строящегося луча остается хотя бы один еще не использованный город, дорога к которому не разрушена; Бизнесмен приватизирует такую дорогу. Если в процессе уже появился нужный цикл, задача решена, так что считаем, что этого не произошло.\n\nОбозначим концы построенных 11 лучей через \\(l_1,\\ldots,l_{11}\\). Теперь Бизнесмен начинает строить из того же центра \\(c\\) двенадцатый луч, снова используя только новые города, и жадно приватизирует первые 4 его дороги. Это возможно по той же причине: к этому моменту сделано всего 59 ходов или меньше, разрушенных дорог не более \\(590\\), а свободных городов намного больше.\n\nПусть \\(y\\) - текущий конец недостроенного двенадцатого луча, находящийся на расстоянии 4 от \\(c\\). Выберем последний город \\(x\\) этого луча так, чтобы не были разрушены дороги \\(yx,xl_1,\\ldots,xl_{11}\\). Такой город существует. Действительно, сейчас использовано только 60 городов, а среди остальных 1950 городов каждый неподходящий кандидат \\(x\\) требует хотя бы одной уже разрушенной дороги из набора \\(yx,xl_1,\\ldots,xl_{11}\\). Разрушенных дорог всего не более \\(590\\), значит неподходящих кандидатов не более \\(590\\), и подходящий город остается.\n\nБизнесмен приватизирует дорогу \\(yx\\), завершая двенадцатый луч длины 5. Теперь для каждого \\(i=1,\\ldots,11\\) в его приватизированном графе уже есть путь длины 10 от \\(x\\) до \\(l_i\\): пять дорог от \\(x\\) до \\(c\\) по двенадцатому лучу и пять дорог от \\(c\\) до \\(l_i\\) по старому лучу. Кроме того, все 11 дорог \\(xl_1,\\ldots,xl_{11}\\) еще целы и не приватизированы.\n\nВечером Министерство может разрушить не более 10 из этих 11 дорог. Поэтому на следующее утро хотя бы одна дорога \\(xl_i\\) остается целой. Бизнесмен приватизирует ее. Вместе с двумя лучами от \\(c\\) к \\(x\\) и к \\(l_i\\) эта дорога образует простой цикл из \\(5+5+1=11\\) дорог, проходящий по одному разу по 11 разным городам. Значит Бизнесмен имеет выигрышную стратегию.", "idea_ids": [ "idea-subdivided-star", "idea-eleven-closing-options", "idea-global-destroyed-edge-count" ], "standard_idea_ids": [ "pigeonhole_principle", "greedy_ordering" ], "status": "ai_checked", "definition_ids": [ "complete_graph", "path", "cycle" ] } ], "difficulty": { "main": "regional", "local_score": 5, "comment": "СПбМО 2010, 9 класс. Ключевая идея доступна: построить много лучей длины 5 и получить 11 одновременных возможностей замкнуть цикл против 10 вечерних разрушений; аккуратность нужна только в счете свободных городов.", "status": "ai_checked" }, "tags": [ "goal_strategy_game", "construction", "pigeonhole_principle", "trees", "graph_model" ], "properties": { "central_method": { "value": [ "subdivided_star_strategy", "greedy_fresh_vertex_choice", "more_final_options_than_blocking_moves" ], "status": "ai_checked" }, "typical_olympiad_use": { "value": "Maker-breaker style strategy: build a robust partial graph whose last move creates more immediate threats than the opponent can block.", "status": "ai_checked" } }, "sources": [ { "source_id": "src-spbmo-2010-city-911-tex", "role": "official_problem_statement", "status": "source_verified", "statement_ids": [ "stmt-original" ] } ], "editorial": { "created_by": "ai", "created_at": "2026-05-03", "review_status": "ai_checked", "public_ready": true, "notes": [ "2026-05-04: условие сверено с локальной копией официального TeX-архива PDMI audit/spbmo/pdmi_downloads/2010_91110tex.zip, файл c_911_10.tex, строки задачи 9 класса N5; архив использует cp866.", "Исправлена исходная condition-only заготовка: задача просит цикл ровно по 11 городам в игре на 2010 городах, а не цикл длины 2010.", "Автор подтвержден по макросу \\be в том же TeX-файле; макрос определен как подпись С. Берлова.", "Официального решения в найденном TeX/PDF-архиве не обнаружено; приведено локально проверенное самодостаточное решение." ], "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" } } }