{ "id": "imo-2024-c4-turbo-grid-monsters-three-attempts-strategy", "title": "Три попытки Турбо-улитки достаточны, IMO 2024 P5 / Shortlist C4", "kind": { "primary": "olympiad_problem", "secondary": [ "application" ] }, "language": "ru", "authors": [ { "name": "?", "status": "needs_human_review" } ], "problem_profile": { "objects": [ "grid_graph", "hidden_obstacles", "paths", "adaptive_strategy" ], "methods": [ "constructive_strategy", "case_analysis", "safe_corridor" ], "transformations": [ "board_to_grid_graph", "visited_cells_to_safe_set" ], "goal": [ "upper_bound_on_attempts", "guaranteed_path_to_last_row" ], "auxiliary_graph_type": [], "invariants": [ "one_monster_per_middle_row", "at_most_one_monster_per_column", "known_safe_cells" ], "keywords": [ "imo_2024_p5", "turbo_snail", "grid_path", "hidden_monsters", "three_attempts" ], "status": "ai_checked" }, "statements": { "original": [ { "id": "stmt-original-three-attempts", "title": "Улитка, доска и три попытки", "text": "Улитка Турбо играет на доске с \\(2024\\) строками и \\(2023\\) столбцами. В \\(2022\\) клетках спрятаны монстры. Сначала Турбо не знает, где они находятся, но знает, что ровно по одному монстру стоит в каждой строке, кроме первой и последней, и что в каждом столбце находится не более одного монстра. Турбо делает попытки пройти из первой строки в последнюю. В каждой попытке он выбирает любую клетку первой строки, а затем многократно переходит в соседнюю по стороне клетку; ему разрешено возвращаться в уже посещённые клетки. Если Турбо попадает в клетку с монстром, попытка заканчивается, и его возвращают в первую строку. Монстры не двигаются, а Турбо запоминает, в каких посещённых клетках есть монстры и в каких их нет. Если он достигает любой клетки последней строки, попытка заканчивается, и игра выиграна. Докажите, что у Турбо есть стратегия, гарантирующая победу не позже третьей попытки.", "source_id": "src-imo-2024-problems-eng", "status": "ai_checked", "self_contained": { "status": "ai_checked" }, "definition_ids": [ "path" ] } ], "graph_theory": [], "olympiad_reformulations": [] }, "ideas": [ { "id": "idea-row-two-scan", "title": "Сканирование второй строки", "text": "Первая попытка идёт по второй строке и обязательно находит единственного монстра этой строки, после чего его столбец ниже становится безопасным.", "tags": [ "goal_strategy_game", "connectivity" ], "status": "ai_checked" }, { "id": "idea-symmetric-or-edge-detour", "title": "Два обхода или крайний коридор", "text": "Если найденный монстр не на краю, две попытки по соседним столбцам сводят риск к двум клеткам одной строки; если он на краю, диагональная попытка либо сразу доходит до низа, либо оставляет безопасный третий обход по краевому столбцу.", "tags": [ "goal_strategy_game", "goal_classification" ], "status": "ai_checked" } ], "solutions": [ { "id": "sol-three-attempt-strategy", "title": "Конструктивная стратегия за три попытки", "text": "В первой попытке Турбо идёт по пути \\((1,1),(2,1),(2,2),\\ldots,(2,2023)\\), тем самым находит монстра во второй строке. Пусть он стоит в \\((2,i)\\). Если \\(2\\le i\\le2022\\), то во второй и третьей попытках Турбо идёт по путям через \\((2,i-1),(3,i-1),(3,i),(4,i),\\ldots,(2024,i)\\) и через \\((2,i+1),(3,i+1),(3,i),(4,i),\\ldots,(2024,i)\\). В столбце \\(i\\) ниже монстров нет, потому что монстр этого столбца уже найден во второй строке. Единственные новые опасные точки перед выходом в безопасный столбец — \\((3,i-1)\\) и \\((3,i+1)\\); они лежат в одной строке, где монстр только один, поэтому хотя бы одна из двух попыток успешна. Если монстр второй строки стоит на краю, скажем в \\((2,1)\\), то во второй попытке Турбо идёт от \\((1,2)\\) по ломаной \\((2,2),(2,3),(3,3),(4,4),\\ldots,(2023,2023),(2024,2023)\\). Если монстра нет, он уже победил. Иначе пусть первый встреченный монстр — \\((r,c)\\), где по форме пути \\(c=r\\) или \\(c=r+1\\). В третьей попытке Турбо повторяет безопасную начальную часть до строки \\(r-1\\), затем проходит по строке \\(r\\) влево до первого столбца и дальше спускается по первому столбцу. Начальная часть безопасна, клетки строки \\(r\\) левее \\((r,c)\\) безопасны, потому что в строке \\(r\\) только один монстр, а первый столбец ниже безопасен, потому что его единственный монстр уже найден в \\((2,1)\\). Поэтому третья попытка достигает последней строки. Случай монстра в \\((2,2023)\\) симметричен.", "idea_ids": [ "idea-row-two-scan", "idea-symmetric-or-edge-detour" ], "standard_idea_ids": [ "extremal_choice" ], "status": "ai_checked", "definition_ids": [ "path" ] } ], "difficulty": { "main": "imo_p2_p5", "local_score": 10, "comment": "Верхняя оценка для IMO 2024 P5 / Shortlist C4; конструкция использует найденный монстр второй строки для построения безопасных коридоров.", "status": "ai_checked" }, "tags": [ "connectivity", "goal_strategy_game" ], "properties": { "central_method": { "value": [ "constructive_path_strategy", "case_analysis" ], "status": "ai_checked" } }, "sources": [ { "source_id": "src-imo-2024-problems-eng", "role": "official_problem_statement", "status": "source_verified" }, { "source_id": "src-imo-2024-shortlist", "role": "official_solution", "status": "source_verified" }, { "source_id": "src-aops-imo-2024-p5", "role": "community_wiki", "status": "source_verified" } ], "editorial": { "created_by": "ai", "created_at": "2026-04-20", "review_status": "needs_human_review", "public_ready": false, "graph_theory_absent_reason": "Графовая структура используется в официальном решении, но не является самостоятельной переформулировкой исходного условия.", "graph_theory_duplicate_removed": true, "notes": [ "Выделено из составной карточки imo-2024-c4-turbo-grid-monsters." ], "relations_status": "deep_done", "solution_classification": { "type": "official_complete_or_near_complete", "label": "официальное полное/почти полное", "status": "ai_checked", "confidence": 0.78, "basis": "агентский аудит средней сложности", "notes": "В карточке есть официальные, шортлистные или справочные источники и проверенное ИИ решение.", "audit_source": "agent-imo-us-classical.json" } } }