{ "id": "lktg-2026-project2-problem17-firms-and-geniuses", "title": "Фирмы и отмеченные гении в графе знакомств", "kind": { "primary": "olympiad_problem", "secondary": [ "graph_in_statement", "application", "game", "published_generalization" ] }, "language": "ru", "authors": [ { "name": "Шаповалов А.В.", "status": "source_verified" } ], "problem_profile": { "objects": [ "acquaintance_graph", "distinguished_vertices", "connected_growing_sets", "integer_simplex_graph", "connected_subgraph", "positional_game" ], "methods": [ "explicit_construction", "strategy", "distance_race", "coordinate_maximum_invariant", "coordinate_potential", "max_coordinate_invariant" ], "transformations": [ "programmers_to_vertices", "hiring_rule_to_connected_growth", "integer_compositions_to_graph", "acquaintances_to_graph" ], "goal": [ "second_player_collects_r_minus_one_targets", "construct_graph", "second_player_strategy", "construct_example" ], "auxiliary_graph_type": [ "cycle", "subdivided_complete_bipartite_skeleton", "integer_simplex_graph" ], "invariants": [ "strict_distance_advantage", "coordinate_maximum_advantage", "coordinate_advantage", "max_coordinate_gap", "connectedness" ], "keywords": [ "lktg_2026_project2_problem17", "firms_and_geniuses", "mmo_2011", "tournament_of_cities_2011", "generalization", "mmo-2011-firms-programmers-geniuses", "programmers", "geniuses", "acquaintances", "hiring_game", "integer_compositions" ], "status": "ai_checked" }, "statements": { "original": [ { "id": "stmt-original", "title": "Фирмы нанимают программистов в графе знакомств", "text": "Вершины конечного простого графа — программисты, а рёбра означают знакомства. Фирмы Пети и Васи по очереди нанимают по одному программисту, ещё не нанятому ни одной фирмой; начинает фирма Пети. Первого программиста каждая фирма выбирает произвольно. Каждый следующий нанятый ею программист должен быть знаком хотя бы с одним программистом, уже работающим в этой фирме. Если фирма не может сделать ход, она прекращает набор, а другая продолжает по тем же правилам, пока может. Среди программистов заранее отмечены \\(r\\) гениев.\n\nа) Для \\(r=3\\) постройте граф, в котором фирма Васи гарантированно наймёт не меньше двух гениев.\n\nб) Для \\(r=4\\) постройте граф, в котором фирма Васи гарантированно наймёт не меньше трёх гениев.\n\nв) Для каждого \\(r\\ge2\\) постройте граф, в котором фирма Васи гарантированно наймёт не меньше \\(r-1\\) гениев.", "source_id": "src-lktg-2026-project2-problems-ru", "status": "source_verified", "self_contained": { "status": "ai_checked" }, "definition_ids": [ "simple_graph", "connected_graph", "path", "cycle", "distance" ] }, { "id": "stmt-tc-2011-eleven-geniuses", "title": "Версия Турнира городов с 11 гениями", "text": "Две фирмы по очереди нанимают программистов, среди которых есть 11 всем известных гениев. Первого программиста каждая фирма выбирает произвольно, а каждый следующий должен быть знаком с кем-то из ранее нанятых данной фирмой. Если фирма не может нанять программиста по этим правилам, она прекращает приём, а другая может продолжать. Список программистов и их знакомств заранее известен. Могут ли знакомства быть устроены так, что фирма, вступающая в игру второй, сможет нанять 10 гениев, как бы ни действовала первая фирма?", "source_id": "src-tc-2011-32-vs32sl-official", "status": "source_verified", "self_contained": { "status": "ai_checked" }, "definition_ids": [ "simple_graph", "connected_graph" ] } ], "graph_theory": [], "olympiad_reformulations": [] }, "ideas": [ { "id": "idea-alternating-six-cycle", "title": "Чередующийся шестиугольник для трёх гениев", "text": "На цикле длины шесть гении и обычные программисты чередуются. Первый ответ Васи переводит игру в вынужденное чередование, при котором два гения достаются Васе.", "tags": [ "goal_construction", "goal_strategy_game" ], "status": "ai_checked" }, { "id": "idea-simplex-coordinate-maxima", "title": "Целочисленный симплекс и максимумы координат", "text": "В общей конструкции вершины — неотрицательные целые векторы фиксированной суммы, а ход по ребру переносит единицу между координатами. Вася поддерживает строгий перевес максимума по всем координатам, кроме одной.", "tags": [ "process_invariant", "goal_construction" ], "status": "ai_checked" } ], "solutions": [ { "id": "sol-official-parts-a-c", "title": "Шестиугольник, пути длин 10–13 и общая координатная конструкция", "text": "а) Возьмём цикл\n\\[\ng_1-u_1-g_2-u_2-g_3-u_3-g_1\n\\]\nи объявим гениями \\(g_1,g_2,g_3\\). Если Петя первым нанял гения, например \\(g_1\\), Вася нанимает противоположную вершину \\(u_2\\). Следующий законный ход Пети — \\(u_1\\) или \\(u_3\\). В первом случае Вася берёт \\(g_2\\), во втором — \\(g_3\\). После этого набор по оставшимся дугам цикла вынужден, и второй из двух оставшихся гениев также достаётся Васе.\n\nЕсли Петя начал с обычной вершины, например \\(u_1\\), Вася берёт соседнего гения \\(g_1\\). Петя вынужден взять \\(g_2\\), затем Вася берёт \\(u_3\\), Петя — \\(u_2\\), Вася — \\(g_3\\). В обоих случаях Вася нанимает двух гениев.\n\nб) Это частный случай пункта в при \\(r=4\\): общая координатная конструкция, доказанная ниже, гарантирует Васе не меньше \\(r-1=3\\) гениев. Поэтому отдельной конструкции для этого пункта не требуется.\n\nв) Положим \\(L=r(r-1)\\). Программистами будут все векторы\n\\[\nx=(x_1,\\ldots,x_r),\\qquad x_i\\in\\mathbb Z_{\\ge0},\\qquad x_1+\\cdots+x_r=L.\n\\]\nДва программиста знакомы, если один вектор получается из другого увеличением одной координаты на 1 и уменьшением другой на 1. Гениями объявим\n\\[\nG_i=(0,\\ldots,0,L,0,\\ldots,0),\\qquad1\\le i\\le r,\n\\]\nгде \\(L\\) стоит в \\(i\\)-й координате. Граф конечен, и отмеченных гениев ровно \\(r\\).\n\nПусть первым Петя нанял \\(A=(A_1,\\ldots,A_r)\\). Некоторая координата, скажем \\(A_k\\), не меньше \\(L/r=r-1\\). Первым ходом Вася нанимает \\(B\\), где\n\\[\nB_i=A_i+1\\quad(i\\ne k),\\qquad B_k=A_k-(r-1).\n\\]\nКоординаты неотрицательны, их сумма равна \\(L\\), поэтому такой программист существует.\n\nДля каждой фирмы и каждого \\(i\\ne k\\) обозначим через \\(m_i\\) и \\(M_i\\) наибольшую \\(i\\)-ю координату среди уже нанятых Петей и Васей соответственно. Сразу после первого хода Васи \\(M_i>m_i\\) для всех \\(i\\ne k\\). Покажем, как Вася сохраняет эти неравенства.\n\nНовый работник Пети смежен с одним из прежних, поэтому у его вектора увеличилась ровно одна координата и только на единицу. После хода Пети не более одного строгого неравенства может стать равенством, и ни одно не меняет знак. Если возникло \\(m_i=M_i=d\\), у Васи уже есть работник \\(S\\) с \\(S_i=d\\). Число \\(dm_i\\); остальные максимумы Васи не уменьшаются, поскольку все ранее нанятые вершины остаются у фирмы.\n\nЕсли равенства нет, Вася выбирает любую координату \\(i\\ne k\\) с \\(M_i