{ "id": "cmo-2026-p3-grid-hamiltonian-snail", "title": "Игра на гамильтоновом пути решётки, CMO 2026 P3", "kind": { "primary": "olympiad_problem", "secondary": [ "graph_in_statement", "game" ] }, "language": "ru", "authors": [ { "name": "Canadian Mathematical Olympiad Committee", "note": "Официальные листы задач и решений CMS указывают олимпиаду, но не называют индивидуального автора задачи.", "status": "source_verified" } ], "problem_profile": { "objects": [ "square_grid_graph", "marked_vertices", "hamiltonian_path", "hamiltonian_cycle", "checkerboard_coloring" ], "methods": [ "minimax_strategy", "checkerboard_lower_bound", "hamiltonian_cycle_pairing", "reverse_traversal_averaging" ], "transformations": [ "cells_to_vertices", "snail_walk_to_hamiltonian_path", "monster_cells_to_marked_vertices" ], "goal": [ "exact_game_value" ], "auxiliary_graph_type": [ "even_square_grid_graph" ], "invariants": [ "checkerboard_bipartition", "paired_reverse_labels", "sum_of_opposite_traversal_scores" ], "keywords": [ "cmo_2026_p3", "canadian_mathematical_olympiad", "hamiltonian_path", "hamiltonian_cycle", "grid_graph", "minimax_score" ], "status": "ai_checked" }, "statements": { "original": [ { "id": "stmt-original", "title": "Условие задачи", "text": "Улитка Turbo играет в игру на доске с \\(2n\\) строками и \\(2n\\) столбцами. Есть \\(2n^2\\) чудовищ, которые сначала, зная всё о Turbo, выбирают \\(2n^2\\) различных клеток и занимают их. После этого Turbo выбирает любую клетку и помечает её числом \\(1\\). Начиная с этой клетки, Turbo затем проходит через все остальные \\(4n^2-1\\) клетки ровно по одному разу, помечая их по порядку числами \\(2,3,\\ldots,4n^2\\). Turbo ходит только между клетками с общей стороной и никогда не возвращается в уже посещённую клетку. Итоговый счёт равен сумме меток клеток с чудовищами. Чудовища стараются расположиться так, чтобы максимизировать счёт, а Turbo старается минимизировать счёт, зная расположение чудовищ. Найдите, в терминах \\(n\\), наибольший счёт, который чудовища могут гарантировать.", "source_id": "src-cmo-2026-official", "status": "ai_checked", "self_contained": { "status": "ai_checked" }, "definition_ids": [], "distinct_from": [ "stmt-graph" ] } ], "graph_theory": [ { "id": "stmt-graph", "title": "Игра на гамильтоновом пути решётки", "text": "Пусть \\(G\\) — квадратный решётчатый граф размера \\((2n)\\times(2n)\\), вершинами которого являются клетки доски \\(2n\\) на \\(2n\\), а рёбра соединяют клетки с общей стороной. Сначала выбирается множество \\(M\\subseteq V(G)\\) размера \\(2n^2\\). Затем выбирается гамильтонов путь в \\(G\\), и его вершины помечаются числами \\(1,2,\\ldots,4n^2\\) в порядке прохождения пути. Счёт равен сумме меток на вершинах из \\(M\\). Выбирающий \\(M\\) хочет максимизировать этот счёт, а выбирающий гамильтонов путь хочет минимизировать его после того, как увидит \\(M\\). Определите значение этой игры в терминах \\(n\\).", "status": "ai_checked", "self_contained": { "status": "ai_checked" }, "definition_ids": [ "hamiltonian_path" ], "distinct_from": [ "stmt-original" ] } ], "graph_hint_reformulations": [ { "id": "stmt-graph-hint-cycle-pairing", "text": "Для верхней оценки используйте гамильтонов цикл чётной квадратной решётки. Если одну отмеченную вершину выбрать начальной, то два гамильтоновых пути, полученные обходом цикла в двух противоположных направлениях, дают каждой другой отмеченной вершине дополняющие друг друга метки.", "status": "ai_checked", "self_contained": { "status": "ai_checked" }, "definition_ids": [ "hamiltonian_cycle", "hamiltonian_path" ], "distinct_from": [ "stmt-original", "stmt-graph" ] } ], "olympiad_reformulations": [] }, "ideas": [ { "id": "idea-checkerboard-lower-bound", "title": "Шахматный цветовой класс заставляет брать нечётные метки", "text": "Если чудовища занимают один цветовой класс шахматной раскраски, всякий гамильтонов путь чередует цвета. Turbo может выбрать цвет начальной клетки, но лучший выбор всё равно помещает чудовищ ровно на нечётные позиции, сумма которых равна \\(4n^4\\).", "tags": [ "coloring", "parity_coloring", "goal_construction" ], "status": "ai_checked" }, { "id": "idea-hamiltonian-cycle-pairing", "title": "Противоположные направления вдоль гамильтонова цикла спаривают счета", "text": "Для любого расположения чудовищ начнём с одной клетки с чудовищем и сравним два гамильтоновых пути, полученных обходом гамильтонова цикла в противоположных направлениях. Каждое не начальное чудовище получает метки, сумма которых в двух направлениях равна \\(4n^2+2\\), а начальное даёт вклад \\(1+1\\).", "tags": [ "hamiltonian_cycles", "double_counting" ], "status": "ai_checked" } ], "solutions": [ { "id": "sol-official-checkerboard-cycle-pairing", "title": "Шахматная расстановка и два обхода гамильтонова цикла", "text": "Ответ: \\(4n^4\\).\n\nСначала докажем, что чудовища могут гарантировать не меньше \\(4n^4\\). Раскрасим клетки доски в шахматном порядке. Так как доска имеет размер \\(2n\\times 2n\\), в каждом цвете ровно половина клеток, то есть \\(2n^2\\) клеток. Пусть чудовища займут все клетки одного цвета.\n\nЛюбой ход Turbo идет между соседними по стороне клетками, а соседние клетки имеют разные цвета. Поэтому вдоль любого пути цвета клеток чередуются. Если Turbo начнет с клетки цвета чудовищ, то чудовища окажутся ровно на местах с нечетными номерами \\(1,3,5,\\ldots,4n^2-1\\). Если он начнет с клетки другого цвета, то чудовища окажутся на местах с четными номерами \\(2,4,\n\\ldots,4n^2\\), что дает больший счет. Значит при такой расстановке оптимальный выбор Turbo дает чудовищам сумму первых \\(2n^2\\) нечетных чисел:\n\\[\n1+3+\\cdots+(4n^2-1)=(2n^2)^2=4n^4.\n\\]\nСледовательно, чудовища действительно могут гарантировать счет хотя бы \\(4n^4\\).\n\nТеперь докажем, что большего они гарантировать не могут. Нужно показать, что при любой расстановке \\(2n^2\\) чудовищ Turbo умеет получить счет не больше \\(4n^4\\).\n\nНам понадобится гамильтонов цикл по всем клеткам доски \\(2n\\times 2n\\). Он существует: например, можно пройти верхнюю строку слева направо, затем змейкой пройти строки со второй по последнюю, используя столбцы со второго по последний, после этого из последней строки перейти в первый столбец, подняться по нему до второй строки и последним шагом вернуться в левую верхнюю клетку. Так получается цикл, проходящий через каждую клетку ровно один раз. Четность числа строк важна: после змейки по строкам конец оказывается внизу во втором столбце, откуда можно замкнуть обход через первый столбец.\n\nЗафиксируем произвольную расстановку чудовищ. Выберем одну клетку с чудовищем и назовем ее начальной. Turbo рассмотрит два допустимых обхода: идти из этой клетки по найденному гамильтонову циклу в одну сторону или в другую. В обоих случаях начальная клетка получает метку \\(1\\), а удаление начальной клетки из цикла оставляет гамильтонов путь по всем остальным клеткам.\n\nПусть всего клеток \\(N=4n^2\\). Возьмем любое другое чудовище. Если при обходе цикла в первую сторону его клетка получила номер \\(i\\), то при обходе в противоположную сторону она получит номер \\(N+2-i\\). Действительно, в одну сторону от начальной клетки до этой клетки идет \\(i-1\\) ребер цикла, а в другую сторону идет \\(N-(i-1)\\) ребер; значит соответствующая метка во втором обходе равна \\(N-(i-1)+1=N+2-i\\).\n\nПросуммируем счета двух противоположных обходов. Начальное чудовище дает вклад \\(1+1=2\\). Каждое из остальных \\(2n^2-1\\) чудовищ дает вклад\n\\[\ni+(4n^2+2-i)=4n^2+2.\n\\]\nПоэтому сумма двух счетов равна\n\\[\n2+(2n^2-1)(4n^2+2)=2+(8n^4-2)=8n^4.\n\\]\nЕсли сумма двух чисел равна \\(8n^4\\), то хотя бы одно из них не превосходит \\(4n^4\\). Turbo выбирает соответствующее направление обхода цикла и получает счет не больше \\(4n^4\\).\n\nИтак, чудовища имеют расстановку, гарантирующую \\(4n^4\\), а при любой их расстановке Turbo может удержать счет не выше \\(4n^4\\). Следовательно, наибольший счет, который чудовища могут гарантировать, равен \\(4n^4\\).", "idea_ids": [ "idea-checkerboard-lower-bound", "idea-hamiltonian-cycle-pairing" ], "standard_idea_ids": [], "definition_ids": [ "hamiltonian_cycle", "hamiltonian_path" ], "source_id": "src-cmo-2026-solutions", "status": "ai_checked" } ], "difficulty": { "main": "national_final_medium", "local_score": 8, "comment": "CMO 2026 P3; точное минимаксное значение получается из нижней оценки шахматной раскраской и усреднения по двум противоположным обходам гамильтонова цикла чётной решётки.", "status": "ai_checked" }, "tags": [ "hamiltonian_cycles", "coloring", "parity_coloring", "double_counting", "goal_exact_bound", "goal_strategy_game" ], "properties": { "central_method": { "value": [ "checkerboard_coloring", "hamiltonian_cycle_pairing", "reverse_traversal_averaging" ], "status": "ai_checked" } }, "sources": [ { "source_id": "src-cmo-2026-official", "role": "problem_statement_official", "statement_ids": [ "stmt-original" ], "status": "source_verified", "note": "Официальный PDF задач CMS CMO 2026, ссылка на который дана на странице результатов CMO/CJMO 2026." }, { "source_id": "src-cmo-2026-solutions", "role": "official_solutions", "solution_ids": [ "sol-official-checkerboard-cycle-pairing" ], "status": "source_verified", "note": "Официальный PDF решений CMS CMO 2026; решение задачи 3 даёт ответ \\(4n^4\\), используя шахматную конструкцию и противоположные обходы гамильтонова цикла." } ], "editorial": { "created_by": "ai", "created_at": "2026-04-27", "updated_at": "2026-04-27", "review_status": "ai_checked", "public_ready": true, "notes": [ "2026-04-27: условие сверено с официальным CMS CMO2026-problems.pdf, а решение — с CMO2026-solutions.pdf.", "2026-04-27: в официальном листе задач и решений индивидуальный автор задачи не указан; в поле authors записан комитет/источник олимпиады.", "2026-04-27: обычная формулировка graph_theory является эквивалентной игровой формулировкой через гамильтонов путь в графе смежности клеток; подсказка о спаривании по гамильтонову циклу оставлена в graph_hint_reformulations.", "2026-04-27: отдельная карточка леммы не добавлялась, потому что спаривание счёта по обратному обходу цикла короткое и тесно связано с минимаксной постановкой этой задачи." ], "relations_status": "deep_done", "solution_classification": { "type": "official_complete_or_near_complete", "status": "ai_checked", "confidence": 0.82, "basis": "официальный источник решения и несжатый текст решения", "notes": "Текущий текст основан на официальном источнике и выглядит полным или почти полным.", "label": "официальное полное/почти полное" } } }