{ "id": "simon-marais-2023-c4-reverse-chess-grid-pursuit", "title": "Обратные шахматы: порог для погони королей за ладьёй на решётке, SMMC 2023 C4", "kind": { "primary": "olympiad_problem", "secondary": [ "graph_in_statement", "game", "application" ] }, "language": "ru", "authors": [ { "name": "?", "status": "needs_human_review" } ], "problem_profile": { "objects": [ "rectangular_grid", "king_move_graph", "rook_visibility_graph", "pursuit_evasion_game", "moving_barrier" ], "methods": [ "safe_row_evasion", "pigeonhole_safe_row", "barrier_strategy", "guarded_columns", "monotone_sweep" ], "transformations": [ "chessboard_to_move_graphs", "board_position_to_pursuit_game" ], "goal": [ "find_capture_threshold" ], "auxiliary_graph_type": [ "grid_graph", "king_graph", "rook_visibility_graph" ], "invariants": [ "safe_row_distance_margin", "rook_column_blocked_by_new_king", "rook_below_moving_barrier", "assigned_double_columns" ], "keywords": [ "smmc_2023_c4", "reverse_chess", "king_rook_game", "grid_pursuit", "threshold_1012" ], "status": "ai_checked" }, "statements": { "original": [ { "id": "stmt-original", "title": "Условие", "text": "Пусть \\(k\\) — положительное целое число. Кейра и Роланд играют в обратные шахматы. Сначала Роланд выбирает положительное целое число \\(n>k/2023\\). Затем Кейра ставит \\(k\\) королей на \\(k\\) различных клеток шахматной доски с \\(2023\\) столбцами и \\(n\\) строками. После этого Роланд ставит ладью на свободную клетку. Игроки по очереди ходят любым числом своих фигур, возможно нулевым; первой ходит Кейра. Король ходит на одну клетку по горизонтали, вертикали или диагонали. Король не может ходить на клетку, занятую другим королём, но может взять ладью. Если Кейра за один ход двигает несколько королей, она двигает их по одному. Ладья Роланда ходит на любое число клеток по горизонтали или вертикали, не может брать королей и не может проходить через клетку, занятую королём. При каких \\(k\\) Кейра может гарантировать взятие ладьи независимо от ходов Роланда и от выбранного им \\(n\\)?", "source_id": "src-simon-marais-2023-C4-official", "status": "ai_checked", "self_contained": { "status": "ai_checked" }, "definition_ids": [], "distinct_from": [ "stmt-graph" ] } ], "graph_theory": [ { "id": "stmt-graph", "title": "Обратные шахматы: порог для погони королей за ладьёй на решётке, SMMC 2023 C4", "text": "Рассмотрим прямоугольную решётку из \\(2023\\) столбцов и \\(n\\) строк. Преследователи занимают различные вершины и за свой ход могут перейти в соседние по стороне или диагонали вершины, а беглец за свой ход может пройти по одной горизонтали или вертикали на любое расстояние, но его путь не должен проходить через занятую преследователем вершину. Беглец не удаляет преследователей, а преследователи выигрывают, если один из них переходит в вершину беглеца. Сначала беглец выбирает \\(n>k/2023\\), затем преследователи выбирают \\(k\\) стартовых вершин, затем беглец выбирает свободную стартовую вершину, после чего первым ходят преследователи. Найдите все \\(k\\), при которых у преследователей есть стратегия гарантированного захвата для любого выбора \\(n\\).", "status": "ai_checked", "self_contained": { "status": "ai_checked" }, "definition_ids": [ "simple_graph", "path" ], "distinct_from": [ "stmt-original" ] } ], "olympiad_reformulations": [] }, "ideas": [ { "id": "idea-safe-rows", "title": "При \\(k\\le1011\\) ладья уходит между безопасными строками", "text": "Роланд выбирает очень большое число строк. В любой текущей позиции есть строка, удалённая от всех королей на большой запас. Если в столбце ладьи нет короля, ладья вертикально уходит в такую строку; если король закрывает столбец, ладья сдвигается на два столбца, и тот же король уже не успевает закрыть следующий столбец.", "tags": [ "goal_strategy_game", "pigeonhole_principle" ], "status": "ai_checked" }, { "id": "idea-column-barrier", "title": "\\(1012\\) королей образуют движущийся барьер", "text": "Короли ставятся в верхней строке в нечётных столбцах \\(1,3,\\ldots,2023\\). Каждый король отвечает за один двухстолбцовый блок, а вся линия каждый ход спускается на строку ниже; король, чей блок содержит ладью, становится в её столбец и не даёт ладье перескочить через линию.", "tags": [ "graph_model", "goal_strategy_game", "invariant" ], "status": "ai_checked" } ], "solutions": [ { "id": "sol-threshold-1012", "title": "Порог равен \\(1012\\)", "text": "Ответ: \\(k\\ge1012\\).\n\nСначала докажем, что при \\(k\\le1011\\) Роланд может избегать взятия бесконечно долго. Он выбирает число строк \\(n>2027\\cdot1012\\), что, в частности, больше \\(k/2023\\). Назовём строку безопасной в текущий момент, если она удалена по номеру хотя бы на \\(1014\\) от каждой строки, в которой стоит король. Каждый король делает небезопасными не более \\(2027\\) строк, поэтому при \\(k\\le1011\\) всегда существует безопасная строка.\n\nРоланд ставит ладью в безопасную строку. После первого хода Кейры короли всё ещё не могут находиться в этой строке, и Роланд переводит ладью горизонтально в первый столбец. Далее он повторяет один и тот же приём. Если в текущем столбце ладьи нет короля, ладья ходит вертикально в какую-нибудь безопасную строку, существующую в текущей позиции. Такой ход разрешён, потому что в её столбце нет королей, через которые ладья могла бы упереться. Если же в текущем столбце есть король, Роланд ходит ладьёй на две клетки вправо.\n\nОдин и тот же король не может закрывать столбец ладьи два раза подряд в такой серии: за ход Кейры он меняет номер столбца не более чем на \\(1\\), а ладья только что ушла на \\(2\\) столбца. Значит, каждый случай с закрытым столбцом требует нового короля и потому случается не более \\(1011\\) раз, пока ладья идёт от первого столбца вправо через столбцы \\(1,3,5,\\ldots,2023\\). Вся серия до следующего вертикального ухода занимает не более \\(1012\\) ходов Роланда и не более \\(1013\\) ходов Кейры. Ладья начинала её в безопасной строке с запасом \\(1014\\), поэтому ни один король за это время не успевает дойти до строки ладьи и взять её. После вертикального ухода в новую безопасную строку тот же аргумент начинается заново. Следовательно, при \\(k\\le1011\\) Кейра не имеет гарантированной победы.\n\nТеперь докажем, что \\(1012\\) королей достаточно. Кейра изначально ставит королей в верхнюю строку в столбцы \\(1,3,5,\\ldots,2023\\). Обозначим их слева направо \\(K_1,\\ldots,K_{1012}\\). Для \\(i=1,\\ldots,1011\\) король \\(K_i\\) отвечает за столбцы \\(2i-1\\) и \\(2i\\), а \\(K_{1012}\\) отвечает за столбец \\(2023\\). Если после постановки ладьи она находится в верхней строке, то ближайший король берёт её первым ходом Кейры.\n\nОстаётся случай, когда ладья ниже верхней строки. Кейра поддерживает такой инвариант: все короли стоят в одной строке, каждый внутри своего назначенного блока столбцов, а ладья находится ниже этой строки и не может пройти через неё вверх. На своём ходе Кейра передвигает всех королей на одну строку вниз. Тот король, чей блок содержит текущий столбец ладьи, выбирает в следующей строке именно этот столбец; остальные короли остаются внутри своих блоков. Блоки не пересекаются, поэтому короли занимают разные клетки, а каждый такой ход является допустимым ходом короля.\n\nПосле этого в столбце ладьи на строке барьера стоит король. Ладья не может его взять и не может пройти через его клетку, поэтому своим следующим ходом она остаётся ниже линии королей. Если она когда-либо оказывается прямо под линией, то на следующем ходу соответствующий король переходит в её клетку и берёт её. Иначе линия королей продолжает спускаться на одну строку за ход. Так как доска имеет конечное число строк, бесконечно оставаться строго ниже спускающейся линии невозможно; перед нижним краем ладья окажется непосредственно под барьером и будет взята. Значит, при \\(k=1012\\), а тем более при любом большем \\(k\\), у Кейры есть выигрышная стратегия.", "idea_ids": [ "idea-safe-rows", "idea-column-barrier" ], "standard_idea_ids": [ "pigeonhole_principle", "invariant" ], "status": "ai_checked", "definition_ids": [ "simple_graph", "path" ] } ], "difficulty": { "main": "national_final_medium", "local_score": 6, "comment": "Стратегическая задача уровня SMMC C4: нижняя оценка требует аккуратно контролировать запас безопасных строк, а верхняя строит явный монотонный барьер из королей.", "status": "ai_checked" }, "tags": [ "graph_model", "goal_strategy_game", "construction", "invariant", "pigeonhole_principle" ], "properties": { "central_method": { "value": [ "goal_strategy_game", "construction", "invariant", "pigeonhole_principle" ], "status": "ai_checked" }, "typical_olympiad_use": { "value": "Для отрицательной части выбирается очень высокая доска и строка с большим запасом до всех преследователей; для положительной части преследователи образуют спускающийся барьер, перекрывающий каждый столбец ладьи.", "status": "ai_checked" } }, "sources": [ { "source_id": "src-simon-marais-2023-C4-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": [ "2026-05-04: сверено с официальным PDF SMMC 2023 solutions, Problem C4, pages 21-22: ответ \\(k\\ge1012\\), нижняя стратегия Роланда использует \\(n>2027\\cdot1012\\), безопасные строки с запасом \\(1014\\) и сдвиг ладьи на два столбца; верхняя стратегия Кейры использует королей в столбцах \\(1,3,\\ldots,2023\\) и движущийся вниз барьер.", "Предыдущий `public_ready: false` был оправдан: русскоязычные поля были повреждены mojibake-кодировкой, а доказательство было сжатым и не фиксировало официальные численные запасы." ], "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" } } }