М1758. Рейтинговые переходы

Задача из журнала «Квант» (2001 год, 4 выпуск)

Условие

Всякий депутат имеет свой (абсолютный) рейтинг. В начальный момент после избрания каждый депутат вошел в одну из фракций, в которой он может подсчитать свой относительный рейтинг. Возможен переход депутата из одной фракции в другую, если его относительный рейтинг при этом увеличивается. Пусть в каждый момент времени может происходить лишь один такой переход. Докажите, что спустя конечное время все рейтинговые переходы прекратятся.

Доказательство

Всякий $i$-й депутат имеет свой абсолютный рейтинг $R_{i}$. В начальный момент (после избрания) каждый $i$-й депутат вошел в одну из фракций, в которой он может подсчитать свой относительный рейтинг: $r_{i} = \frac{R_{i}}{S}$, где $S$ – сумма всех абсолютных рейтингов данной фракции.

Обозначим через $S_{i}\left(t\right)$, $S_{j}\left(t\right)$ суммы всех абсолютных рейтингов депутатов $i$ и $j$ фракций в момент $t$. Согласно условию переход $k$-го депутата (в момент $t$) из $i$-й фракции в $j$-ю реализуется, если и только если выполняется неравенство $\frac{R_{k}}{S_{i}\left(t\right)} < \frac{R_{k}}{S_{j}\left(t\right) + R_{k}}$ т.е $S_{i}\left(t\right) > S_{j}\left(t\right) + R_{k}$, или $$R_{k} + S_{j}\left(t\right) — S_{i}\left(t\right) < 0 \tag{*}$$Отметим, что здесь получаем $S_{i}\left(t+1\right) = S_i\left(t\right) — R_{k}$ и $S_{j}\left(t+1\right) = S_j\left(t\right) + R_{k}$.

Теперь рассмотрим функцию $L\left(t\right) = \sum S^{2}_{m}\left(t\right)$, где индекс $m$ пробегает все номера фракций. Покажем, что при реализации перехода $L\left(t\right)$ убывает. Действительно, пусть в момент $t$ происходит переход $k$-го депутата из фракции $i$-й во фракцию $j$-ю. Тогда получаем $$L\left(t+1\right) = \left(S_{i}\left(t\right) — R_{k}\right)^{2} + \left(S_{j}\left(t\right) + R_{k}\right)^{2} + \sum S^{2}_{n}\left(t+1\right)$$где $n$ отлично от $i$ и $j$. Раскрывая первые два квадрата и находим $$L\left(t+1\right) = S^{2}_{i}\left(t\right) + S^{2}_{j}\left(t\right) + 2R_{k}\left(R_k + S_{j}\left(t\right) — S_{i}\left(t\right)\right) + \sum S^{2}_{n}\left(t+1\right)$$С учетом неравенства $\left(*\right)$ устанавливаем $L\left(t+1\right) < L\left(t\right)$. Но функция $L$ может принимать лишь конечное число значений, поэтому ее убывание не может продолжаться сколь угодно долго.

В.Ильичев

М749* Задача на различные доказательства неравенства

Задача из журнала «Квант»(1982 год, 6 выпуск)

Условие

a) Докажите, что если $x_1, x_2, x_3$— положительные числа, то $$\frac{x_1}{x_2 + x_3} + \frac{x_2 }{x_3+x_1} + \frac{x_3}{x_1 + x_2} \ge \frac{3}{2};$$ при каком условии то неравенство превращается в равенство?

б) Докажите, что если $x_1, x_2,…,x_n (n ≥ 4)$ — положительные числа, то

$$\frac{x_1}{x_2 + x_n} + \frac{x_2}{x_3 + x_1} + … + \frac{x_{n-1}}{x_n + x_{n-2}} + \frac{x_n}{x_1 + x_{n-1}} \ge 2.$$ причем равенство возможно только при $n = 4.$

в) Докажите, что при $n>4$ неравенство пункта б) является точным в том смысле, что ни при каком $n$ число $2$ в правой части нельзя заменить на большее.

А. Прокопьев

Решение

