{
  "id": "yumt-2018-grand-final-problem1",
  "title": "Игра на связном графе с числами в вершинах, ЮМТ 2018",
  "kind": {
    "primary": "olympiad_problem",
    "secondary": [
      "graph_in_statement",
      "application"
    ]
  },
  "language": "ru",
  "authors": [
    {
      "name": "?",
      "status": "needs_human_review"
    }
  ],
  "problem_profile": {
    "objects": [],
    "methods": [],
    "transformations": [],
    "goal": [],
    "auxiliary_graph_type": [],
    "invariants": [],
    "keywords": [
      "yumt",
      "2018_grand_final_problem1",
      "yumt_2018"
    ],
    "status": "needs_human_review"
  },
  "statements": {
    "original": [
      {
        "id": "stmt-original",
        "title": "Оригинальная формулировка",
        "text": "Изначально N неотрицательных целых чисел расставлены в вершинах связного графа, в котором не меньше 3 вершин; сумма этих чисел равна 2N.\nИгра состоит из раундов: сначала Вася вычитает 3 из одного числа, а затем Петя прибавляет по 1 к какому-то числу и двум из его соседей.\nПетя выигрывает, если Вася не может сделать очередной ход; если Вася может продолжать игру бесконечно, Петя не выигрывает.\nДля каких связных графов с не менее чем 3 вершинами у Пети есть выигрышная стратегия при любой начальной расстановке чисел?",
        "source_id": "src-yumt-2018-grand-final-problem1-official",
        "status": "ai_checked",
        "self_contained": {
          "status": "ai_checked"
        },
        "definition_ids": [
          "connected_graph"
        ]
      }
    ],
    "graph_theory": [],
    "olympiad_reformulations": []
  },
  "ideas": [
    {
      "id": "idea-mod3-triple-invariant",
      "title": "Инвариант по допустимым тройкам modulo 3",
      "text": "Если вершинам приписаны элементы поля \\(\\mathbb F_3\\) так, что сумма на каждой допустимой тройке «вершина и два её соседа» равна нулю, то взвешенная сумма чисел в вершинах не меняется ни при ходе Васи, ни при ходе Пети.",
      "tags": [
        "invariant",
        "goal_strategy_game"
      ],
      "status": "ai_checked"
    },
    {
      "id": "idea-finite-trap-linear-algebra",
      "title": "Конечная игра и линейная алгебра над F3",
      "text": "В конечной игре отсутствие выигрышной стратегии у Пети даёт замкнутую проигрышную область. По модулю 3 такая область замкнута относительно прибавления всех допустимых троек; если эти тройки порождают все векторы с нулевой суммой, то в ней должен оказаться единственный остаточный класс финальной позиции.",
      "tags": [
        "invariant",
        "goal_strategy_game"
      ],
      "status": "ai_checked"
    }
  ],
  "solutions": [
    {
      "id": "sol-ai-mod3-triples-classification",
      "title": "ИИ-решение: классификация через допустимые тройки modulo 3",
      "text": "Ответ: Петя выигрывает ровно на тех связных графах, которые не являются путями и не являются циклами длины, кратной 3.\n\nНазовём допустимой тройкой множество из вершины и двух её различных соседей. После полного раунда сумма чисел снова равна \\(2N\\). Поэтому если перед ходом Васи он не может ходить, то все числа не превосходят 2, а из суммы \\(2N\\) следует, что все они равны 2. Значит, цель Пети — добиться позиции \\((2,2,\\ldots,2)\\).\n\nСначала докажем общий критерий. Пусть \\(U\\) — линейная оболочка над \\(\\mathbb F_3\\) индикаторов всех допустимых троек. Так как каждая такая тройка имеет размер 3, \\(U\\) лежит в пространстве \\(W\\) всех векторов с суммой координат 0. Утверждаем, что Петя выигрывает при любой начальной позиции тогда и только тогда, когда \\(U=W\\).\n\nЕсли \\(U\\ne W\\), то найдётся не постоянная функция \\(c:V\\to\\mathbb F_3\\), сумма значений которой на каждой допустимой тройке равна 0. Тогда величина \\(\\sum_v c_v x_v\\) по модулю 3 не меняется: Вася вычитает 3 из одной координаты, а Петя прибавляет индикатор допустимой тройки. Возьмём две вершины \\(p,q\\) с \\(c_p\\ne c_q\\) и начальную позицию, в которой в \\(p\\) стоит 3, в \\(q\\) стоит 1, а во всех остальных вершинах стоит 2. Её сумма равна \\(2N\\), но значение инварианта отличается от значения в финальной позиции \\((2,\\ldots,2)\\). Поэтому Петя не может прийти к финальной позиции; раз сумма всегда \\(2N\\), любая нефинальная позиция содержит число хотя бы 3, и Вася может продолжать бесконечно.\n\nОсталось объяснить обратное. Игра конечна, потому что позиций с неотрицательными целыми числами и суммой \\(2N\\) конечно. Если из некоторой позиции Петя не выигрывает, то существует непустое множество проигрышных для Пети нефинальных позиций \\(L\\) с таким свойством: из каждой позиции \\(x\\in L\\) Вася может выбрать вершину, после вычитания из которой любой ответ Пети снова приводит в \\(L\\). Рассмотрим остатки позиций из \\(L\\) по модулю 3. Вычитание 3 Васей не меняет остаток, а ответы Пети прибавляют все индикаторы допустимых троек. Значит, множество таких остатков замкнуто относительно прибавления всех элементов \\(U\\). Если \\(U=W\\), то вместе с любым остатком суммы \\(2N\\) оно содержит все остатки с той же суммой координат, в частности остаток \\((2,2,…,2)\\). Но среди неотрицательных позиций суммы \\(2N\\), все координаты которых сравнимы с 2 по модулю 3, есть только сама позиция \\((2,2,…,2)\\). Она финальная и не может лежать в \\(L\\), противоречие. Значит, при \\(U=W\\) Петя действительно выигрывает из любой начальной позиции.\n\nТеперь осталось понять, когда \\(U=W\\). Перейдём к ортогональному дополнению над \\(\\mathbb F_3\\). Условие \\(U=W\\) равносильно тому, что всякая функция \\(c:V\\to\\mathbb F_3\\), сумма которой на каждой допустимой тройке равна 0, постоянна.\n\nЕсли в графе есть вершина \\(v\\) степени хотя бы 3, то для любых трёх её соседей \\(a,b,d\\) из равенств \\(c_v+c_a+c_b=0\\) и \\(c_v+c_a+c_d=0\\) получаем \\(c_b=c_d\\). Значит, все соседи \\(v\\) имеют одно значение, а из \\(c_v+2c_a=0\\) следует, что это значение равно \\(c_v\\). Далее равенство распространяется вдоль любого пути: если две соседние вершины на пути уже имеют одно значение, то у следующей вершины оно такое же из равенства для соответствующей допустимой тройки. Так как граф связен, все значения \\(c\\) постоянны. Поэтому все связные графы с вершиной степени хотя бы 3 подходят.\n\nЕсли же все степени не больше 2, связный граф — это путь или цикл. Для пути с вершинами \\(1,2,…,N\\) условия имеют вид \\(c_{i-1}+c_i+c_{i+1}=0\\) при \\(2\\le i\\le N-1\\). Последовательность \\(0,1,-1,0,1,-1,…\\) даёт непостоянное решение, поэтому пути не подходят.\n\nДля цикла получаем те же рекуррентные соотношения по кругу. Любое решение имеет период 3: если первые два значения равны \\(a,b\\), то дальше идут \\(-a-b,a,b,-a-b,…\\). Если длина цикла кратна 3, можно взять непостоянный периодический набор, например \\(0,1,-1\\), и Петя не всегда выигрывает. Если длина цикла не кратна 3, циклическое замыкание заставляет \\(a=b=-a-b\\), то есть все значения равны; значит, такие циклы подходят.\n\nИтак, ровно исключённые графы — пути и циклы длины \\(3,6,9,…\\). На всех остальных связных графах с не менее чем тремя вершинами у Пети есть выигрышная стратегия при любой начальной расстановке.",
      "idea_ids": [
        "idea-mod3-triple-invariant",
        "idea-finite-trap-linear-algebra"
      ],
      "standard_idea_ids": [],
      "status": "ai_checked",
      "definition_ids": [],
      "review_notes": "ИИ-решение, добавлено 2026-05-05: самодостаточная классификация через конечную игру и линейную алгебру над F3; внешние теоремы не используются."
    }
  ],
  "difficulty": {
    "main": "regional",
    "local_score": 6,
    "comment": "Импортировано из проверенной архивной карточки ЮМТ 2018_grand_final_problem1.md; этап: Гранд-лига, финал.",
    "status": "ai_checked"
  },
  "tags": [
    "connectivity",
    "goal_strategy_game",
    "invariant"
  ],
  "sources": [
    {
      "source_id": "src-yumt-2018-grand-final-problem1-official",
      "role": "problem_and_solutions_official",
      "status": "source_verified"
    }
  ],
  "editorial": {
    "created_by": "ai",
    "created_at": "2026-04-25",
    "review_status": "needs_human_review",
    "public_ready": false,
    "notes": [
      "Импортировано из проверенной рабочей карточки ЮМТ 2018_grand_final_problem1.md.",
      "2026-04-27: сверено с распакованной рабочей карточкой ЮМТ; формулировка уточнена для явного порядка ходов/условия гарантии без изменения математического смысла источника.",
      "2026-05-05: внешний поиск нашёл официальный сайт Южного математического турнира и условия туров 2018 года, но не нашёл публичный разбор/автора этой финальной задачи. Добавлено ИИ-решение: ответ — все связные графы, кроме путей и циклов длины, кратной 3; доказательство использует только конечность игры и линейную алгебру над F3."
    ],
    "relations_status": "deep_done",
    "graph_theory_duplicate_removed": true,
    "solution_classification": {
      "type": "official_complete_or_near_complete",
      "label": "официальное полное/почти полное",
      "status": "ai_checked",
      "confidence": 0.78,
      "basis": "агентский аудит средней сложности",
      "notes": "Метаданные источника указывают на архивное или официальное решение; решение проверено.",
      "audit_source": "agent-russian-archives.json"
    }
  }
}