{
  "id": "kolmogorov-2021-individual-olympiad-seniors-problem-1",
  "title": "Двухкруговой турнир с равным числом домашних и гостевых побед, Кубок Колмогорова 2021",
  "kind": {
    "primary": "olympiad_problem",
    "secondary": [
      "graph_in_solution",
      "application"
    ]
  },
  "language": "ru",
  "authors": [
    {
      "name": "?",
      "status": "needs_human_review"
    }
  ],
  "problem_profile": {
    "objects": [
      "simple_graph"
    ],
    "methods": [
      "handshake_lemma"
    ],
    "transformations": [
      "auxiliary_graph_model"
    ],
    "goal": [
      "proof"
    ],
    "auxiliary_graph_type": [
      "simple_graph"
    ],
    "invariants": [
      "parity"
    ],
    "keywords": [
      "kolmogorov",
      "kolmogorov_2021"
    ],
    "status": "ai_checked"
  },
  "statements": {
    "original": [
      {
        "id": "stmt-original",
        "title": "Оригинальная формулировка",
        "text": "\\(999\\) команд сыграли двухкруговой турнир по волейболу: каждая сыграла с каждой матч дома и матч в гостях.\n\nКаждая команда выиграла ровно половину своих домашних матчей и ровно половину гостевых.\n\nДокажите, что какая-то из команд дважды обыграла какую-то другую.",
        "source_id": "src-kolmogorov-2021-official",
        "status": "ai_checked",
        "self_contained": {
          "status": "ai_checked"
        },
        "definition_ids": [
          "simple_graph"
        ]
      }
    ],
    "graph_theory": [],
    "olympiad_reformulations": []
  },
  "ideas": [
    {
      "id": "idea-graph-role",
      "title": "Графовая роль",
      "text": "В условии турнир не сформулирован языком графов, но официальное решение существенно вводит граф на командах и завершает доказательство через лемму о рукопожатиях.",
      "tags": [],
      "status": "ai_checked"
    }
  ],
  "solutions": [
    {
      "id": "sol-official-compressed",
      "title": "Самодостаточное решение",
      "text": "Предположим противное: ни одна команда не обыграла другую дважды. Рассмотрим две произвольные команды `X` и `Y`. Они сыграли два матча: один на площадке `X`, другой на площадке `Y`. По нашему предположению не может быть так, что `X` выиграла оба матча, и не может быть так, что `Y` выиграла оба матча. Значит, победы в этой паре разделились поровну: либо обе команды выиграли свои домашние матчи, либо обе команды выиграли свои гостевые матчи.\n\nПостроим простой граф на `999` вершинах-командах. Соединим две команды ребром тогда и только тогда, когда в их паре обе команды выиграли домашние матчи. Для фиксированной команды ее степень в этом графе равна числу ее домашних побед: каждое ребро, выходящее из вершины, соответствует сопернику, которого эта команда победила дома, а если команда победила дома данного соперника, то по предыдущему абзацу соперник тоже победил дома, значит соответствующее ребро действительно есть.\n\nКаждая команда сыграла дома с `998` соперниками и выиграла ровно половину домашних матчей, то есть `499`. Следовательно, в построенном графе каждая из `999` вершин имеет степень `499`.\n\nНо сумма степеней любого конечного неориентированного графа равна удвоенному числу ребер, поэтому должна быть четной. Здесь сумма степеней равна `999 * 499`, а это произведение двух нечетных чисел, то есть нечетное число. Получили противоречие.\n\nЗначит, исходное предположение неверно, и найдутся две команды, одна из которых обыграла другую в обоих матчах.",
      "idea_ids": [
        "idea-graph-role"
      ],
      "standard_idea_ids": [
        "double_counting"
      ],
      "status": "ai_checked",
      "definition_ids": [
        "simple_graph",
        "degree"
      ],
      "repair_status": "medium_reasoning_understandable_2026_05_06",
      "review_notes": "Аудит средней сложности 2026-05-06: решение понятно агенту среднего уровня; скрытых непроверенных переходов при чтении не найдено."
    }
  ],
  "difficulty": {
    "main": "national_final_medium",
    "local_score": 6,
    "comment": "Импортировано из подготовленной графовой карточки KOLM; оценка сложности требует проверки человеком.",
    "status": "needs_human_review"
  },
  "tags": [
    "double_counting",
    "goal_strategy_game"
  ],
  "properties": {},
  "sources": [
    {
      "source_id": "src-kolmogorov-2021-official",
      "role": "problem_and_solutions_official",
      "status": "source_verified"
    },
    {
      "source_id": "src-kolmogorov-archive",
      "role": "official_archive_index",
      "status": "source_verified"
    }
  ],
  "editorial": {
    "created_by": "ai",
    "created_at": "2026-04-26",
    "review_status": "needs_human_review",
    "public_ready": false,
    "notes": [
      "Импортировано из подготовленной карточки cards/kolm/2021_individual_olympiad_seniors_problem_1.md.",
      "Файл-источник, указанный в карточке: work/kolm/archive/2021/extracted_seniors/5lichol-sen-sol.tex.",
      "Страница-источник, указанная в карточке: индивидуальная олимпиада, старшая группа, задача 1.",
      "Роль графа: существенна в официальном решении.",
      "Исходное название в финальной выборке: индивидуальная олимпиада, старшие участники, задача 1.",
      "Сжатое официальное решение в этом проходе сверено с локально извлечённым текстом официального архива."
    ],
    "relations_status": "deep_done",
    "graph_theory_absent_reason": "Самостоятельная графовая постановка из условия неочевидна; графовая модель используется только в решении.",
    "solution_classification": {
      "type": "official_complete_or_near_complete",
      "label": "официальное полное/почти полное",
      "status": "ai_checked",
      "confidence": 0.9,
      "basis": "агентский аудит средней сложности",
      "notes": "Короткое решение было развёрнуто: отдельно проверены два типа пар, степень в вспомогательном графе и четность суммы степеней.",
      "audit_source": "agent-russian-archives.json"
    }
  }
}