a) Пусть $ a=x_2+x_3, b=x_3+x_1, c=x_1+x_2.$ Тогда $x_1=\frac{b+c-a}{2},$ $x_2 = \frac{a+c-b}{2},$ $x_3=\frac{a+b-c}{2}, $ и левая часть неравенства перепишется так: $ \frac{b+c-a}{2a}+\frac{a+c-b}{2b}+\frac{a+b-c}{2c}=$ $\frac{1}{2}(\frac{b}{a}+\frac{a}{b})+\frac{1}{2}(\frac{c}{a}+\frac{a}{c})+\frac{1}{2}(\frac{b}{c}+\frac{c}{b})-\frac{3}{2}.$ Каждая из скобок в этом выражении, не меньше $2$ в силу известного неравенства $x + \frac{1}{x} \ge 2$ при $x > 0.$ Поэтому вся левая часть не меньше $3-\frac{3}{2} = \frac{3}{2}.$ А так как $x + \frac{1}{x} = 2$ только при $x = 1,$ доказанное неравенство обращается в равенство только при $a = b = c.$

б) Докажем неравенство индукцией по $n.$ При $n = 4$ оно очевидно: $$\frac{x_1}{x_2+x_4}+\frac{x_2}{x_3+x_1} + \frac{x_3}{x_4+x_2}+\frac{x_4}{x_1+x_3} = \frac{x_1+x_3}{x_2+x_4}+\frac{x_2+x_4}{x_1+x_3} \ge 2$$ равенство возможно в том и в только в том случае, когда $x_1 + x_3 = x_2 + x_4.$

Докажем теперь неравенство для произвольных положительных чисел $ x_1, …, x_{n + 1},$ предполагая, что оно справедливо для любых $ n (n \ge 4)$ положительных чисел. Выберем наименьшее из чисел $ x_1, …, x_{n + 1}.$ Поскольку они входят в неравенство симметрично, можно, не ограничивая общности, считать, что это $ x_{n + 1}.$ Тогда $x_{n+1} > 0,$ $x_{n+1} \le x_n$ и $x_{n + 1} \le x_1,$ и поэтому $$\frac{x_1}{x_2 + x_{n+1}} + \frac{x_2}{x_3+x_1} + … + \frac{x_n}{x_{n + 1}+x_{n- 1}}+$$ $$ +\frac{x_{n+1}}{x_1+x_n}> \frac{x_1}{x_2+x_n}+\frac{x_2}{x_3 + x_1} + … + \frac{x_n}{x_1 + x_{n-1}} \ge 2 $$

(последнее неравенство выполняется по предположению индукции). Попутно получаем, что при $n>4$ равенство невозможно.

в) Числа $x_1, …, x_n$ удобно расставлять по окружности; тогда каждое слагаемое в левой части рассматриваемого неравенства есть одно из этих чисел, деленное на сумму двух соседних с ним. При $n = 2k$ определим $x_i$ так, как показано на рисунке 1, а при $n = 2k+1$ — как на рисунке 2.

 

В первом случае получим сумму $$2(\frac{1}{q+1}+ \frac{q}{q^2+1}+\frac{q^2}{q^3+q}+ … + \frac{q^{k-1}}{q^{k-1}+q^{k-2}})= 2(1 + \frac{(k-2)q}{g^2+1}),$$

а во втором —

$$ \frac{1}{2q} + 2(\frac{q}{q^2+1} + \frac{q^2}{q^3 + q} + … + \frac{q^k}{q^k+q^{k-1}})=\frac{1}{2q} + \frac{2(k-1)q}{q^2+1}-\frac{2q}{q+1}=$$ $$=2+(\frac{1}{2q} + \frac{2(k-1)q}{q^2+1} — \frac{2}{q+1}).$$

В обоих случаях при достаточно большом $q$ значение левой части будет сколь угодно близко к $2$, поэтому число $2$ в неравенстве на большее заменить нельзя.

А. Егоров

 

M1699. Неравенство

Задача из журнала «Квант» (1999 год, 5 выпуск)

Условие

Докажите, что при любом натуральном $n$ справедливо неравенство $$\left \{ \sqrt{1} \right \} + \left \{ \sqrt{2} \right \} +\dots+ \left \{ \sqrt{n} \right \} \leqslant \frac{n^2-1}{2}$$
(Здесь $\left \{ k \right \}$ — дробная часть числа $k$.)

Решение

При $n = 1$ неравенство обращается в равенство $0 = 0$. При $n > 1$ докажем, что сумма дробных частей на каждом промежутке между двумя последовательными квадратами удовлетворяет неравенству $$\sum_{k=m^2}^{m^2+2m} \left \{ \sqrt{k} \right \} \leqslant \frac{2m+1}{2}.\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;(1)$$

Нетрудно проверить (например, с помощью очевидного неравенства $\displaystyle \sqrt{m^2+x} \leqslant m + \frac{x}{2m}$), что
$$\sqrt{m^2+a} + \sqrt{m^2 + m -a} \leqslant 2m+1$$
при $0 \leqslant a \leqslant m$.

