{ "id": "simon-marais-2018-b3-dodecahedron-spider-pursuit", "title": "Погоня трёх пауков за жуком на графе додекаэдра, SMMC 2018 B3", "kind": { "primary": "olympiad_problem", "secondary": [ "graph_in_statement", "game" ] }, "language": "ru", "authors": [ { "name": "?", "status": "needs_human_review" } ], "problem_profile": { "objects": [ "dodecahedron_graph", "metric_graph", "pursuit_evasion_game", "reflection_plane", "tree_subgraph", "graph_symmetry" ], "methods": [ "phased_strategy", "symmetry_barrier", "tree_chasing", "confinement_strategy", "case_analysis" ], "transformations": [ "polyhedron_edges_to_metric_graph", "delete_guarded_vertex_to_tree" ], "goal": [ "prove_spiders_have_winning_strategy" ], "auxiliary_graph_type": [ "dodecahedron_graph", "planar_cubic_graph", "tree_subgraph" ], "invariants": [ "fast_spider_reflects_beetle", "beetle_confined_to_component", "guarded_vertex_X", "tree_has_no_cycles" ], "keywords": [ "smmc_2018_b3", "dodecahedron_graph", "pursuit_game" ], "status": "ai_checked" }, "statements": { "original": [ { "id": "stmt-original", "title": "Условие", "text": "Три паука пытаются поймать жука. Все они изначально находятся на рёбрах правильного додекаэдра с длиной ребра \\(1\\). В некоторый момент они начинают непрерывно двигаться вдоль рёбер додекаэдра. Жук и один из пауков имеют максимальную скорость \\(1\\), а два остальных паука имеют максимальную скорость \\(1/2018\\). Каждый игрок всегда знает своё положение и положения всех остальных; можно мгновенно разворачиваться и реагировать на поведение других. Пауки могут договариваться о стратегии до игры и во время игры. Если какой-либо паук когда-либо оказывается в той же точке, что и жук, пауки выигрывают. Докажите, что пауки могут выиграть независимо от начальных положений всех участников и от движения жука.", "source_id": "src-simon-marais-2018-B3-official", "status": "ai_checked", "self_contained": { "status": "ai_checked" }, "definition_ids": [], "distinct_from": [ "stmt-graph" ] } ], "graph_theory": [ { "id": "stmt-graph", "title": "Погоня трёх пауков за жуком на графе додекаэдра, SMMC 2018 B3", "text": "На метрическом графе додекаэдра, где каждое ребро имеет длину \\(1\\), один быстрый преследователь скорости \\(1\\) и два медленных преследователя скорости \\(1/2018\\) ловят беглеца скорости \\(1\\). Все участники имеют полную информацию и могут двигаться по рёбрам. Докажите, что у трёх преследователей есть стратегия гарантированного захвата.", "status": "ai_checked", "self_contained": { "status": "ai_checked" }, "definition_ids": [ "simple_graph", "tree", "planar_graph" ], "distinct_from": [ "stmt-original" ] } ], "olympiad_reformulations": [] }, "ideas": [ { "id": "idea-capture-on-tree", "title": "На дереве медленный паук всё равно выдавливает жука", "text": "Если жук заперт в конечном дереве и не может пройти через охраняемые выходы, то паук, пусть даже очень медленный, может двигаться по единственному пути к жуку. Отступая, жук в конце концов приходит к листу или к охраняемой вершине.", "tags": [ "trees", "goal_strategy_game" ], "status": "ai_checked" }, { "id": "idea-reflection-barrier", "title": "Быстрый паук превращает плоскость симметрии в барьер", "text": "Когда жук находится в вершине \\(W\\), а быстрый паук — в зеркально симметричной вершине \\(V\\), быстрый паук может дальше копировать движение жука отражением относительно плоскости симметрии. Любое пересечение этой плоскости приводит к немедленному совпадению с быстрым пауком.", "tags": [ "graph_symmetry", "goal_strategy_game" ], "status": "ai_checked" } ], "solutions": [ { "id": "sol-official-structured", "title": "Сведение к дереву в половине додекаэдра", "text": "Рассматриваем рёбра додекаэдра как метрический граф \\(G\\), все рёбра имеют длину \\(1\\). Зафиксируем вершину \\(V\\). В графе додекаэдра относительно \\(V\\) есть соответственно \\(3,6,6,3,1\\) вершин на расстояниях \\(1,2,3,4,5\\); последняя вершина на расстоянии \\(5\\) единственна.\n\nПервая фаза. Быстрый паук идёт в \\(V\\), а один из медленных пауков — в единственную вершину, удалённую от \\(V\\) на расстояние \\(5\\). Это можно сделать независимо от жука: жук пауков не ловит, а время игры не ограничено. Пусть оба паука заняли эти позиции к моменту \\(t_0\\).\n\nВторая фаза. Оставшийся медленный паук может гарантировать, что после \\(t_0\\) жук посетит какую-нибудь вершину додекаэдра. Действительно, если жук после \\(t_0\\) вообще не посещает вершин, то он всё время остаётся во внутренности одного и того же ребра. Медленный паук доходит до этого ребра и затем идёт по нему к жуку. На отрезке жук не может пройти сквозь паука без поимки; значит, он либо будет пойман, либо вынужден выйти через конец ребра, то есть посетить вершину.\n\nКогда жук оказался в вершине, он не может быть ни в \\(V\\), ни в антиподальной к \\(V\\) вершине: там стоят пауки. Поэтому его расстояние от \\(V\\) равно \\(1\\), \\(2\\), \\(3\\) или \\(4\\). Если это расстояние равно \\(1\\), \\(2\\) или \\(4\\), обозначим эту вершину через \\(W\\). Если же жук попал в вершину уровня \\(3\\), пауки сначала вынуждают его прийти в вершину уровня \\(2\\) или \\(4\\). В самом деле, если жук никогда не посещает уровни \\(2\\) и \\(4\\), то он заперт в одном из малых подграфов, состоящих из двух соседних вершин уровня \\(3\\) и внутренних частей рёбер, ведущих к соседним вершинам уровней \\(2\\) и \\(4\\). Такой подграф является деревом с выходами в вершины уровней \\(2\\) и \\(4\\). Один из медленных пауков идёт в этом дереве по единственному пути к жуку; уже очищенная часть дерева отделена от жука положением паука, поэтому доступная жуком часть монотонно уменьшается. В конечном дереве это рано или поздно даёт поимку или вынуждает жука выйти через одну из граничных вершин уровня \\(2\\) или \\(4\\). В последнем случае снова обозначим эту вершину через \\(W\\). Пусть это произошло в момент \\(t_1\\).\n\nРассмотрим плоскость \\(P\\), перпендикулярно делящую отрезок \\(VW\\). Для расстояний \\(d(V,W)=1,2,4\\) эта плоскость является плоскостью зеркальной симметрии правильного додекаэдра; отражение относительно \\(P\\) переводит \\(V\\) в \\(W\\) и сохраняет граф \\(G\\). Удалим из метрического графа точки, лежащие в \\(P\\). Оставшаяся часть распадается на две компоненты; пусть \\(H\\) — компонента, содержащая \\(W\\). В официальной слоевой картине видно, что как граф \\(H\\) состоит из двух циклов с одним общим ребром. Выберем вершину \\(X\\), соседнюю с этим общим ребром, так что после удаления \\(X\\) подграф \\(H\\setminus\\{X\\}\\) становится деревом.\n\nНачиная с момента \\(t_1\\), быстрый паук всё время занимает точку, зеркально симметричную положению жука относительно \\(P\\). В момент \\(t_1\\) это уже верно: жук находится в \\(W\\), а быстрый паук — в \\(V\\). Поскольку отражение сохраняет рёбра и длины, а скорости у жука и быстрого паука одинаковые, быстрый паук может поддерживать такое зеркальное движение. Если жук коснётся плоскости \\(P\\), его точка совпадёт со своей зеркальной точкой, значит, там же окажется быстрый паук и жук будет пойман. Следовательно, не будучи пойманным, жук остаётся в компоненте \\(H\\).\n\nПосле \\(t_1\\) один медленный паук идёт в вершину \\(X\\) и остаётся там; пусть он занял её к моменту \\(t_2\\). Если после этого жук приходит в \\(X\\), он пойман. Если он касается \\(P\\), его ловит быстрый паук. Во всех остальных безопасных положениях после \\(t_2\\) жук находится в дереве \\(H\\setminus\\{X\\}\\). Второй медленный паук теперь преследует его внутри этого дерева, всё время двигаясь по единственному пути к текущему положению жука. Как и выше, жук не может пройти через паука, а компонента дерева, в которой он ещё может находиться, постепенно уменьшается. Так как дерево конечно, бесконечно уклоняться внутри него невозможно: жук либо пересечёт \\(P\\), либо попадёт в \\(X\\), либо будет пойман этим медленным пауком.\n\nИтак, во всех случаях пауки имеют стратегию, которая при любых начальных положениях и любом движении жука приводит к захвату.", "idea_ids": [ "idea-capture-on-tree", "idea-reflection-barrier" ], "standard_idea_ids": [ "invariant", "delete_to_simplify" ], "status": "ai_checked", "definition_ids": [ "tree", "connected_graph" ] } ], "difficulty": { "main": "national_final_hard", "local_score": 9, "comment": "Сложная стратегическая задача на метрическом графе додекаэдра; решение использует симметрию, разделение графа и преследование на дереве.", "status": "ai_checked" }, "tags": [ "graph_model", "goal_strategy_game", "graph_symmetry", "trees", "connectivity" ], "properties": { "central_method": { "value": [ "graph_symmetry", "trees", "goal_strategy_game" ], "status": "ai_checked" }, "typical_olympiad_use": { "value": "Зеркальная симметрия превращает середину додекаэдра в барьер, а затем охраняемая вершина удаляется так, чтобы оставшаяся область уклонения стала деревом.", "status": "ai_checked" } }, "sources": [ { "source_id": "src-simon-marais-2018-B3-official", "role": "problem_and_solution_official", "status": "source_verified" } ], "editorial": { "created_by": "ai", "created_at": "2026-05-02", "review_status": "ai_checked", "public_ready": true, "notes": [ "Сверено с официальным файлом smmc-2018-solutions_1.pdf, Problem B3, pages 13-15: сохранены фазы с вершиной V, антиподом, принуждением к вершине, плоскостью симметрии P, вершиной X и деревом H\\setminus\\{X\\}." ], "relations_status": "deep_done", "solution_classification": { "type": "official_complete_or_near_complete", "label": "официальное полное/почти полное", "status": "ai_checked", "confidence": 0.78, "basis": "агентский аудит средней сложности", "notes": "агент grouped classification", "audit_source": "agent-university-archives.json" } } }