{ "id": "lktg-2026-project2-problem14-white-clique-infinite-board", "title": "Белая клика в смещённой игре на \\(K_\\infty\\), ЛКТГ 2026", "kind": { "primary": "research_project_problem", "secondary": [ "graph_in_statement", "game", "open_subproblem" ] }, "language": "ru", "authors": [], "problem_profile": { "objects": [ "countably_infinite_complete_graph", "white_clique", "finite_target_family", "rooted_tree" ], "methods": [ "branching_tree_strategy", "potential_function", "erdos_selfridge_weight", "probabilistic_selection", "nested_set_construction" ], "transformations": [ "infinite_game_prefix_to_finite_complete_graph", "cliques_to_target_sets" ], "goal": [ "prove_finite_winning_time", "exact_triangle_time", "upper_and_lower_bounds", "open_asymptotic_improvement" ], "auxiliary_graph_type": [ "finite_rooted_branching_tree", "black_graph_on_candidate_set" ], "invariants": [ "ancestor_representatives_form_white_clique", "target_weight_below_one", "bounded_black_density_in_nested_sets" ], "keywords": [ "lktg_2026_project2_problem14", "white_clique_infinite_board", "beck_bound", "pekec_1996", "gebauer_2012", "open_part_14e" ], "status": "ai_checked" }, "statements": { "original": [ { "id": "stmt-original", "title": "Белая клика на бесконечной доске", "text": "Пусть \\(b\\ge1\\) и \\(r\\ge2\\) — целые числа. На рёбрах счётного полного графа \\(K_\\infty\\) Белла и Чингиз играют по раундам: Белла красит одно свободное ребро белым, затем Чингиз красит \\(b\\) свободных рёбер чёрным. Белла выигрывает сразу после появления белой клики \\(K_r\\). Через \\(T_b(r)\\) обозначим наименьшее число ходов Беллы, за которое она может гарантировать победу.\n\nа) Докажите, что для всех \\(b\\ge1\\), \\(r\\ge2\\) Белла имеет выигрышную стратегию; в частности, \\(T_b(r)\\) конечно.\n\nб) Докажите, что \\(T_b(3)=b+3\\).\n\nв) При \\(r\\ge17\\) докажите\n\\[\n\\lfloor2^{r/2}\\rfloor\\le T_1(r)\\le(r-3)2^{r-1}+r+1.\n\\]\n\nг) При \\(r\\ge30\\) докажите\n\\[\n\\lfloor3^{r/2}\\rfloor\\le T_2(r)\\le\\sum_{j=0}^{r-2}j3^j+r+12^{5r/2+1}\\). Для \\(r=17\\) это верно: \\(17!=355687428096000>2^{43.5}\\). При переходе от \\(r\\) к \\(r+1\\) левая часть умножается на \\(r+1\\ge18\\), правая — на \\(2^{5/2}<6\\), поэтому неравенство сохраняется для всех \\(r\\ge17\\). Весовая лемма защищает первые \\(t\\) ходов, значит \\(T_1(r)\\ge t+1=\\lfloor2^{r/2}\\rfloor\\).\n\nВерхняя оценка получается из пункта а) при \\(b=1\\). Индукцией проверяется\n\\[\n\\sum_{j=0}^{r-2}j2^j=(r-3)2^{r-1}+2.\n\\]\nПоэтому \\(T_1(r)\\le(r-3)2^{r-1}+r+1\\).\n\nг) Нижняя оценка для \\(b=2\\). Положим \\(t=\\lfloor3^{r/2}\\rfloor-1\\), \\(N=6t<6\\cdot3^{r/2}\\). Теперь \\(\\lambda=3\\), и достаточно\n\\[\n\\binom Nr<3^{\\binom r2-1}. \\tag{4}\n\\]\nИз \\(\\binom Nr6^r3^{r/2+1}\\). При \\(r=30\\) прямое сравнение даёт\n\\[\n30!=265252859812191058636308480000000>6^{30}3^{16}=9516507342594806772904803434496.\n\\]\nПри увеличении \\(r\\) левая часть умножается на \\(r+1\\ge31\\), правая — на \\(6\\sqrt3<12\\), поэтому неравенство верно для всех \\(r\\ge30\\). Весовая лемма даёт \\(T_2(r)\\ge\\lfloor3^{r/2}\\rfloor\\).\n\nИз пункта а) при \\(b=2\\) следует даже\n\\[\nT_2(r)\\le\\sum_{j=0}^{r-2}j3^j+r-1,\n\\]\nа значит и заявленная оценка с \\(r+1\\). Кроме того,\n\\[\n\\sum_{j=0}^{r-2}j3^j\\le(r-2)\\sum_{j=0}^{r-2}3^j=\\frac{r-2}{2}(3^{r-1}-1).\n\\]\nПри \\(r\\ge2\\) последняя величина вместе с \\(r+1\\) меньше \\(r3^{r-1}\\), что завершает пункт г).\n\nд) Оценка Бека. Сначала докажем лемму о выборе половины. Пусть дан граф \\(F\\) на чётном числе вершин. Два игрока по очереди выбирают по одной ещё не выбранной вершине, начинает Первый. Тогда Первый может добиться, чтобы внутри выбранного им множества было не больше \\(e(F)/4\\) рёбер.\n\nСледим за рёбрами, ни один конец которых ещё не выбрал Второй. Если у такого ребра свободны \\(s\\) концов, даём ему вес \\(2^{-s}\\). Изначально общий вес равен \\(e(F)/4\\). Первый выбирает вершину с наименьшей суммой весов выходящих сохраняющихся рёбер; его ход удваивает веса этих рёбер и увеличивает общий вес ровно на найденную сумму. Затем Второй выбирает вершину и уничтожает все сохраняющиеся рёбра из неё. До хода Первого сумма у этой вершины была не меньше выбранного минимума, а после могла только возрасти, поэтому Второй уничтожает вес не меньше только что добавленного. После каждой пары ходов вес не растёт. В конце сохраняются рёбра с обоими концами у Первого, каждое веса 1, и их не больше \\(e(F)/4\\).\n\nПоложим \\(n=r+2\\) и выберем в \\(K_\\infty\\) множество \\(V_0\\) из \\(2^n\\) вершин. Белла построит вложенные множества \\(V_0\\supset V_1\\supset\\cdots\\) и вершины \\(u_1,u_2,\\ldots\\), причём \\(u_i\\) бело соединена со всем \\(V_i\\). Сначала она выбирает \\(u_1\\in V_0\\) и проводит лучи, пока не получит \\(s_1=2^{n-1}\\) белых соседей; это возможно, потому что из \\(u_1\\) к остальным выходит \\(2^n-1=2s_1-1\\) рёбер, а Чингиз между белыми ходами отнимает не больше одного. Эти соседи образуют \\(V_1\\).\n\nПусть \\(s_i=|V_i|\\), \\(e_i\\) — число чёрных рёбер внутри \\(V_i\\), \\(\\delta_i\\) — наименьшая чёрная степень в \\(V_i\\). На первом шаге \\(e_1\\le s_1\\), поэтому \\(\\delta_1\\le2e_1/s_1\\le2\\).\n\nЧтобы построить \\(V_i\\) из \\(V_{i-1}\\), выберем вершину \\(u_i\\) чёрной степени \\(\\delta_{i-1}\\), удалим её и всех её чёрных соседей, а из оставшихся возьмём наибольшее чётное множество \\(A\\). Все лучи из \\(u_i\\) в \\(A\\) свободны: чёрных нет по выбору, а белые рёбра прошлых шагов имели центры \\(u_j\\notin V_j\\), так что внутри текущего множества белых рёбер нет. На графе старых чёрных рёбер внутри \\(A\\) мысленно разыграем лемму о половине. Когда Первый выбирает \\(x\\), Белла красит \\(u_ix\\). Если Чингиз отвечает лучом \\(u_iy\\) к ещё не выбранной вершине \\(A\\), считаем, что Второй выбрал \\(y\\); иначе Второму отдаём любую свободную вершину. Предписанный Белле луч всегда свободен: вершина, луч к которой Чингиз уже занял, тогда же отдана Второму. Множество вершин Первого объявим \\(V_i\\). Тогда\n\\[\ns_i=\\left\\lfloor\\frac{s_{i-1}-1-\\delta_{i-1}}2\\right\\rfloor, \\tag{5}\n\\]\nа по лемме и с учётом не более одного нового чёрного ребра на белый ход\n\\[\ne_i\\le\\frac{e_{i-1}}4+s_i. \\tag{6}\n\\]\n\nДокажем индукцией, что при \\(1\\le i\\le n-4\\)\n\\[\n2^{n-i}-7\\le s_i\\le2^{n-i},\\qquad\\delta_i\\le5. \\tag{7}\n\\]\nБаза следует из определения \\(s_1\\) и оценки \\(\\delta_1\\). Пусть утверждение известно для \\(i-1\\), обозначим \\(x=2^{n-i}\\). Тогда \\(s_{i-1}\\ge2x-7\\), \\(\\delta_{i-1}\\le5\\), и (5), включая округление вниз, даёт \\(s_i\\ge((2x-7)-5-2)/2=x-7\\); верхняя оценка очевидна. Повторяя (6), получаем\n\\[\ne_i\\le s_i+\\frac{s_{i-1}}4+\\frac{s_{i-2}}{4^2}+\\cdots