Следовательно, $$\left \{ \sqrt{m^2+a} \right \} + \left \{ \sqrt{m^2 + 2m -a} \right \} \leqslant 1\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;(2)$$

Просуммировав эти неравенства при $a =0,1,\dots,m-1$ и неравенство $\displaystyle \left \{ m^2+m \right \} \leqslant \frac{1}{2}$ (получаемое деление на $2$ обеих частей $(2)$ при $a = m$), приходим к неравенству $(1)$. Суммируя неравенство $(1)$ по всем $m$ от $1$ до $n-1$, получаем $$\sum_{k=1}^{n^2-1} \left \{ \sqrt{k} \right \} \leqslant \frac{n^2-1}{2}.$$

Остается заметить, что $\left \{ \sqrt{n^2} \right \} = 0.$

А. Храбров

М1304. Задача о связи вписанной и описанной окружностей в треугольнике

Задача из журнала «Квант» (1991)

Условие

Пусть [latex]I[/latex] — центр вписанной окружности в треугольнике [latex]ABC[/latex], [latex]R[/latex] — радиус описанной окружности. Докажите, что $${R}^{3}\geq IA\cdot IB\cdot IC.$$

Иллюстрация к задаче

kvant (2)

Решение

Пусть [latex]\alpha, \beta, \gamma[/latex] — углы треугольника, [latex]x, y, z[/latex] — отрезки, на которые точки касания с вписанной окружностью разбивают его стороны. Поскольку радиус [latex]R[/latex] равен половине отношения стороны к синусу к синусу противоположного угла (теорема синусов), а отрезки [latex]IA, IB, IC[/latex] выражаются через [latex]x, y, z[/latex] и углы из прямоугольных треугольников , требуемое неравенство можно переписать так: $\frac{\left(x+y\right)\left(y+z\right)\left(z+x\right)}{8\sin\alpha\cdot\sin\beta\cdot\sin\gamma}\geq$$\frac{xyz}{\cos\left(\alpha/2\right)\cos\left(\beta/2\right)\cos\left(\gamma/2\right)}$ или $\left(x+y\right)\left(y+z\right)\left(z+x\right)\geq$$64xyz\sin\left(\alpha/2\right)\sin\left(\beta/2\right)\sin\left(\gamma/2\right)$

С другой стороны, пользуясь теоремой косинусов, получаем $\sin^2\left(\alpha/2\right)=$$\frac{1}{2}\left(1-\frac{b^2+c^2-a^2}{2bc}\right)=$$\frac{\left(p-b\right)\left(p-c\right)}{bc}=$$\frac{yz}{\left(x+y\right)\left(x+z\right)}.$

Аналогично, $$\sin^2\left(\beta/2\right)=\frac{xz}{\left(x+y\right)\left(y+z\right)},$$ $$\sin^2\left(\beta/2\right)=\frac{xy}{\left(x+z\right)\left(y+z\right)},$$ тогда $\sin\left(\alpha/2\right)\sin\left(\beta/2\right)\sin\left(\gamma/2\right)=$$\frac{xyz}{\left(x+y\right)\left(x+z\right)\left(y+z\right)}$ и неравенство имеет вид $${\left(x+y\right)\left(x+z\right)\left(y+z\right)}\geq8xyz,$$ для доказательства которого достаточно перемножить три очевидных неравенства:

  1. $x+y\geq2\sqrt{xy}.$
  2. $y+z\geq2\sqrt{yz}.$
  3. $x+z\geq\sqrt{xz}.$

Еще одно решение задачи можно получить, используя равенства:

  • $IA=\frac{r}{\sin\left(\alpha/2\right)}.$
  • $IB=\frac{r}{\sin\left(\beta/2\right)}.$
  • $IC=\frac{r}{\sin\left(\gamma/2\right)}.$

$$r=4R\sin\left(\alpha/2\right)\sin\left(\beta/2\right)\sin\left(\gamma/2\right).$$ Имеем: $R^2\geq4r^2,$ т. е. $R\geq2r.$

Это хорошо известное неравенство можно доказать чисто геометрически (например, опираясь на то, что радиус окружности, проходящей через середины сторон треугольника [latex]ABC[/latex], равный [latex]R/2[/latex], не меньше [latex]r[/latex]).

Н. Васильев. В. Сендеров. А.Соловьев

М1396. Выполняется ли неравенство?

Задача из журнала «Квант» (1993, №5, M1396)

Условие

