{ "id": "mmo-2011-firms-programmers-geniuses", "title": "Стратегия второй фирмы при найме программистов и четырёх гениев, ММО 2011", "kind": { "primary": "olympiad_problem", "secondary": [ "graph_in_statement", "application", "game" ] }, "language": "ru", "authors": [ { "name": "Шаповалов А.В.", "status": "source_verified" } ], "problem_profile": { "objects": [ "acquaintance_graph", "paths", "positional_game" ], "methods": [ "strategy", "distance_in_graph", "path_length_construction", "balancing_strategy" ], "transformations": [ "acquaintances_to_graph" ], "goal": [ "second_player_strategy" ], "auxiliary_graph_type": [], "invariants": [ "distance_to_target_vertices", "strict_distance_advantage", "free_private_channels" ], "keywords": [ "mmo_2011", "firms", "programmers", "geniuses", "acquaintance_graph", "famous_programmers", "chain_length_matrix" ], "status": "ai_checked" }, "statements": { "original": [ { "id": "stmt-original", "title": "Фирмы нанимают знакомых программистов", "text": "Две фирмы по очереди нанимают программистов, среди которых есть 4 гения. Первого программиста каждая фирма выбирает произвольно, а каждый следующий должен быть знаком с кем-то из ранее нанятых данной фирмой. Если фирма не может нанять программиста по этим правилам, она прекращает приём, а другая может продолжать. Список программистов и их знакомств заранее известен. Могут ли знакомства быть устроены так, что фирма, вступающая в игру второй, сможет нанять по крайней мере 3 гениев, как бы ни действовала первая фирма?", "source_id": "src-mmo-2011-74mmo", "status": "ai_checked", "self_contained": { "status": "ai_checked" }, "definition_ids": [ "simple_graph", "path" ] } ], "graph_theory": [ { "id": "stmt-graph", "title": "Игра на связно растущих множествах в графе знакомств", "text": "Существует ли простой граф с четырьмя выделенными вершинами, в котором два игрока по очереди выбирают ещё не выбранные вершины, причём первая вершина каждого игрока произвольна, а каждая следующая выбранная им вершина должна быть смежна хотя бы с одной уже выбранной им вершиной, и второй игрок гарантирует себе выбор не менее трёх выделенных вершин независимо от игры первого?", "status": "ai_checked", "self_contained": { "status": "ai_checked" }, "definition_ids": [ "simple_graph", "connected_graph", "path" ] } ] }, "ideas": [ { "id": "idea-distance-race-to-geniuses", "title": "Цепочки заданных длин к гениям", "text": "Ключевая конструкция строит граф из четырёх 'знаменитых' программистов и четырёх гениев, соединённых попарно внутренне непересекающимися цепочками специальных длин. Вторая фирма после первого ответа фиксирует три целевых гения и поддерживает строгий инвариант: до каждого из них её оставшийся путь короче, чем минимальный путь первой фирмы.", "tags": [ "goal_strategy_game", "connectivity" ], "status": "ai_checked" } ], "solutions": [ { "id": "sol-official-summary", "title": "Развернутая стратегия второй фирмы", "text": "Ответ: могут.\n\nПостроим граф знакомств. Обозначим четырёх гениев через G0, G1, G2, G3. Добавим ещё четырёх программистов F0, F1, F2, F3, которые будут играть роль 'знаменитых'. Для каждой пары i, j соединим Fi и Gj отдельной цепочкой длины k(i,j), то есть цепочкой\nFi = H0(i,j), H1(i,j), ..., Hk(i,j)(i,j) = Gj,\nгде соседние вершины цепочки знакомы. Внутренние вершины всех шестнадцати цепочек считаются различными, а других программистов и других знакомств нет. Длины зададим таблицей:\n\nот F0: 13, 12, 11, 10;\nот F1: 12, 11, 10, 13;\nот F2: 11, 10, 13, 12;\nот F3: 10, 13, 12, 11.\n\nИными словами, в строке Fi стоят длины цепочек от Fi до G0, G1, G2, G3. Каждая следующая строка получается циклическим сдвигом: по сравнению со строкой Fi строка F(i+1) короче ровно на 1 для трёх последовательных гениев и длиннее для четвёртого.\n\nБудем говорить, что расстояние от фирмы до ещё не нанятого программиста X равно минимальному числу дальнейших ходов, за которое эта фирма могла бы нанять X, если бы другая фирма больше не мешала; уже занятые другой фирмой вершины использовать нельзя. После первого хода фирмы это обычное расстояние от её уже нанятого связного множества до X по свободным вершинам. Если фирма стоит в Fi, то её расстояние до Gj равно k(i,j).\n\nОпишем первый ответ второй фирмы. Если первая фирма первым ходом взяла знаменитого программиста Fi, то вторая берёт F(i+1) с индексами по модулю 4. Тогда три гения Gi, G(i+1), G(i+2) ближе ко второй фирме, чем к первой: соответствующие длины у F(i+1) меньше на 1. После переобозначения этих трёх гениев будем называть их G0, G1, G2, а оставшегося - G3. Например, если первая взяла F0, то вторая берёт F1 и имеет расстояния 12, 11, 10 до G0, G1, G2, тогда как первая имеет 13, 12, 11.\n\nЕсли первая фирма первым ходом взяла гения, назовём его G3, то вторая берёт любого знаменитого программиста, например F0, и будет бороться за G0, G1, G2. До этих трёх гениев второй фирме нужно соответственно 13, 12, 11 ходов. Первой же, чтобы из G3 добраться до любого другого гения, надо пройти через некоторого знаменитого программиста, поэтому требуется не меньше 10 + 10 = 20 ходов, фактически в таблице минимум равен 21. Значит, все G0, G1, G2 сначала существенно ближе ко второй фирме.\n\nЕсли первая фирма первым ходом взяла внутреннюю вершину цепочки между некоторым Fi и некоторым гением, назовём этот гений G3, то вторая берёт Fi и снова борется за G0, G1, G2. Для любого j = 0, 1, 2 путь первой фирмы к Gj через Fi длиннее пути второй ровно на расстояние от первой вершины до Fi; если же путь через Fi уже перекрыт занятым второй фирмой Fi, то первой тем более не легче. Поэтому каждый из G0, G1, G2 после ответа второй фирмы ближе ко второй фирме.\n\nИтак, после первого ответа второй фирмы есть знаменитый программист F, принадлежащий второй фирме, и три целевых гения G0, G1, G2 со свойством: каждый из них строго ближе ко второй фирме, чем к первой. Зафиксируем для второй фирмы три её канала - цепочки от F к G0, G1, G2. Эти три цепочки имеют общую только вершину F, а их внутренние вершины не встречаются ни в каких других каналах второй фирмы. Поэтому первая фирма не может попасть во внутренность такого канала со стороны F, потому что F уже занят второй фирмой; со стороны Gj она тоже не может войти, пока не наняла самого Gj. Следовательно, пока Gj ещё не у второй фирмы, её частный канал к Gj остаётся свободным, и вторая фирма всегда может одним ходом уменьшить своё расстояние до Gj на 1, взяв следующую вершину этого канала.\n\nТеперь поддерживается следующий инвариант: сразу после каждого хода второй фирмы каждый ещё не нанятый из G0, G1, G2 находится строго ближе ко второй фирме, чем к первой. Пусть инвариант выполнен. Первая фирма делает ход. Один ход может уменьшить её расстояние до любого фиксированного гения не более чем на 1, потому что новая вершина обязана быть смежна с уже нанятым связным множеством первой фирмы. Если первая фирма взяла вершину на цепочке, ведущей к одному из целевых гениев Gj, то именно расстояние до этого Gj является единственной немедленной угрозой: движение по такой цепочке приближает первую фирму к её гениевому концу, а к другим целевым гениям путь всё равно должен сначала пройти через один из концов цепочки и не становится короче защищённых каналов второй фирмы. Вторая фирма отвечает ходом по своему каналу к тому же Gj. До хода первой был строгий целочисленный зазор, значит расстояние первой до Gj после её хода всё ещё не меньше прежнего расстояния второй; затем вторая уменьшает своё расстояние на 1 и снова получает строгий зазор.\n\nЕсли же ход первой фирмы не лежит на цепочке к G0, G1 или G2, то он не приближает её ни к одному из этих трёх гениев. Тогда вторая фирма уменьшает на 1 своё расстояние до того из G0, G1, G2, который от неё дальше всего; при равенстве выбирает любой. Строгий зазор для всех трёх гениев сохраняется, а максимальное из расстояний второй фирмы до целевых гениев не растёт.\n\nОсталось объяснить, почему сохранение этого инварианта действительно даёт победу. Если первая фирма когда-нибудь смогла бы нанять один из G0, G1, G2, то непосредственно перед её ходом расстояние от неё до этого гения было бы равно 1. Но это состояние наступает после предыдущего хода второй фирмы, а по инварианту расстояние второй фирмы до того же гения должно быть строго меньше 1, то есть равно 0. Значит, этот гений уже нанят второй фирмой, противоречие. Поэтому первая фирма не может завладеть ни одним из G0, G1, G2.\n\nПри этом вторая фирма не застревает: пока среди G0, G1, G2 есть не нанятый ею гений, его частный канал от F свободен от вершин первой фирмы до самого конца, и вторая может продолжать идти по нему. Если первая фирма прекращает приём, вторая просто продолжает сокращать расстояния по тем же каналам. Так как граф конечен, после конечного числа ходов вторая фирма нанимает G0, G1 и G2. Следовательно, заранее устроенные знакомства действительно позволяют фирме, вступающей в игру второй, гарантированно нанять по крайней мере трёх гениев.", "source_id": "src-mmo-2011-74mmo", "status": "ai_checked", "standard_idea_ids": [] } ], "difficulty": { "main": "national_final_hard", "local_score": 6, "comment": "ММО 2011, 10 класс, задача 6.", "status": "source_verified" }, "tags": [ "graph_model", "goal_strategy_game", "connectivity" ], "sources": [ { "source_id": "src-mmo-2011-74mmo", "role": "official_booklet", "status": "source_verified" } ], "editorial": { "created_by": "ai", "created_at": "2026-05-03", "review_status": "ai_checked", "public_ready": true, "notes": [ "Подтверждено по manifest family=mmo: URL http://olympiads.mccme.ru/mmo/2011/74mmo.pdf, локальный PDF audit/_mmo_tc_pdfs/e2912b92a11e0f2c.pdf, локальный текст audit/_mmo_tc_text_clean/e2912b92a11e0f2c.txt.", "graph_role=explicit_statement_application: условие прямо задано на графе знакомств; официальное решение использует пути и расстояния в графе.", "Близкий родственник, но не дубль, lktg-2026-project2-problem17-firms-and-geniuses: в MMO есть 4 гения и цель второй фирмы получить по крайней мере 3, а общая карточка ЛКТГ использует координатную конструкцию для произвольного числа гениев.", "Решение развернуто по локальному официальному тексту audit/_mmo_tc_text_clean/e2912b92a11e0f2c.txt: явно указана матрица длин цепочек, первый ответ второй фирмы, частные каналы к трём гениям и инвариант строгого преимущества по расстояниям.", "2026-05-16: карточка проверена в хвостовом срезе official_outline_needs_work; решение признано полным.", "2026-05-16: официальный план доведён до самодостаточного решения; карточка обновлена после статуса official_outline_needs_work." ], "relations_status": "deep_done", "solution_classification": { "type": "official_plan_completed_by_ai", "label": "официальный план доведён до полного", "status": "ai_checked", "confidence": 0.9, "basis": "официальный сборник и повторная проверка развёрнутой стратегии из хвоста очереди official-plan-needs-completion", "notes": "Решение раскрывает конструкцию графа, начальный ответ второй фирмы и инвариант строгого преимущества по расстояниям до трёх целевых гениев.", "audit_source": "official-plan-tail-pass-2026-05-16" } } }