{ "id": "spbmo-2010-11-p3-k2009-long-cycle-game", "title": "Игра на полном графе \\(K_{2009}\\) и цикл длины 75, СПбМО 2010, 11 класс, II тур, задача 3", "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" ], "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" ], "invariants": [ "at_most_ten_new_blocked_edges_per_evening", "reserved_spokes_are_already_privatised", "many_good_extension_vertices_remain" ], "keywords": [ "spbmo_2010_11_p3", "maker_breaker_cycle_game", "complete_graph_2009", "cycle_length_75", "ten_deleted_edges" ], "status": "ai_checked" }, "statements": { "original": [ { "id": "stmt-original", "title": "Условие", "text": "В стране 2009 городов и любые два из них соединены дорогой (не проходящей через другие города). Бизнесмен и Министерство Дорожного Строительства играют в игру. Бизнесмен каждое утро приватизирует одну из дорог, а Министерство каждый вечер разрушает по десять еще не приватизированных им дорог. Сможет ли Бизнесмен, несмотря на козни Министерства, создать циклический маршрут из приватизированных дорог, проходящий по одному разу ровно по 75 разным городам?", "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_{2009}\\) и цикл длины 75", "text": "На ребрах полного графа \\(K_{2009}\\) играют два игрока. За ход первого игрока выбирается одно еще не выбранное и не заблокированное ребро; после этого второй игрок блокирует десять еще не выбранных первым игроком ребер. Выбранные первым игроком ребра уже нельзя заблокировать. Докажите, что первый игрок может гарантированно получить среди своих ребер простой цикл длины ровно 75.", "status": "ai_checked", "self_contained": { "status": "ai_checked" }, "definition_ids": [ "complete_graph", "cycle" ], "distinct_from": [ "stmt-original" ] } ], "olympiad_reformulations": [] }, "ideas": [ { "id": "idea-reserved-spokes", "title": "Сначала приватизировать запасные ребра к одному центру", "text": "Если заранее приватизировать 12 ребер из одного города \\(c\\) к вершинам \\(a_0,a_1,\\ldots,a_{11}\\), то Министерство уже не сможет разрушить эти ребра. Дальше достаточно построить приватизированный путь от \\(a_0\\) к одной из запасных вершин \\(a_i\\): вместе с двумя приватизированными ребрами к \\(c\\) он даст цикл.", "tags": [ "construction", "goal_strategy_game" ], "status": "ai_checked" }, { "id": "idea-eleven-final-options", "title": "Одиннадцать вариантов сильнее десяти разрушений", "text": "Финальную вершину пути выбирают так, чтобы от нее не были разрушены все 11 ребер к запасным вершинам \\(a_1,\\ldots,a_{11}\\). После вечернего хода Министерство может разрушить не больше 10 из них, поэтому утром у Бизнесмена останется хотя бы одно завершающее ребро.", "tags": [ "pigeonhole_principle", "goal_strategy_game" ], "status": "ai_checked" }, { "id": "idea-good-vertices-count", "title": "Хороших вершин для продолжения пути всегда много", "text": "Назовем вершину хорошей, если ни одно из ее 11 ребер к запасным вершинам не разрушено. После не более чем 83 вечерних ходов разрушено не более 830 ребер, значит плохих вершин относительно запасного множества не более 830. Даже с учетом уже использованных вершин и разрушенных ребер из текущего конца пути хорошая доступная вершина остается.", "tags": [ "pigeonhole_principle", "graph_model" ], "status": "ai_checked" } ], "solutions": [ { "id": "sol-reserve-spokes-and-greedy-path", "title": "Запасные спицы и жадное построение пути", "text": "Ответ: сможет.\n\nСначала Бизнесмен выбирает город \\(c\\). В течение первых 12 утренних ходов он приватизирует 12 дорог из \\(c\\) в разные города; обозначим их концы через \\(a_0,a_1,\\ldots,a_{11}\\). Это возможно: перед \\(k\\)-м из этих ходов уже приватизировано \\(k-1\\) дорог из \\(c\\), а Министерство успело разрушить всего не более \\(10(k-1)\\) дорог, так что при \\(k\\le 12\\) из \\(2008\\) дорог, выходящих из \\(c\\), еще остается свободная дорога.\n\nДальше город \\(a_0\\) будет началом длинного пути, а города \\(a_1,\\ldots,a_{11}\\) оставим запасными для конца пути. Назовем город хорошим, если он не равен \\(c,a_0,a_1,\\ldots,a_{11}\\), еще не использован в строящемся пути и ни одна из дорог от него к запасным городам \\(a_1,\\ldots,a_{11}\\) не разрушена.\n\nПокажем, что Бизнесмен может 72 раза подряд продолжить путь из текущего конца в новый хороший город. Перед любым из этих 72 ходов с начала игры прошло не более \\(12+71=83\\) вечеров, поэтому Министерство разрушило не более \\(830\\) дорог. Каждый нехороший город из-за запасного множества требует хотя бы одной разрушенной дороги к одному из \\(a_1,\\ldots,a_{11}\\), значит таких городов не более \\(830\\). Кроме того, к этому моменту использовано не более 72 внутренних городов пути, а также 13 специальных городов \\(c,a_0,\\ldots,a_{11}\\). Поэтому среди городов, которые могли бы стать следующим хорошим концом пути, остается по крайней мере \\(2009-13-72-830=1094\\) кандидата.\n\nИз текущего конца пути Министерство за все время могло разрушить не более тех же \\(830\\) дорог. Так как хороших неиспользованных кандидатов больше 830, хотя бы одна дорога из текущего конца пути в хороший новый город не разрушена. Бизнесмен приватизирует ее и тем самым продлевает путь, сохраняя новый конец хорошим на момент выбора.\n\nПосле 72 таких продолжений у Бизнесмена есть приватизированный путь из \\(a_0\\) в некоторый город \\(v\\), проходящий через 73 города: \\(a_0\\) и 72 новых внутренних города. Когда город \\(v\\) был выбран, все 11 дорог из \\(v\\) в запасные города \\(a_1,\\ldots,a_{11}\\) были целы. Вечером после этого Министерство может разрушить не более 10 дорог, значит утром хотя бы одна из этих 11 дорог, скажем \\(va_i\\), все еще цела. Бизнесмен приватизирует ее.\n\nТеперь приватизированы дороги \\(ca_0\\), весь путь от \\(a_0\\) до \\(v\\), дорога \\(va_i\\) и дорога \\(a_i c\\). Они образуют простой цикл. В нем ровно \\(1+1+72+1=75\\) городов: центр \\(c\\), начальный город \\(a_0\\), 72 внутренних города пути и конечный запасной город \\(a_i\\). Значит Бизнесмен гарантированно создает требуемый циклический маршрут.", "idea_ids": [ "idea-reserved-spokes", "idea-eleven-final-options", "idea-good-vertices-count" ], "standard_idea_ids": [ "pigeonhole_principle", "greedy_ordering" ], "status": "ai_checked", "definition_ids": [ "complete_graph", "cycle" ] } ], "difficulty": { "main": "regional", "local_score": 6, "comment": "СПбМО 2010, 11 класс. Идея короткая, но решение требует аккуратного учета чисел: 12 заранее приватизированных спиц, 11 запасных концов против 10 вечерних разрушений и запас 2009 вершин для жадного продолжения пути.", "status": "ai_checked" }, "tags": [ "goal_strategy_game", "construction", "pigeonhole_principle", "graph_model" ], "properties": { "central_method": { "value": [ "reserve_spokes", "greedy_path_extension", "more_final_options_than_blocking_moves" ], "status": "ai_checked" }, "typical_olympiad_use": { "value": "Maker-breaker style strategy: first secure a small robust reserve, then use a counting buffer to keep many legal continuations.", "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, строки задачи 11 класса N3.", "Официального решения в найденном TeX/PDF-архиве не обнаружено; приведено локально проверенное решение.", "Исправлена исходная condition-only заготовка: задача просит цикл ровно по 75 городам в игре на 2009 городах, а не цикл длины 2009." ], "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" } } }