Докажите, что для любых положительных чисел $a_{k},b_{k} (k=1,2,…,n)$ выполнено неравенство $$\sum\limits_{k=1}^{n}{\frac{a_{k}b_{k}}{a_{k}+b_{k}}}\leq \frac{AB}{A+B}$$где $A=a_{1}+…a_{n}, B=b_{1}+…+b_{n}$.

Первое решение

Доказательство проведем по индукции. Докажем неравенство для $n=2$. Положим $v=a_{1}+b_{1},u=a_{2}+b_{2}$: $$a_{1}b_{1}u^2+(a_{1}b_{1}+a_{2}b_{2})uv+a_{2}b_{2}v^2\leq uv(a_{1}+a_{2})(b_{1}+b_{2})$$ или $$a_{1}b_{1}u^2-(a_{2}b_{1}+a_{1}b_{2})uv+a_{2}b_{2}v^2\leq 0$$Обозначим $t=u/v$. Перепишем неравенство: $$v^2a_{1}b_{1}(t-\frac{b_{2}}{b_{1}})(t-\frac{a_{2}}{a_{1}})\leq 0$$Подставляя $t=(a_{2}+b_{2})/(a_{1}+b_{1})$, приходим к эквивалентному неравенству: $$(b_{2}a_{1}-b_{1}a_{2})(a_{2}b_{1}-a_{1}b_{2})\leq 0$$ или $$-(b_{2}a_{1}-b_{1}a_{2})^2\leq 0$$Неравенство доказано.

Еще одно, геометрическое, доказательство неравенства основано на том, что биссектриса прямого угла треугольника с катетами $a$ и $b$ равна $\sqrt{2}ab/(a+b)$.

Picture one

Пусть, для определенности $b_{2}/a_{2}\geq  b_{1}/a_{1}$. Рассмотрим конфигурацию рисунка 1. Точка пересечения биссектрисы с отрезком $AB$ лежит дальше от вершины угла $O$, чем точка $L$ $(PK/KQ=BP/QA=b_{1}/a_{1})\leq PL/LQ=b_{2}/a_{2})$.

Дадим еще одно доказательство этого неравенства, основанное на исследовании функции $$f(x)=\frac{(x+a_{2})(b_{1}+b_{2})}{x+a_{2}+b_{1}+b_{2}}-\frac{xb_{1}}{x+b_{1}}$$ где $x\geq 0$. Нетрудно проверить, что $$f(0)=\frac{a_{2}(b_{1}+b_{2})}{a_{2}+b_{1}+b_{2}}>\frac{a_{2}b_{2}}{a_{2}+b_{2}}$$ функция $f(x)$ имеет единственный минимум при $x=a_{2}b_{1}/b_{2}$, равный $a_{2}b_{2}/(a_{2}+b_{2});$ $f(x)\rightarrow b_{2}$ при $x\rightarrow +\infty$ (рис. 2). Отсюда легко вывести, что $f(x)\geq a_{2}b_{2}/(a_{2}+b_{2})$ при всех $x\geq 0$. Далее, $$\sum\limits_{k=1}^{n+1}{\frac{a_{k}b_{k}}{a_{k}+b_{k}}}\leq \frac{A’B’}{A’+B’}+\frac{a_{n+1}b_{n+1}}{a_{n+1}+b_{n+1}}\leq \frac{AB}{A+B}$$ где $$A’=\sum\limits_{k=1}^{n}{a_{k}}, B’=\sum\limits_{k=1}^{n}{b_{k}}$$ Неравенство задачи доказано. Мы видели, что для $n=2$ неравенство переходит в равенство лишь при $x/b_{1}=a_{2}/b_{2}$, т.е. в случае коллинеарности векторов $(a_{1},b_{1})$ и $(a_{2},b_{2})$. Попробуем дать задаче дальнейшую векторную интерпретацию.

Второе решение

Будем рассматривать числовые функции $f(\bar{x})$, где $\bar{x}=(x,y)$ — вектор плоскости, $x>0,y>0$.

Определение. Функция $f(\bar{x})$ называется вогнутой (или выпуклой вверх), если для любых векторов $\bar{x}_{1}$ и $\bar{x}_{2}$ выполняется неравенство $$\frac{f(\bar{x}_{1})+f(\bar{x}_{2})}{2}\leq f(\frac{\bar{x}_{1}+\bar{x}_{2}}{2}) (1)$$
Замечание. Геометрический смысл вогнутости ясен из рисунка 3. Вогнутыми являются, например,  функции $y=ax+b, y=-x^{2}+bx+c, y=-1/(dx+e)$, где $dx+e>0$.Рассмотрим функцию $$f(\bar{x})=\frac{xy}{x+y}$$

