Разделы 
Дополнительно
Задача по математике - 1998
2019-01-22 
Дано дерево с $n$ вершинами, $n \geq 2$ (т. е. граф с $n$ вершинами и $n - 1$ ребром, в котором из любой вершины в любую можно пройти по ребрам, и нет циклического маршрута, проходящего по ребрам). В его вершинах расставлены числа $x_1, x_2,\cdots, x_n$, а на каждом ребре записано произведение чисел, стоящих в концах этого ребра. Обозначим через $S$ сумму чисел на всех ребрах. Докажите, что $\sqrt {n-1}(x_{1}^{2}+x_{2}^{2}+\cdots+x_{2}^{n}) \geq 2S$.
Решение:
Первое решение. Рассмотрим ребро $l$, соединяющее вершины с числами $x_i$ и $x_j$. Обозначим через $k_i(l)$ число вершин, из которых нельзя пройти в вершину $x_i$ при удалении ребра $l$. Аналогично, число вершин, из которых нельзя пройти в вершину $x_j$ при удалении ребра $l$, обозначим $k_j(l)$. Ясно, что $1 \leq k_i(1),k_j(l) \leq n - 1, k_i(l) + k_j(l) = n$. Кроме того, для каждого $i$ сумма $\sum_{ }^{ }k_i(l))$ равна $n - 1$ (сумма берется по всем ребрам $l$, выходящим из $x_i$), так как из вершины $x_i$ можно пройти по ребрам дерева в каждую из оставшихся $n - 1$ вершин единственным несамопересекающимся путем.
Согласно неравенству между средним арифметическим и средним геометрическим, для данного ребра $l$ получим:
$\frac{k_i(l)}{\sqrt{n-1}}x_i^2 + \frac{k_j(l)}{\sqrt{n-1}}x_j^2 \geq 2\sqrt{\frac{k_i(l)k_j(l)}{n-1}}|x_ix_j|\geq 2x_ix_j$. (*)
Последнее неравенство верно, так как $k_i(l)k_j(l) = \frac{k_i(l)k_j(l)^2 - (k_i(l) - k_j(l)}{4} \geq \frac{n^2 - ((n-1) - 1)^2}{4} = n - 1$.
Сложив неравенства (*) по всем ребрам, получим требуемое неравенство.
Второе решение. Будем проводить операции, не изменяющие чисел в вершинах и не уменьшающие сумму $S$ чисел на ребрах. Достаточно доказать неравенство по окончании этих операций.
Вначале заменим числа в вершинах на их модули, т. е. далее считаем, что $x_1, x_2, \cdots, x_n \geq 0$.
Выберем наибольшее из чисел $x_i$, пусть это число $x_1$. Если нашлась вершина с числом $x_i, i \not\equiv 1$, из которой выходит ровно одно ребро l, ведущее в вершину $x_j, j \neq 1$, то произведем перестройку: удалим ребро l, и соединим ребром вершины с числами $x_i$ и $x_1$. Полученный граф остается деревом, так как количество ребер не изменилось и по-прежнему из любой вершины можно пройти по ребрам в любую другую. После перестройки сумма $S$ изменяется на $x_ix_1 - x_ix_j \geq 0$. Производим перестройки, пока это возможно. Поскольку при каждой перестройке число ребер, выходящих из вершины с числом $x_1$, увеличивается, через конечное число шагов мы придем к ситуации, когда невозможно сделать перестройку. В этой ситуации вершина с числом $x_1$ соединена ребром с каждой из оставшихся $n - 1$ вершин. В самом деле, предположим, что некоторая вершина не соединена ребром с вершиной $x_1$. Пройдем в нее из $x_1$ по ребрам (не проходя дважды по одному ребру) и продолжим этот путь, пока это возможно. Ясно, что концом этого пути может являться вершина, из которой выходит ровно одно ребро, причем не в вершину с числом $x_1$. Но это означает, что можно произвести перестройку, - противоречие.
Таким образом, для конечной ситуации $S = x_1x_2 + x_1x_3 +\cdots + x_1x_n$. Исходное неравенство верно, поскольку $\sqrt{n-1}(x_1^2 + x_2^2 + \cdots + x_n^2) = \left (\frac{x_1^2}{\sqrt{n-1}} + \sqrt{n-1}x_2^2 \right ) + \left (\frac{x_1^2}{\sqrt{n-1}} + \sqrt{n-1}x_3^2 \right ) + \left (\frac{x_1^2}{\sqrt{n-1}} + \sqrt{n-1}x_n^2 \right ) \geq 2x_1x_2 + 2x_1x_3 + \cdots + 2x_1x_n$.
Дано дерево с $n$ вершинами, $n \geq 2$ (т. е. граф с $n$ вершинами и $n - 1$ ребром, в котором из любой вершины в любую можно пройти по ребрам, и нет циклического маршрута, проходящего по ребрам). В его вершинах расставлены числа $x_1, x_2,\cdots, x_n$, а на каждом ребре записано произведение чисел, стоящих в концах этого ребра. Обозначим через $S$ сумму чисел на всех ребрах. Докажите, что $\sqrt {n-1}(x_{1}^{2}+x_{2}^{2}+\cdots+x_{2}^{n}) \geq 2S$.
Решение:
Первое решение. Рассмотрим ребро $l$, соединяющее вершины с числами $x_i$ и $x_j$. Обозначим через $k_i(l)$ число вершин, из которых нельзя пройти в вершину $x_i$ при удалении ребра $l$. Аналогично, число вершин, из которых нельзя пройти в вершину $x_j$ при удалении ребра $l$, обозначим $k_j(l)$. Ясно, что $1 \leq k_i(1),k_j(l) \leq n - 1, k_i(l) + k_j(l) = n$. Кроме того, для каждого $i$ сумма $\sum_{ }^{ }k_i(l))$ равна $n - 1$ (сумма берется по всем ребрам $l$, выходящим из $x_i$), так как из вершины $x_i$ можно пройти по ребрам дерева в каждую из оставшихся $n - 1$ вершин единственным несамопересекающимся путем.
Согласно неравенству между средним арифметическим и средним геометрическим, для данного ребра $l$ получим:
$\frac{k_i(l)}{\sqrt{n-1}}x_i^2 + \frac{k_j(l)}{\sqrt{n-1}}x_j^2 \geq 2\sqrt{\frac{k_i(l)k_j(l)}{n-1}}|x_ix_j|\geq 2x_ix_j$. (*)
Последнее неравенство верно, так как $k_i(l)k_j(l) = \frac{k_i(l)k_j(l)^2 - (k_i(l) - k_j(l)}{4} \geq \frac{n^2 - ((n-1) - 1)^2}{4} = n - 1$.
Сложив неравенства (*) по всем ребрам, получим требуемое неравенство.
Второе решение. Будем проводить операции, не изменяющие чисел в вершинах и не уменьшающие сумму $S$ чисел на ребрах. Достаточно доказать неравенство по окончании этих операций.
Вначале заменим числа в вершинах на их модули, т. е. далее считаем, что $x_1, x_2, \cdots, x_n \geq 0$.
Выберем наибольшее из чисел $x_i$, пусть это число $x_1$. Если нашлась вершина с числом $x_i, i \not\equiv 1$, из которой выходит ровно одно ребро l, ведущее в вершину $x_j, j \neq 1$, то произведем перестройку: удалим ребро l, и соединим ребром вершины с числами $x_i$ и $x_1$. Полученный граф остается деревом, так как количество ребер не изменилось и по-прежнему из любой вершины можно пройти по ребрам в любую другую. После перестройки сумма $S$ изменяется на $x_ix_1 - x_ix_j \geq 0$. Производим перестройки, пока это возможно. Поскольку при каждой перестройке число ребер, выходящих из вершины с числом $x_1$, увеличивается, через конечное число шагов мы придем к ситуации, когда невозможно сделать перестройку. В этой ситуации вершина с числом $x_1$ соединена ребром с каждой из оставшихся $n - 1$ вершин. В самом деле, предположим, что некоторая вершина не соединена ребром с вершиной $x_1$. Пройдем в нее из $x_1$ по ребрам (не проходя дважды по одному ребру) и продолжим этот путь, пока это возможно. Ясно, что концом этого пути может являться вершина, из которой выходит ровно одно ребро, причем не в вершину с числом $x_1$. Но это означает, что можно произвести перестройку, - противоречие.
Таким образом, для конечной ситуации $S = x_1x_2 + x_1x_3 +\cdots + x_1x_n$. Исходное неравенство верно, поскольку $\sqrt{n-1}(x_1^2 + x_2^2 + \cdots + x_n^2) = \left (\frac{x_1^2}{\sqrt{n-1}} + \sqrt{n-1}x_2^2 \right ) + \left (\frac{x_1^2}{\sqrt{n-1}} + \sqrt{n-1}x_3^2 \right ) + \left (\frac{x_1^2}{\sqrt{n-1}} + \sqrt{n-1}x_n^2 \right ) \geq 2x_1x_2 + 2x_1x_3 + \cdots + 2x_1x_n$.
