{ "id": "kolmogorov-2014-round1-complete-graph-orientation-game", "title": "Игра в ориентацию рёбер полного графа, Кубок Колмогорова 2014", "kind": { "primary": "olympiad_problem", "secondary": [ "graph_in_statement" ] }, "language": "ru", "authors": [ { "name": "?", "status": "needs_human_review" } ], "problem_profile": { "objects": [ "complete_graph", "directed_graph", "directed_path", "cycle" ], "methods": [ "strategy", "longest_path", "counting" ], "transformations": [], "goal": [ "winning_strategy" ], "auxiliary_graph_type": [], "invariants": [], "keywords": [ "kolmogorov", "kolmogorov_2014", "round_1_higher_league" ], "status": "ai_checked" }, "statements": { "original": [ { "id": "stmt-original", "title": "Оригинальная формулировка", "text": "Дан полный неориентированный граф на 2014 вершинах. Два игрока по очереди ориентируют ещё не ориентированные рёбра. За один ход первый игрок ориентирует одно ребро, а второй — от 1 до 1000 рёбер. Когда все рёбра ориентированы, первый игрок выигрывает, если получившийся ориентированный граф содержит простой ориентированный цикл; иначе выигрывает второй игрок. Определите победителя при правильной игре.", "source_id": "src-kolmogorov-2014-official", "status": "ai_checked", "self_contained": { "status": "ai_checked" }, "definition_ids": [ "simple_graph", "complete_graph", "directed_graph", "cycle" ] } ], "graph_theory": [], "olympiad_reformulations": [] }, "ideas": [ { "id": "idea-graph-role", "title": "Графовая роль", "text": "Карточка фиксирует задачу как явно графовую: графовая модель присутствует уже в условии, а в конце получается турнир — ориентация полного графа.", "tags": [ "tournaments" ], "status": "ai_checked" }, { "id": "idea-longest-chain-counting", "title": "Длинная цепочка и подсчёт хорд", "text": "Первый игрок может каждый раз удлинять максимальную ориентированную цепочку на одну вершину. Чтобы не дать ему замкнуть цикл обратной хордой, второй должен успевать ориентировать все ребра между вершинами этой цепочки, но к длине 2003 таких ребер уже больше, чем могло быть ориентировано за 2002 раунда.", "tags": [ "tournaments", "goal_strategy_game" ], "status": "ai_checked" } ], "solutions": [ { "id": "sol-ai-longest-chain-counting", "title": "Стратегия первого через длинную цепочку", "text": "Выигрывает первый игрок.\n\nБудем называть цепочкой ориентированный путь \\(v_1\\to v_2\\to\\cdots\\to v_k\\), составленный из уже ориентированных ребер. Если второй игрок когда-либо сам создал ориентированный цикл, то этот цикл останется до конца игры и первый уже выигрывает. Поэтому дальше считаем, что после ходов второго ориентированных циклов нет.\n\nСначала докажем лемму: после хода второго, если самая длинная цепочка имеет меньше 2014 вершин, первый может одним ходом получить более длинную цепочку. Пусть \\(v_1\\to v_2\\to\\cdots\\to v_k\\) — одна из самых длинных цепочек, и пусть \\(a\\) — вершина вне нее. Если ребро между \\(a\\) и \\(v_1\\) еще не ориентировано, первый направляет его как \\(a\\to v_1\\) и удлиняет цепочку слева; если оно уже направлено \\(a\\to v_1\\), такая более длинная цепочка уже была бы. Значит, когда удлинить слева нельзя, обязательно стоит стрелка \\(v_1\\to a\\). Аналогично, когда удлинить справа нельзя, ребро между \\(a\\) и \\(v_k\\) обязательно направлено как \\(a\\to v_k\\).\n\nРассмотрим индексы \\(i\\), для которых ребро между \\(v_i\\) и \\(a\\) не направлено из \\(a\\) в \\(v_i\\). Такой индекс есть, потому что \\(v_1\\to a\\), а \\(i=k\\) не подходит, потому что \\(a\\to v_k\\). Возьмем наибольший такой индекс \\(i\\). Тогда ребро между \\(a\\) и \\(v_{i+1}\\) уже направлено как \\(a\\to v_{i+1}\\). Если бы ребро между \\(v_i\\) и \\(a\\) уже было направлено как \\(v_i\\to a\\), цепочка \\(v_1\\to\\cdots\\to v_i\\to a\\to v_{i+1}\\to\\cdots\\to v_k\\) уже была бы длиннее исходной. Значит, это ребро еще свободно, и первый направляет его как \\(v_i\\to a\\), вставляя \\(a\\) в цепочку. Лемма доказана.\n\nИз леммы следует индукцией, что после 2002-го хода первого существует цепочка хотя бы на 2003 вершинах. Пусть после ответного хода второго такая цепочка равна \\(v_1\\to v_2\\to\\cdots\\to v_{2003}\\) или длиннее. Если между двумя ее вершинами \\(v_i\\) и \\(v_j\\), где \\(i