#4 Экстремальный принцип

Пусть \(M\) — максимальный элемент множества. По условию число \(f(M)\) принадлежит тому же множеству и \(f(M)>M\). Но это противоречит максимальности \(M\). Следовательно, такого соответствия не существует.

Начнём с произвольной точки \(v_1\) и каждый раз будем переходить по стрелке: \(v_1,v_2,v_3,\ldots\). Точек конечное число, поэтому какая-то точка повторится: \(v_i=v_j\) при \(i

Тогда отрезок последовательности \(v_i,v_{i+1},\ldots,v_{j-1},v_j=v_i\) образует цикл по стрелкам. Значит, такой цикл существует.

Предположим, что вершина \(v_k\) соединена с вершиной \(u\), которая не входит в путь. Тогда последовательность \(v_1v_2\ldots v_k u\) является путём и имеет на одну вершину больше.

Это противоречит выбору исходного пути как максимального по длине. Значит, все соседи \(v_k\) лежат на пути.

Выберем в дереве путь максимальной длины \(v_1v_2\ldots v_k\). Если у вершины \(v_k\) есть сосед, не лежащий на пути, путь можно продолжить, что невозможно.

Если \(v_k\) соединена с какой-то более ранней вершиной пути, кроме \(v_{k-1}\), то возникнет цикл. В дереве циклов нет. Значит, единственный сосед \(v_k\) — это \(v_{k-1}\), и степень \(v_k\) равна \(1\).

Пусть \([a,b]\) — отрезок с минимальным правым концом \(b\). Рассмотрим любой другой отрезок \([c,d]\). По выбору \(b\) имеем \(b\le d\).

Так как \([a,b]\) и \([c,d]\) пересекаются, не может быть \(b

Рассмотрим все связные подграфы, содержащие все вершины исходного графа. Среди них выберем подграф \(H\) с минимальным числом рёбер. Такой подграф существует, так как исходный граф входит в рассмотрение.

Если в \(H\) есть цикл, удалим одно ребро этого цикла. Между его концами всё ещё есть путь по остальной части цикла, поэтому связность не нарушается. Получается связный остовный подграф с меньшим числом рёбер, противоречие.

Значит, циклов в \(H\) нет. Искомый граф получен удалением лишних рёбер.

Выберем самый длинный путь \(v_1v_2\ldots v_k\). Все соседи вершины \(v_k\) лежат на этом пути, иначе путь можно было бы продолжить.

Так как степень \(v_k\) не меньше \(2\), кроме соседа \(v_{k-1}\) у неё есть ещё один сосед среди вершин пути. Пусть это \(v_i\), где \(i

В каждой паре \(\{i,2n+1-i\}\) нельзя взять оба числа, потому что их сумма равна \(2n+1\). Значит, из каждой пары взято не более одного числа.

Предположим, из некоторой пары не взято ни одного числа. Тогда можно добавить в \(A\) одно из чисел этой пары: его единственный партнёр по сумме \(2n+1\) тоже отсутствует. Условие не нарушится, что противоречит максимальности по включению.

Следовательно, из каждой пары взято ровно одно число.

Предположим, что непокрытые вершины \(x\) и \(y\) соединены ребром \(xy\). Так как обе вершины не покрыты, ребро \(xy\) не имеет общих концов ни с одним выбранным ребром.

Тогда \(xy\) можно добавить к выбранному множеству, и рёбра всё ещё будут попарно не иметь общих концов. Это противоречит условию, что добавить ребро нельзя. Значит, такого ребра нет.

Имеем \(8=3+5\), \(9=3+3+3\), \(10=5+5\). Предположим, что существуют контрпримеры, и пусть \(n\) — наименьший из них.

Так как \(8,9,10\) представимы, то \(n\ge 11\). Тогда \(n-3\ge 8\), и по минимальности \(n\) число \(n-3\) представимо: \(n-3=3a+5b\).

Следовательно, \(n=3(a+1)+5b\), что противоречит тому, что \(n\) — контрпример. Значит, утверждение верно для всех \(n\ge 8\).

Инверсией назовём пару позиций \(i

Если меняются соседние числа \(x>y\), то пара \((x,y)\) перестаёт быть инверсией. Отношения этих двух чисел со всеми остальными числами не меняют общего числа инверсий, потому что они соседние. Поэтому число инверсий уменьшается на \(1\).

Оно не может уменьшаться бесконечно, значит, процесс завершится. В конце нет соседних чисел в неправильном порядке. Тогда вся последовательность возрастает.

Ответ: \(n-2\). Сначала покажем, что \(n-1\) невозможно. Если \(n-1\) человек знакомы со всеми, то оставшийся человек знаком с каждым из этих \(n-1\) людей. Значит, он тоже знаком со всеми, что противоречит условию.

Покажем достижимость. Пусть два человека \(A\) и \(B\) не знакомы друг с другом, а все остальные знакомы со всеми. Тогда ровно \(n-2\) человек знакомы со всеми остальными, а \(A\) и \(B\) не знакомы со всеми. Условие выполнено.

Выберем направленный путь максимальной длины \(v_1\to v_2\to\cdots\to v_k\). Предположим, что есть вершина \(u\), не лежащая на пути.

Если \(u\to v_1\), то можно поставить \(u\) перед \(v_1\), получив более длинный путь. Поэтому \(v_1\to u\). Если \(v_k\to u\), то можно поставить \(u\) после \(v_k\), значит, \(u\to v_k\).

Идя слева направо, найдём первый индекс \(j\), для которого \(u\to v_j\). Тогда \(j>1\), а по минимальности \(j\) имеем \(v_{j-1}\to u\). Следовательно, можно вставить \(u\) между \(v_{j-1}\) и \(v_j\): \(v_1\to\cdots\to v_{j-1}\to u\to v_j\to\cdots\to v_k\). Это более длинный путь, противоречие.

Значит, внешней вершины нет, и путь содержит все вершины.

Пусть две соседние невыбранные клетки \(i\) и \(i+1\) имеют разные цвета. Тогда пара \((i,i+1)\) подходит по условию и не пересекается ни с одной выбранной парой, потому что обе клетки не выбраны.

Её можно добавить к текущему множеству пар, сохранив все условия. Это противоречит максимальности по включению. Следовательно, таких соседних невыбранных клеток нет.

Выберем самый длинный путь \(v_1v_2\ldots v_m\). Все соседи вершины \(v_m\) лежат на этом пути, иначе путь можно было бы продолжить.

У вершины \(v_m\) не меньше \(k\) соседей среди вершин \(v_1,\ldots,v_{m-1}\). Пусть \(v_i\) — самый ранний из этих соседей на пути. Тогда среди вершин \(v_i,v_{i+1},\ldots,v_{m-1}\) находится не меньше \(k\) соседей вершины \(v_m\), поэтому \(m-i\ge k\).

Рёбра пути от \(v_i\) до \(v_m\) вместе с ребром \(v_m v_i\) образуют цикл \(v_i v_{i+1}\ldots v_m v_i\). В нём \(m-i+1\ge k+1\) вершин.

Пусть сумма всех чисел из \(A\) равна \(S\). У множества \(A\) есть \(2^k\) подмножеств, если считать и пустое. По условию суммы различных непустых подмножеств различны; сумма пустого подмножества равна \(0\) и не совпадает с ними, потому что все числа положительны.

Значит, получаются \(2^k\) различных целых сумм. Каждая из них лежит между \(0\) и \(S\), а в этом промежутке ровно \(S+1\) целых чисел. Поэтому \(S+1\ge 2^k\), откуда \(S\ge 2^k-1\).

Рассмотрим единственный путь от \(A\) к \(B\). Если степень \(A\) больше \(1\), то у \(A\) есть сосед \(C\), отличный от следующей вершины на пути к \(B\).

В дереве путь от \(C\) к \(B\) проходит через \(A\), поэтому расстояние \(CB\) на \(1\) больше расстояния \(AB\). Это противоречит максимальному выбору пары \(A,B\). Значит, степень \(A\) равна \(1\). Аналогично степень \(B\) равна \(1\).

Для каждого места \(i\) обозначим через \(p_i\) длину наибольшей возрастающей подпоследовательности, заканчивающейся на \(a_i\), а через \(q_i\) — длину наибольшей убывающей подпоследовательности, заканчивающейся на \(a_i\).

Предположим, что нет ни возрастающей, ни убывающей подпоследовательности длины \(n+1\). Тогда все пары \((p_i,q_i)\) принимают значения из множества \(\{1,\ldots,n\}\times\{1,\ldots,n\}\), то есть возможны только \(n^2\) пар.

Покажем, что пары для разных \(i\) различны. Если \(ip_i\). Если \(a_i>a_j\), то аналогично \(q_j>q_i\). В обоих случаях пары различны.

Но элементов \(n^2+1\), а различных пар не больше \(n^2\). Противоречие. Значит, нужная подпоследовательность существует.

Выберем вершину \(v\) с максимальной исходящей степенью. Пусть \(u\) — вершина, в которую нет дуги из \(v\). Тогда в турнире обязательно \(u\to v\).

Предположим, что ни один исходящий сосед \(w\) вершины \(v\) не имеет дуги \(w\to u\). Тогда для каждого такого \(w\) дуга направлена \(u\to w\). Кроме того, \(u\to v\). Значит, \(u\) побеждает всех, кого побеждает \(v\), и ещё саму вершину \(v\). У \(u\) исходящих дуг больше, чем у \(v\), противоречие.

Следовательно, найдётся исходящий сосед \(w\) вершины \(v\), для которого \(w\to u\). Тогда \(v\to w\to u\). Для вершин, которые \(v\) побеждает напрямую, путь имеет длину \(1\). Поэтому \(v\) достигает всех вершин за не более чем \(2\) шага.

Пусть два пути максимальной длины \(P\) и \(Q\) не имеют общих вершин. Обозначим их длину через \(L\). Так как граф связен, существует путь, соединяющий некоторую вершину \(x\) пути \(P\) с некоторой вершиной \(y\) пути \(Q\). Выберем такой соединяющий путь кратчайшим; тогда его внутренняя часть не пересекает \(P\) и \(Q\).

Вершина \(x\) делит путь \(P\) на две части, суммы длин которых равна \(L\). Одна из этих частей имеет длину не меньше \(\frac{L}{2}\). Аналогично, вершина \(y\) делит путь \(Q\) на две части, и одна часть имеет длину не меньше \(\frac{L}{2}\).

Возьмём более длинную часть пути \(P\), затем соединяющий путь от \(x\) к \(y\), затем более длинную часть пути \(Q\). Получается простой путь: внутренние вершины соединяющего пути не лежат на \(P\) и \(Q\), а сами \(P\) и \(Q\) не пересекаются.

Его длина не меньше \(\frac{L}{2}+1+\frac{L}{2}=L+1\), потому что соединяющий путь имеет положительную длину. Это больше максимальной длины \(L\), противоречие. Следовательно, два самых длинных пути должны иметь общую вершину.