{ "id": "usamo-2004-p4-black-path-grid-game", "title": "Чёрный путь на сетке 6x6 после игры, USAMO 2004 P4", "kind": { "primary": "olympiad_problem", "secondary": [ "graph_in_statement", "application" ] }, "language": "ru", "authors": [ { "name": "Melanie Wood", "status": "source_verified" } ], "problem_profile": { "objects": [ "grid_board", "cell_adjacency_graph", "top_bottom_path", "pairing_strategy" ], "methods": [ "invariant_strategy", "pairing_strategy", "separator_construction" ], "transformations": [ "black_cells_to_grid_path_problem" ], "goal": [ "winning_strategy" ], "auxiliary_graph_type": [ "grid_graph" ], "invariants": [ "forbidden_cells_never_black", "top_bottom_separation" ], "keywords": [ "usamo_2004_p4", "grid_path_game", "separator_strategy" ], "status": "ai_checked" }, "statements": { "original": [ { "id": "stmt-original", "title": "Игра на таблице 6x6", "text": "Алиса и Боб по очереди вписывают в пустые клетки таблицы \\(6 \\times 6\\) попарно различные рациональные числа; первой ходит Алиса. После заполнения таблицы в каждой строке закрашивается в чёрный цвет клетка с максимальным числом. Алиса выигрывает, если затем может провести путь из чёрных клеток от верхней стороны таблицы до нижней, переходя между клетками, имеющими общую сторону или вершину. Если такого пути нет, выигрывает Боб. Докажите, у кого есть выигрышная стратегия.", "source_id": "src-usamo-2004-p4-aops-wiki", "status": "ai_checked", "self_contained": { "status": "ai_checked" }, "definition_ids": [] } ], "graph_theory": [], "olympiad_reformulations": [] }, "ideas": [ { "id": "idea-forbidden-squares", "title": "Сделать заранее выбранные клетки невозможными максимумами", "text": "В каждой строке Боб выбирает три запрещённые клетки и попарно связывает их с тремя оставшимися клетками той же строки. Ответом Боба в паре можно всегда сделать число в незапрещённой клетке больше числа в запрещённой, поэтому запрещённая клетка не станет чёрной.", "tags": [ "extremal_choice" ], "status": "ai_checked" }, { "id": "idea-staircase-separator", "title": "Лестничный барьер разрезает все верх-низ пути", "text": "Достаточно, чтобы среди запрещённых клеток были `(1,1)`, `(2,1),(2,2)`, `(3,2),(3,3)`, `(4,3),(4,4)`, `(5,4),(5,5)`, `(6,5),(6,6)`. Любой путь из верхней строки в нижнюю, переходящий между соседними по стороне или вершине клетками, обязан пересечь эту лестницу.", "tags": [ "extremal_choice" ], "status": "ai_checked" } ], "solutions": [ { "id": "sol-bob-useless-squares", "title": "Выигрышная стратегия Боба через запрещённые клетки", "text": "Покажем, что выигрывает Боб.\n\nБоб заранее объявляет запрещёнными следующие клетки. В строке `1` это столбцы `1,2,3`; в строке `2` — `1,2,3`; в строке `3` — `2,3,4`; в строке `4` — `3,4,5`; в строке `5` — `4,5,6`; в строке `6` — `4,5,6`. В каждой строке он произвольно разбивает три запрещённые и три незапрещённые клетки на пары, каждая пара лежит в одной строке и содержит одну запрещённую и одну незапрещённую клетку.\n\nСтратегия Боба такова. Если Алиса пишет число `x` в одной клетке некоторой пары, Боб немедленно пишет число в другой клетке этой пары. Если клетка Алисы была запрещённой, Боб выбирает рациональное число больше `x`; если клетка Алисы была незапрещённой, Боб выбирает рациональное число меньше `x`. Это всегда возможно, потому что между рациональными числами нет ближайших соседей и занято лишь конечное число значений. В итоге в каждой паре число в незапрещённой клетке больше числа в запрещённой. Поэтому ни одна запрещённая клетка не может быть максимумом своей строки: в той же строке у неё есть парная незапрещённая клетка с большим числом.\n\nОстаётся доказать, что незапрещённые клетки не могут содержать путь сверху вниз. Уже подмножество запрещённых клеток\n`(1,1)`, `(2,1),(2,2)`, `(3,2),(3,3)`, `(4,3),(4,4)`, `(5,4),(5,5)`, `(6,5),(6,6)` образует лестничный барьер. Действительно, поскольку после игры в каждой строке ровно одна чёрная клетка, верх-низ путь из чёрных клеток должен проходить через строки `1,2,...,6` по порядку; если его клетка в строке `r` стоит в столбце `c_r`, то соседство по стороне или вершине даёт `|c_{r+1}-c_r|<=1`.\n\nЕсли путь избегает барьера, то из строки `1` он обязан начать со столбца `c_1>=2`. Тогда в строке `2` из-за условия соседства `c_2>=1`, но столбцы `1` и `2` запрещены, значит `c_2>=3`. Далее та же индукция даёт `c_3>=4`, `c_4>=5`, `c_5>=6`. При переходе в строку `6` получаем `c_6>=5`, а в шестой строке оба столбца `5` и `6` запрещены; противоречие. Значит, чёрного пути от верхней стороны к нижней нет, и Боб выигрывает.", "idea_ids": [ "idea-forbidden-squares", "idea-staircase-separator" ], "standard_idea_ids": [ "extremal_choice" ], "status": "ai_checked", "definition_ids": [ "path" ] }, { "id": "sol-bob-shifted-row-pairing", "title": "Та же стратегия в форме парной защиты строк", "text": "Выигрышная стратегия Боба состоит не в выборе чисел по абсолютной величине, а в заранее заданных парах клеток. В каждой строке он объявляет запрещёнными три клетки: в строках `1,2` это столбцы `1,2,3`, в строке `3` — `2,3,4`, в строке `4` — `3,4,5`, в строках `5,6` — `4,5,6`. Каждую запрещённую клетку он парует с одной незапрещённой клеткой той же строки. Если Алиса играет в запрещённую клетку пары, Боб отвечает большим рациональным числом в её незапрещённой паре; если Алиса играет в незапрещённую клетку, Боб отвечает меньшим рациональным числом в запрещённой. Поэтому в каждой паре запрещённая клетка меньше незапрещённой и не может стать максимумом строки.\n\nСреди запрещённых клеток содержится лестница `(1,1)`, `(2,1),(2,2)`, `(3,2),(3,3)`, `(4,3),(4,4)`, `(5,4),(5,5)`, `(6,5),(6,6)`. Любой путь чёрных клеток сверху вниз должен проходить по одной чёрной клетке в каждой строке; если их столбцы равны `c_1,...,c_6`, то соседство по стороне или вершине требует `|c_{r+1}-c_r|<=1`. Избегая лестницы, получаем последовательно `c_1>=2`, затем `c_2>=3`, `c_3>=4`, `c_4>=5`, `c_5>=6`; после этого в шестой строке путь должен иметь `c_6>=5`, но столбцы `5` и `6` там запрещены. Противоречие. Значит, Боб гарантирует отсутствие чёрного верх-низ пути.", "idea_ids": [ "idea-forbidden-squares", "idea-staircase-separator" ], "standard_idea_ids": [ "extremal_choice" ], "status": "ai_checked", "definition_ids": [ "path" ] } ], "difficulty": { "main": "national_final_medium", "local_score": 6, "comment": "Игровая задача, где графовый путь стоит уже в условии, а решение строит парную стратегию и разделяющий узор.", "status": "ai_checked" }, "tags": [ "extremal_choice", "goal_strategy_game" ], "properties": { "central_method": { "value": [ "pairing_strategy", "separator_construction" ], "status": "ai_checked" } }, "sources": [ { "source_id": "src-usamo-2004-p4-aops-wiki", "role": "community_wiki_statement_and_solutions", "status": "source_verified" } ], "editorial": { "created_by": "ai", "created_at": "2026-04-24", "review_status": "ai_checked", "public_ready": true, "graph_theory_absent_reason": "Графовая структура используется в условии и решении, но отдельная graph_theory-формулировка была бы косметическим пересказом клеточного пути.", "graph_theory_duplicate_removed": true, "notes": [ "2026-05-17: карточка закрыта самодостаточной стратегией Боба; явно заданы пары ходов и доказано, что лестничный барьер отделяет верх от низа при королевской смежности." ], "relations_status": "deep_done", "solution_classification": { "type": "unofficial_published", "label": "опубликованное неофициальное", "status": "ai_checked", "confidence": 0.78, "basis": "агентский аудит средней сложности", "notes": "Карточка поддержана опубликованным неофициальным wiki-/форумным источником; решение переписано локально и самодостаточно.", "audit_source": "agent-imo-us-classical.json" } } }