{ "id": "putnam-2002-b2-polyhedron-face-game-four-edge-face", "title": "Игра на гранях полиэдра и грань с четырьмя сторонами, Putnam 2002 B2", "kind": { "primary": "olympiad_problem", "secondary": [ "graph_in_statement", "game" ] }, "language": "ru", "authors": [ { "name": "?", "status": "needs_human_review" } ], "problem_profile": { "objects": [ "polyhedral_graph", "face_adjacency", "cubic_planar_graph", "face_boundary_cycle" ], "methods": [ "winning_strategy", "euler_formula", "face_edge_double_counting", "fork_strategy" ], "transformations": [ "polyhedron_to_embedded_graph_game" ], "goal": [ "prove_first_player_win" ], "auxiliary_graph_type": [ "polyhedral_embedding", "face_incidence_hypergraph" ], "invariants": [ "three_faces_around_vertex", "face_size", "euler_characteristic", "edge_face_incidence" ], "keywords": [ "putnam_2002_b2", "polyhedron_game", "cubic_polyhedral_graph", "face_with_at_least_four_edges", "euler_formula" ], "status": "ai_checked" }, "statements": { "original": [ { "id": "stmt-original", "title": "Условие", "text": "Рассмотрим полиэдр по крайней мере с пятью гранями, у каждой вершины которого сходятся ровно три ребра. Два игрока по очереди подписывают ранее не подписанную грань своим именем. Побеждает тот, кто первым подпишет три грани, имеющие общую вершину. Докажите, что при правильной игре первый игрок всегда может выиграть.", "source_id": "src-putnam-2002-B2-kedlaya", "status": "ai_checked", "self_contained": { "status": "ai_checked" }, "definition_ids": [ "planar_graph", "degree" ], "distinct_from": [ "stmt-graph" ] } ], "graph_theory": [ { "id": "stmt-graph", "title": "Игра на гранях полиэдра и грань с четырьмя сторонами, Putnam 2002 B2", "text": "Пусть дан скелет выпуклого полиэдра с его вложением на сфере; у каждой вершины скелета степень 3, а число граней не меньше 5. Игроки по очереди выбирают еще не выбранные грани; игрок выигрывает, если после своего хода владеет всеми тремя гранями, инцидентными некоторой вершине. Докажите, что у первого игрока есть выигрышная стратегия.", "status": "ai_checked", "self_contained": { "status": "ai_checked" }, "definition_ids": [ "planar_graph", "degree" ], "distinct_from": [ "stmt-original" ] } ], "olympiad_reformulations": [] }, "ideas": [ { "id": "idea-large-face-gives-trap", "title": "Грань с четырьмя соседями дает вилку", "text": "Если первый игрок занимает грань с хотя бы четырьмя сторонами, то после первого ответа соперника среди соседних с ней граней найдутся три подряд свободные. Ход в среднюю из них создает две независимые угрозы закончить тройку вокруг одной из двух соседних вершин.", "tags": [ "goal_strategy_game", "planar_graphs" ], "status": "ai_checked" }, { "id": "idea-not-all-triangles", "title": "Кубический полиэдр с пятью гранями не весь треугольный", "text": "Если бы каждая грань была треугольником, то двойной счет ребер по вершинам и по граням вместе с формулой Эйлера дал бы ровно четыре грани. Это противоречит условию о по крайней мере пяти гранях.", "tags": [ "degree_counting", "planar_graphs", "double_counting" ], "status": "ai_checked" } ], "solutions": [ { "id": "sol-kedlaya-expanded", "title": "Стратегия через большую грань и вилку", "lemma_card_ids": [ "cubic-polyhedron-large-face-fork-strategy-lemma" ], "text": "Будем пользоваться стандартной комбинаторной моделью выпуклого полиэдра: его скелет является связным плоским графом на сфере, каждая грань является многоугольником, каждое ребро лежит на границе ровно двух граней, а две разные грани имеют не более одного общего ребра. При условии задачи в каждой вершине сходятся ровно три ребра, значит в каждой вершине сходятся ровно три грани.\n\nСначала докажем, что есть грань с не менее чем четырьмя сторонами. Обозначим через \\(V,E,F\\) числа вершин, ребер и граней полиэдра. Из условия о трех ребрах в каждой вершине получаем по лемме о рукопожатиях \\(3V=2E\\). Предположим, что все грани треугольные. Тогда сумма длин границ всех граней равна \\(3F\\), но каждое ребро при таком счете учитывается дважды, поэтому \\(3F=2E\\). Формула Эйлера для связного полиэдра дает \\(V-E+F=2\\). Подставляя \\(V=2E/3\\) и \\(F=2E/3\\), получаем \\(2E/3-E+2E/3=2\\), то есть \\(E/3=2\\). Следовательно, \\(E=6\\) и \\(F=2E/3=4\\), что противоречит условию \\(F\\ge 5\\). Значит, не все грани треугольные; так как каждая грань имеет хотя бы три стороны, существует грань \\(A\\) с числом сторон \\(k\\ge 4\\).\n\nПервый игрок первым ходом подписывает эту грань \\(A\\). Рассмотрим грани, соседние с \\(A\\) вдоль ее сторон, в циклическом порядке обхода границы \\(A\\): \\(H_1,H_2,\\ldots,H_k\\). Они попарно различны, потому что две грани полиэдра не могут иметь две разные общие стороны. После первого хода второго игрока среди этих \\(k\\) граней занята не более одна: второй игрок сделал только один ход, и этот ход мог быть вообще не соседней с \\(A\\) гранью. В цикле длины \\(k\\ge 4\\) с не более чем одной занятой позицией всегда найдутся три подряд идущие свободные позиции. Действительно, если занятая соседняя грань есть, возьмем три следующие после нее грани в циклическом порядке; если среди соседей \\(A\\) ничего не занято, возьмем любые три подряд. Обозначим такие свободные соседние грани через \\(B,C,D\\), где \\(C\\) стоит между \\(B\\) и \\(D\\). Вторым ходом первый игрок подписывает \\(C\\).\n\nПокажем явно, какие две угрозы возникли. Пусть \\(B\\) и \\(C\\) примыкают к двум соседним сторонам грани \\(A\\). Эти две стороны имеют общий конец, и в этой вершине ровно три инцидентные грани: \\(A\\), \\(B\\), \\(C\\). Поэтому если первый игрок следующим ходом подпишет \\(B\\), то у него будут три подписанные грани с общей вершиной. Точно так же грани \\(A\\), \\(C\\), \\(D\\) имеют общую вершину на другом конце стороны, общей для \\(A\\) и \\(C\\); ход в \\(D\\) тоже сразу выигрышный.\n\nСвоим вторым ходом второй игрок не может немедленно выиграть: после этого хода у него будет всего две подписанные грани. Этим же ходом он может занять не более одной из двух граней \\(B\\) и \\(D\\). Следовательно, по крайней мере одна из них остается свободной. Третьим ходом первый игрок подписывает оставшуюся свободной грань из \\(B,D\\) и получает либо тройку \\(A,B,C\\), либо тройку \\(A,C,D\\) с общей вершиной. Значит, первый игрок выигрывает, причем не позднее своего третьего хода.", "source_id": "src-kalva-putnam-2002-b2-solution", "idea_ids": [ "idea-large-face-gives-trap", "idea-not-all-triangles" ], "standard_idea_ids": [ "invariant", "double_counting" ], "status": "ai_checked", "definition_ids": [ "planar_graph", "degree" ], "repair_status": "medium_reasoning_understandable_2026_05_06", "review_notes": "Средний аудит 2026-05-06: решение понятно для ИИ со средним уровнем рассуждения; скрытых непроверенных переходов при чтении не найдено." } ], "difficulty": { "main": "national_final_hard", "local_score": 12, "comment": "Putnam B2; короткая стратегия, но требуется аккуратно применить формулу Эйлера и свойства граней выпуклого полиэдра.", "status": "ai_checked" }, "tags": [ "planar_graphs", "degree_counting", "goal_strategy_game", "double_counting" ], "properties": { "central_method": { "value": [ "polyhedral_face_size_lemma", "fork_strategy" ], "status": "ai_checked" } }, "sources": [ { "source_id": "src-putnam-2002-B2-kedlaya", "role": "archived_statement", "status": "source_verified" } ], "editorial": { "created_by": "ai", "created_at": "2026-05-02", "review_status": "ai_checked", "public_ready": true, "notes": [ "Решение сверено с Kedlaya/Ng 2002s.pdf: источник явно предупреждает, что используются стандартные свойства полиэдров, включая связность и запрет многократного общего ребра у пары граней. В карточке графовая формулировка поэтому уточнена как скелет выпуклого полиэдра.", "2026-05-05: структурно-игровой инструмент вынесен в отдельную lemma-card cubic-polyhedron-large-face-fork-strategy-lemma; решение явно ссылается на нее через lemma_card_ids и сохраняет полный развернутый аргумент.", "2026-05-06: опубликованное решение дополнительно сверено с Kalva/John Scholes; локальный источник src-putnam-2002-B2-kedlaya оставлен как архив условия, а источники решения указаны отдельными entries с URL." ], "relations_status": "deep_done", "solution_classification": { "type": "unofficial_published", "label": "опубликованное неофициальное", "status": "ai_checked", "confidence": 0.9, "basis": "Опубликованное решение Калвы и Джона Скоулза сверено с материалом Kedlaya/Ng 2002s.pdf и архивной формулировкой Putnam.", "notes": "Опубликованное неофициальное решение полностью развернуто в самодостаточное доказательство; lemma-card сохранена как переиспользуемое выделение, но основной текст не зависит от внешней леммы.", "audit_source": "agent-university-archives.json" } } }