Picture (2)

При $n=2$ утверждение задачи означает, что функция вогнута; при произвольном $n$ утверждение означает, что выполнено неравенство $$\frac{1}{n}\sum\limits_{i=1}^{n}{f({\bar{x}_{i}})}\leq f(\frac{1}{n}\sum\limits_{i=1}^{n}{{\bar{x}_{i}}}) (2)$$

Теорема. Для любой вогнутой (т.е. удовлетворяющей неравенству $(1)$) функции выполнено также и неравенство $(2)$.
Доказательство. Предполагая справедливость теоремы при $n=m$, докажем ее справедливость при $n=2m$. Имеем: $$f(\frac{{\bar{x}_{1}}+{\bar{x}_{2}}+…+{\bar{x}_{2m}}}{2m})=$$ $$=f(\frac{\frac{{\bar{x}_{1}}+{\bar{x}_{2}}}{2}+…+\frac{{\bar{x}_{2m-1}}+{\bar{x}_{2m}}}{2}}{m})\geq$$ $$\geq \frac{f(\frac{{\bar{x}_{1}}+{\bar{x}_{2}}}{2})+…+f(\frac{{\bar{x}_{2m-1}}+{\bar{x}_{2m}}}{2})}{m}\geq$$ $$\geq \frac{\frac{f({\bar{x}_{1}})+f({\bar{x}_{2}})}{2}+…+\frac{f({\bar{x}_{2m-1}})+f({\bar{x}_{2m}})}{2}}{m}=$$ $$=\frac {f({\bar{x}_{1}})+…+f({\bar{x}_{2m}})}{2m}$$ Таким образом теорема справедлива при $n=2m$. Положим теперь $n+p=2m$. Тогда $$f(\frac{{\bar{x}_{1}}+…+{\bar{x}_{n}}+{\bar{y}_{1}}+…+{\bar{y}_{p}}}{n+p})\geq$$ $$\geq\frac {f({\bar{x}_{1}})+…+f({\bar{x}_{n}})+f({\bar{y}_{1}})+…+f({\bar{y}_{p}})}{n+p} (3)$$ Положим $${\bar{y}_{1}}=…={\bar{y}_{p}}=\frac{{\bar{x}_{1}}+…+{\bar{x}_{n}}}{n}$$ тогда $${\bar{y}_{1}}+…+{\bar{y}_{p}}=\frac{{\bar{x}_{1}}+…+{\bar{x}_{n}}}{n}\cdot p$$ Следовательно, $$f(\frac{{\bar{x}_{1}}+…+{\bar{x}_{n}}+{\bar{y}_{1}}+…+{\bar{y}_{p}}}{n+p})=f(\frac{{\bar{x}_{1}}+…+{\bar{x}_{n}}}{n})$$ С другой стороны, $$\frac{f({\bar{x}_{1}})+…+f({\bar{x}_{n}})+f({\bar{y}_{1}})+…+f({\bar{y}_{p}})}{n+p}=$$ $$=\frac{f({\bar{x}_{1}})+…+f({\bar{x}_{n}})+pf(\frac{{\bar{x}_{1}}+…+{\bar{x}_{n}}}{n})}{n+p}$$ Из неравенства $(3)$ получаем: $$f(\frac{{\bar{x}_{1}}+…+{\bar{x}_{n}}}{n})\geq \frac{f({\bar{x}_{1}})+…+f({\bar{x}_{n}})}{n}$$ Теорема доказана.

Перепишем теперь утверждение задачи при $n=2$; функция $f(\bar{x})=\frac{xy}{x+y}$, рассматриваемая на любой прямой $l$, является вогнутой. Докажем это утверждение.

Если $l\mid Oy$, то вогнутость функции $f(\bar{x})$ очевидна. Пусть $l$ задана уравнением $y=ax+b$. Тогда $$f(\bar{x})=\frac{ax^{2}+bx}{(a+1)x+b}$$ При $a=-1$ будет $b>0$, и $f(x)$ вогнута. Полагая $t=(a+1)x+b$ при $a\neq -1$, получаем: $f(\bar{x})=ct+d+\frac{e}{t}$, где $e=\frac{-b^{2}}{(a+1)^{2}}$

При $b=0$ функция $f(\bar{x})$ линейная, при $b\neq 0$, поскольку $t>0$, — строго вогнутая (т.е. при $\bar{x}_{1}\neq \bar{x}_{2}$ неравенство $(1)$ строгое).

Утверждение задачи доказано.