{ "id": "vjimc-2022-cat1-p4-stone-game-state-graph", "title": "Игра с цветными камнями и граф состояний, VJIMC 2022 I.4", "kind": { "primary": "olympiad_problem", "secondary": [ "graph_in_solution", "application" ] }, "language": "ru", "authors": [ { "name": "Leszek Pieniążek", "status": "source_verified" } ], "problem_profile": { "objects": [ "three_player_game", "finite_state_graph", "directed_cycle", "modular_state" ], "methods": [ "invariant_modulo_three", "state_graph_analysis", "strategy_stealing_on_cycle" ], "transformations": [ "stone_counts_to_directed_state_graph" ], "goal": [ "determine_game_outcome" ], "auxiliary_graph_type": [ "directed_state_graph" ], "invariants": [ "total_modulo_three", "linear_form_modulo_three", "turn_modulo_three" ], "keywords": [ "vjimc_2022_cat1_p4", "game_graph", "state_graph", "modulo_three" ], "status": "ai_checked" }, "statements": { "original": [ { "id": "stmt-original", "title": "Условие", "text": "В коробке лежат соответственно \\(31\\), \\(41\\) и \\(59\\) камней красного, зелёного и синего цветов. Три игрока в футболках этих трёх цветов ходят по очереди. За ход игрок либо удаляет из коробки три камня одного цвета, либо заменяет два камня разных цветов двумя камнями третьего цвета. Игра заканчивается, когда все камни в коробке имеют один цвет; победителем считается игрок, цвет футболки которого совпадает с этим цветом. Если игроки играют оптимально, можно ли определить, закончится ли игра и кто выиграет, в зависимости от того, кто ходит первым?", "source_id": "src-vjimc-2022-cat1-p4-official", "status": "source_verified", "self_contained": { "status": "ai_checked" }, "definition_ids": [] } ], "graph_theory": [], "olympiad_reformulations": [] }, "ideas": [ { "id": "idea-two-modular-invariants", "title": "Два инварианта оставляют только красную победу", "text": "Сумма камней и линейная форма \\(r+2g\\) по модулю 3 сохраняются при обоих типах ходов. Для начальных чисел оба остатка равны 2, поэтому финальная одноцветная позиция может быть только красной.", "tags": [ "invariant", "process_invariant" ], "status": "ai_checked" }, { "id": "idea-small-state-graph", "title": "Остаточная игра сводится к малому графу состояний", "text": "Красный игрок уменьшает число камней ходами первого типа, пока остаётся 2 или 5 камней. После этого все возможные состояния и переходы между ними образуют маленький ориентированный граф; единственная бесконечная игра удерживает красного на вершине \\((1,2,2)\\).", "tags": [ "graph_in_solution", "goal_strategy_game" ], "status": "ai_checked" } ], "solutions": [ { "id": "sol-official-state-graph", "title": "Решение через инварианты и граф малых состояний", "text": "Пусть после некоторого хода в коробке лежат \\(r\\), \\(g\\), \\(b\\) красных, зелёных и синих камней. Рассмотрим две величины по модулю 3:\n\\[\nN=r+g+b,\\qquad D=r+2g.\n\\]\nУдаление трёх камней одного цвета не меняет ни \\(N\\), ни \\(D\\) по модулю 3. При замене двух разных цветов двумя камнями третьего цвета изменения \\(D\\) равны соответственно \\(-3\\), \\(3\\) или \\(0\\), а \\(N\\) вообще не меняется. Значит, оба остатка инвариантны.\n\nВ начале \\(N=31+41+59=131\\equiv 2\\pmod 3\\) и \\(D=31+2\\cdot 41=113\\equiv 2\\pmod 3\\). Если игра закончилась, то два из чисел \\(r,g,b\\) равны нулю. Синий финал дал бы \\(D\\equiv 0\\), зелёный финал дал бы \\(D\\equiv 2N\\equiv 1\\), и оба варианта невозможны. Красный финал возможен по остаткам: тогда \\(r\\equiv 2\\pmod 3\\). Поэтому, если игра заканчивается, выигрывает только красный. Значит, красный стремится завершить игру, а два других игрока стремятся играть бесконечно.\n\nПокажем стратегию красного, если он не ходит первым. Когда наступает ход красного, он удаляет три камня какого-нибудь цвета, если это возможно, а если уже может завершить игру, завершает её. После каждого такого хода общее число камней уменьшается на 3. Поэтому рано или поздно, перед ходом красного или сразу после него, игра попадает в область, где всего 2 или 5 камней, потому что общий остаток всегда равен 2.\n\nПри \\(r+g+b=2\\) или \\(5\\) и инвариантах \\(N\\equiv D\\equiv 2\\pmod 3\\) возможны только следующие упорядоченные состояния:\n\\[\n(0,1,1),\\ (2,0,0),\\ (0,1,4),\\ (0,4,1),\\ (1,2,2),\\ (2,0,3),\\ (2,3,0),\\ (3,1,1),\\ (5,0,0).\n\\]\nЗдесь \\((2,0,0)\\) и \\((5,0,0)\\) уже являются красным финалом или ведут к нему удалением трёх красных камней. Остальные переходы этого малого графа, которые важны для стратегии, таковы:\n\\[\n(0,1,1)\\to(2,0,0),\n\\]\n\\[\n(0,1,4)\\to(0,1,1)\\text{ или }(2,0,3),\\qquad\n(0,4,1)\\to(0,1,1)\\text{ или }(2,3,0),\n\\]\n\\[\n(2,0,3)\\to(2,0,0)\\text{ или }(1,2,2),\\qquad\n(2,3,0)\\to(2,0,0)\\text{ или }(1,2,2),\n\\]\n\\[\n(3,1,1)\\to(0,1,1),\\ (2,0,3),\\ (2,3,0)\\text{ или }(5,0,0),\n\\]\n\\[\n(1,2,2)\\to(0,1,4),\\ (0,4,1)\\text{ или }(3,1,1).\n\\]\nЭта таблица - официальный граф состояний, записанный без рисунка: ребро означает один допустимый ход.\n\nТеперь разберём стратегические следствия таблицы по вершинам. Если красный ходит из \\((0,1,1)\\), он заменяет зелёный и синий камни двумя красными и получает финал \\((2,0,0)\\). Из \\((2,0,3)\\) он удаляет три синих камня, из \\((2,3,0)\\) удаляет три зелёных камня, а из \\((3,1,1)\\) заменяет зелёный и синий камни двумя красными и получает финал \\((5,0,0)\\). Из \\((0,1,4)\\) красный удаляет три синих камня и переводит игру в \\((0,1,1)\\); из \\((0,4,1)\\) он удаляет три зелёных камня и снова переводит игру в \\((0,1,1)\\). В состоянии \\((0,1,1)\\) у следующего игрока единственный ход ведёт в красный финал \\((2,0,0)\\), поэтому эти две позиции тоже проиграны для зелёного и синего.\n\nЕдинственная малая позиция, где красный на своём ходе не может сразу или за один вынужденный ответ навязать красный финал, - это \\((1,2,2)\\). Из неё любой ход красного ведёт в одну из трёх позиций \\((0,1,4)\\), \\((0,4,1)\\), \\((3,1,1)\\), и два других игрока могут вернуть игру в \\((1,2,2)\\) за свои следующие два хода:\n\\[\n(1,2,2)\\to(0,1,4)\\to(2,0,3)\\to(1,2,2),\n\\]\n\\[\n(1,2,2)\\to(0,4,1)\\to(2,3,0)\\to(1,2,2),\n\\]\n\\[\n(1,2,2)\\to(3,1,1)\\to(2,0,3)\\to(1,2,2).\n\\]\nЗначит, если каждый раз при попадании в \\((1,2,2)\\) ходит красный, зелёный и синий могут поддерживать бесконечную игру.\n\nОсталось определить, чей ход будет в этой вершине. Начальные остатки равны \\((31,41,59)\\equiv(1,2,2)\\pmod 3\\). Ходы первого типа не меняют упорядоченный вектор остатков. Для ходов второго типа среди остатков, совместимых с \\(N\\equiv D\\equiv2\\pmod3\\), возможны только три вершины \\((1,2,2)\\), \\((0,1,1)\\), \\((2,0,0)\\), и каждый ход второго типа переводит их по циклу\n\\[\n(1,2,2)\\to(0,1,1)\\to(2,0,0)\\to(1,2,2).\n\\]\nПоэтому число ходов второго типа между двумя появлениями остатка \\((1,2,2)\\) кратно \\(3\\). Фактическая малая позиция \\((1,2,2)\\) имеет ровно \\(5\\) камней; чтобы дойти от \\(131\\) камня до \\(5\\) камней, нужно удалить \\(126\\) камней, то есть сделать ровно \\(42\\) хода первого типа. Это число тоже кратно \\(3\\). Следовательно, к моменту появления ключевой позиции \\((1,2,2)\\) общее число сделанных ходов кратно \\(3\\), и ходит тот же игрок, который начинал игру.\n\nЕсли первым ходил красный, то в \\((1,2,2)\\) снова ходит красный, и два других игрока могут бесконечно возвращать игру в эту позицию; при оптимальной игре партия не закончится. Если первым ходил зелёный или синий, то в \\((1,2,2)\\) ходит не красный. Какой бы ход он ни сделал, дальше возможны только два случая: либо следующий ход уже принадлежит красному в одной из позиций \\((0,1,4)\\), \\((0,4,1)\\), \\((3,1,1)\\), либо перед красным ещё ходит второй некрасный игрок и переводит игру в одну из позиций \\((0,1,1)\\), \\((2,0,3)\\), \\((2,3,0)\\), \\((3,1,1)\\) или сразу в красный финал. Все перечисленные позиции выигрышны для красного по разобранным выше ходам. Значит, при первом ходе зелёного или синего победит красный, а при первом ходе красного игра бесконечна.", "idea_ids": [ "idea-two-modular-invariants", "idea-small-state-graph" ], "standard_idea_ids": [ "invariant" ], "status": "ai_checked", "definition_ids": [ "directed_graph", "cycle" ] } ], "difficulty": { "main": "national_final_medium", "local_score": 8, "comment": "VJIMC 2022 Category I Problem 4; граф не в условии, но официальный разбор конечных состояний и бесконечной петли является центральной частью решения.", "status": "ai_checked" }, "tags": [ "graph_in_solution", "process_invariant", "invariant", "goal_strategy_game" ], "properties": { "central_method": { "value": [ "modular_invariants", "directed_state_graph" ], "status": "ai_checked" } }, "sources": [ { "source_id": "src-vjimc-2022-cat1-p4-official", "role": "problem_and_solutions_official", "status": "source_verified" } ], "editorial": { "created_by": "ai", "created_at": "2026-05-02", "review_status": "ai_checked", "public_ready": true, "notes": [ "Добавлено как graph_in_solution: граф состояний явно используется в официальном решении; самостоятельную graph_theory-формулировку не добавлял, чтобы не делать искусственную оболочку.", "High-reasoning проверка 2026-05-04: официальный источник сверён, таблица всех малых упорядоченных состояний и переходов пересчитана, стратегический вывод по циклу \\((1,2,2)\\) развернут." ], "relations_status": "reviewed_no_links", "graph_theory_absent_reason": "Граф состояний является инструментом решения, а не самостоятельной переформулировкой условия.", "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" } } }