{ "id": "yumt-2025-grand-round4-problem3", "title": "Игра Зайца и Волка на раскрашенном графе, ЮМТ 2025", "kind": { "primary": "olympiad_problem", "secondary": [ "graph_in_statement", "application" ] }, "language": "ru", "authors": [ { "name": "Дидин М. А.", "status": "source_verified" } ], "problem_profile": { "objects": [ "edge_colored_graph", "pursuit_evasion_game", "game_state_graph" ], "methods": [ "retrograde_analysis", "winning_region_fixed_point", "strategy" ], "transformations": [ "two_token_game_to_state_game" ], "goal": [ "winning_strategy", "classification" ], "auxiliary_graph_type": [ "directed_state_graph" ], "invariants": [ "winning_region" ], "keywords": [ "yumt", "2025_grand_round4_problem3", "yumt_2025" ], "status": "ai_checked" }, "statements": { "original": [ { "id": "stmt-original", "title": "Оригинальная формулировка", "text": "Заяц и Волк играют в игру. Волк рисует граф, содержащий более одной вершины, и красит его рёбра в красный и синий цвет.\nПосле этого Заяц ставит в какие-то две вершины красную и синюю фишку и выбирает, какая из них достанется ему, а какая — Волку.\nЗатем игроки ходят по очереди, первым ходит Волк; за ход игрок может передвинуть свою фишку по ребру цвета этой фишки или пропустить ход.\nВолк выигрывает, если после нескольких ходов фишки окажутся в одной вершине.\nДля каких графов Волк может гарантированно выиграть?", "source_id": "src-yumt-2025-grand-round4-problem3-official", "status": "ai_checked", "self_contained": { "status": "ai_checked" }, "definition_ids": [ "simple_graph" ] } ], "graph_theory": [], "olympiad_reformulations": [] }, "ideas": [ { "id": "idea-first-move-convention", "title": "Порядок первого хода", "text": "Если вместо Волка первым ходит Заяц, решение не меняется: после выбора начальных вершин и распределения фишек Заяц может своим первым ходом или пропуском добиться любого положения фишек, которое возможно к первому ходу Волка.", "tags": [ "goal_strategy_game" ], "status": "ai_checked" }, { "id": "idea-product-game-winning-region", "title": "Игра на парах вершин", "text": "Для фиксированного распределения фишек состояние задаётся упорядоченной парой \\((x,y)\\): где стоит фишка Волка и где стоит фишка Зайца. Выигрышные состояния Волка находятся обратной индукцией: состояние выигрышно, если у Волка есть ход, после которого любой не проигрывающий немедленно ответ Зайца снова ведёт в уже найденное выигрышное состояние.", "tags": [ "goal_strategy_game", "goal_algorithm" ], "status": "ai_checked" } ], "solutions": [ { "id": "sol-ai-retrograde-state-game", "title": "ИИ-решение: критерий через выигрышные состояния", "text": "Обозначим через \\(G_R\\) и \\(G_B\\) красный и синий подграфы; пропуск хода будем считать петлёй в каждой вершине. Зафиксируем два цвета \\(C,D\\): фишка Волка ходит по \\(G_C\\), фишка Зайца — по \\(G_D\\). Для упорядоченных пар различных вершин построим множества \\(W_i^{C,D}\\). Сначала \\(W_0^{C,D}=\\varnothing\\). Если \\(W_i^{C,D}\\) уже построено, включим в \\(W_{i+1}^{C,D}\\) все пары из \\(W_i^{C,D}\\), а также пару \\((x,y)\\), если существует вершина \\(x'\\in N_C[x]\\) такая, что либо \\(x'=y\\), либо для каждого \\(y'\\in N_D[y]\\) выполнено: \\(y'=x'\\) или \\((x',y')\\in W_i^{C,D}\\). Здесь \\(N_C[x]\\) — замкнутая окрестность в цвете \\(C\\), то есть возможные позиции фишки Волка после одного хода или пропуска; аналогично для \\(N_D[y]\\). Так как пар конечное число, процесс стабилизируется; обозначим предельное множество через \\(W^{C,D}\\). Утверждение: Волк может гарантированно выиграть на данном раскрашенном графе тогда и только тогда, когда все упорядоченные пары различных вершин принадлежат обоим множествам \\(W^{R,B}\\) и \\(W^{B,R}\\). Действительно, если начальная пара лежит в \\(W_i^{C,D}\\), Волк делает ход в соответствующую вершину \\(x'\\). Если он не поймал Зайца сразу, то любой ход Зайца либо сам приводит фишку Зайца в \\(x'\\), либо переводит игру в состояние из \\(W_{i-1}^{C,D}\\); индукция по \\(i\\) даёт стратегию Волка. Обратно, если состояние не попало в предельное множество, то после любого хода Волка, не являющегося немедленной поимкой, у Зайца есть ответ, который снова оставляет состояние вне предельного множества. Повторяя такой ответ, Заяц бесконечно избегает встречи. Остаётся учесть начальный выбор: Заяц выбирает две вершины, цвета фишек и то, какая фишка достанется Волку. Поэтому Волк должен выигрывать из любой пары и при назначении Волку красной фишки против синей, и при назначении ему синей фишки против красной; это ровно два условия выше.", "idea_ids": [ "idea-product-game-winning-region" ], "standard_idea_ids": [ "invariant", "induction" ], "status": "ai_checked", "definition_ids": [ "simple_graph" ], "repair_status": "high_reasoning_checked_2026_05_17" } ], "difficulty": { "main": "regional", "local_score": 6, "comment": "Импортировано из проверенной архивной карточки ЮМТ 2025_grand_round4_problem3.md; этап: Гранд-лига, четвёртый тур.", "status": "ai_checked" }, "tags": [ "coloring", "goal_strategy_game", "goal_characterization", "goal_algorithm" ], "sources": [ { "source_id": "src-yumt-2025-grand-round4-problem3-official", "role": "problem_and_solutions_official", "status": "source_verified" } ], "editorial": { "created_by": "ai", "created_at": "2026-04-25", "review_status": "ai_checked", "public_ready": true, "notes": [ "Импортировано из проверенной рабочей карточки ЮМТ 2025_grand_round4_problem3.md.", "2026-04-27: неоднозначность первоисточника разрешена редакторски: первым ходит Волк; добавлена отдельная идея о неизменности решения при первом ходе Зайца.", "2026-05-05: веб-поиск нашёл атрибуцию в архиве журнала «Квант»: задача М2877, автор Дидин М. А.; официального решения в открытом поиске не найдено. Добавлено ИИ-решение-критерий через ретроградный анализ конечной игры.", "2026-05-17: high-reasoning проверка закрыла критерий: множество выигрышных состояний построено как конечная монотонная ретроградная процедура; доказаны обе стороны стратегии Волка и Зайца." ], "relations_status": "deep_done", "graph_theory_duplicate_removed": true, "solution_classification": { "type": "official_complete_or_near_complete", "label": "официальное полное/почти полное", "status": "ai_checked", "confidence": 0.78, "basis": "агентский аудит средней сложности", "notes": "Метаданные источника указывают на архивное или официальное решение; решение проверено.", "audit_source": "agent-russian-archives.json" } } }