Метка: Международная математическая олимпиада

М1761. Ящики фокусника

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

Условие

У фокусника [latex]100[/latex] карточек, занумерованных числами от [latex]1[/latex] до [latex]100.[/latex] Он раскладывает все карточки в три ящика – красный, белый и синий – так, чтобы в каждом ящике лежала хотя бы одна карточка. Один из зрителей выбирает два из трех ящиков, вынимает из них по одной карточке и объявляет сумму номеров вынутых карточек. Зная эту сумму, фокусник определяет тот ящик, из которого карточки не вынимались. Сколькими различными способами можно разложить карточки по ящикам так, чтобы этот фокус всегда удавался?
(Способы, при которых хотя бы одна карточка попадает в разные ящики, считаются различными.)

Ответ: [latex]12.[/latex]

Решение

Пусть карточка [latex]1[/latex] (или число [latex]1[/latex]) лежит в красном ящике
(сокращенно КЯ), а карточка с наименьшим числом [latex]k,[/latex] не лежащая в КЯ, лежит в белом ящике (БЯ). Тогда [latex]k-1[/latex] находится в КЯ.
По условию, в синем ящике (СЯ) есть хотя бы одна карточка; пусть [latex]n[/latex] – наименьшее число (т.е. карточка с наименьшим числом) в СЯ [latex]\to [/latex] [latex]n > k.[/latex] Если [latex]n-1[/latex] лежит в КЯ, то зритель может вытащить либо [latex]n-1[/latex] и [latex]k[/latex] из КЯ и
БЯ, либо [latex]n[/latex] и [latex]k-1[/latex] из СЯ и КЯ. Суммы чисел на карточках одинаковы, значит, в этом случае фокус не удастся.
Следовательно, [latex]n-1[/latex] находится в БЯ. Предположим, что карточка [latex]2[/latex] лежит в КЯ. Тогда взяв либо [latex]2[/latex] и [latex]n-1[/latex] из КЯ и БЯ, либо [latex]1[/latex] и [latex]n[/latex] из КЯ и СЯ, получим одинаковые суммы, значит, [latex]k=2[/latex] и [latex]2[/latex] находится в БЯ.
Рассмотрим два случая.

  1. В КЯ нет других карточек, кроме [latex]1.[/latex] Покажем, что тогда [latex]n=100.[/latex] Пусть [latex]n<100.[/latex] Тогда [latex]n+1[/latex] лежит либо в БЯ, либо в СЯ. Пары карточек [latex](1, n+1)[/latex] и [latex](2, n)[/latex] с одинаковой суммой находятся в (КЯ, БЯ (СЯ)) и в (БЯ, СЯ) – фокус не удался. Значит,[latex]n=100 ,[/latex] т.е. в СЯ только одна карточка [latex]100,[/latex] в КЯ – одна карточка [latex]1,[/latex] в БЯ – карточки [latex]2, 3, \ldots , 99 .[/latex] Покажем, что в этом случае фокус всегда удается: если мы берем карточки из БЯ и КЯ, то получаем суммы [latex]3, 4, \cdots ,100 ,[/latex] если из КЯ и СЯ – сумму [latex]101,[/latex] если из БЯ и СЯ – суммы [latex]102, 103, \cdots , 199,[/latex] т.е. суммы различны.
  2. В КЯ есть другие числа, и [latex]m[/latex] – наименьшее из них. Тогда [latex]m > 2 ,[/latex] значит, [latex]m-1[/latex]не лежит в КЯ. Если [latex]m-1[/latex] находятся в БЯ, то для пар [latex](m-1, n) ,[/latex] из БЯ и СЯ и [latex](n-1, m) ,[/latex] из БЯ и СЯ фокус не удастся. Значит, [latex]m-1[/latex] лежит в СЯ.

Лемма 1

Если в двух различных ящиках лежат карточки
[latex]x[/latex] и [latex]x+1[/latex], а в третьем [latex]y[/latex] и [latex]y+1,[/latex] то фокус не удастся.

Одинаковые суммы имеют пары [latex](x, y + 1)[/latex] и [latex](x+1, y)[/latex], из разных пар ящиков.

Лемма 2

Если в одном ящике лежат карточки [latex]x[/latex] и [latex]y,[/latex] а в
двух других [latex]x+1[/latex] и [latex]y+1[/latex] соответственно, то фокус не удастся.

Доказательство дословно повторяет доказательство леммы [latex]1.[/latex]

Выше мы показали, что для каждой пары ящиков есть карточки с двумя последовательными числами, а именно
КЯ, БЯ : [latex]1,2,[/latex]
БЯ, СЯ : [latex]n-1, n,[/latex]
СЯ, БЯ : [latex]m — 1, m.[/latex]
Значит, по лемме [latex]1[/latex] ни в одном из ящиков нет карточек с двумя последовательными числами.
Далее, полагая, что [latex]y = 1,[/latex] если [latex]x[/latex] лежит в КЯ и [latex]x + 1[/latex] – в
СЯ, и [latex]y = n — 1,[/latex] если [latex]x[/latex] находится в БЯ и [latex]x + 1[/latex] – в КЯ,
по лемме [latex]2[/latex] получаем, что в этих случаях фокус не удастся.
Аналогично фокус не удастся, если [latex]x[/latex] лежит в СЯ, а [latex]x + 1[/latex] в БЯ. Итак, если а находится в КЯ, то [latex]a + 1[/latex] – в БЯ, [latex]a + 2[/latex] – в СЯ, [latex]a + 3[/latex] – в БЯ и т.д. Значит, в КЯ находятся числа, сравнимые с [latex]1[/latex] по модулю [latex]3[/latex], в БЯ – сравнимые с [latex]2,[/latex] в СЯ – делящиеся на [latex]3.[/latex] Покажем, что такое расположение карточек подходит: сумма чисел на карточках из КЯ и БЯ делится на [latex]3,[/latex] из КЯ и СЯ сравнима с [latex]1[/latex] по модулю 3, из СЯ и БЯ – с [latex]2,[/latex] т.е. всегда можно определить, из каких ящиков взяты карточки.
Мы получили, что если карточка [latex]1[/latex] лежит в КЯ, а карточка с наименьшим числом не из КЯ находится в БЯ, то есть два варианта раскладывания карточек. Аналогично рассуждаем в случае других пяти пар ящиков. Значит, всего имеется [latex]2 \times 3 \times 2 = 12[/latex] различных способов.

Н. Агаханов, А. Гайфуллин

M1710. Докажите неравенство

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

Условие

Пусть $x, \ y, \ z, \ p, \ q, \ r$ — положительные числа, такие, что $p+q+r=1$, $x^{p}y^{q}z^{r}=1.$ Докажите неравенство $$\frac{p^2x^2}{qy+rz}+\frac{q^2y^2}{px+rz}+\frac{r^2z^2}{px+qy} \geqslant \frac{1}{2}$$

Решение

Докажем вначале некоторые вспомогательные неравенства.

Лемма 1.$$\begin{equation}\label{eq:m1710_first} x^{\alpha}-\alpha x \leqslant 1 — \alpha \end{equation},$$ где $x\gt0, \ 0 \lt \alpha \lt 1.$

При $x\gt0$ рассмотрим функцию
$$f\left ( x \right )=x^{\alpha}-\alpha x,$$ где $0\lt\alpha\lt1.$ Имеем $${f}’\left ( x \right )=\alpha \left ( x^{\alpha-1}-1 \right ) \begin{cases} \gt0 \text { при } 0 \lt x \lt 1\\
\lt0 \text { при } x \gt 1
\end{cases}$$

Следовательно функция возрастает, пока $x$ изменяется в промежутке $\left ( 0; \ 1 \right ]$ и убывает в промежутке $\left [ 1; +\infty \right ).$ Отсюда ясно, что $f\left ( 1 \right )=1-\alpha$ будет наибольшим значением функции в промежутке $\left ( 0; +\infty \right ).$

Лемма 2.$$\begin{equation}\label{eq:m1710_second} a^{\alpha}b^{\beta} \leqslant \alpha a + \beta b\end{equation},$$ где $a, \ b, \ \alpha, \ \beta \gt 0, \ \alpha + \beta = 1.$

Для доказательства достаточно положить в $\eqref{eq:m1710_first}$ $x=\frac{a}{b}$ и обозначить $1- \alpha$ через $\beta.$

Лемма 3.$$a^{\alpha}b^{\beta}c^{\gamma} \leqslant \alpha a + \beta b + \gamma c,$$ где $a, \ b, \ c, \ \alpha, \ \beta, \ \gamma \gt 0, \ \alpha + \beta + \gamma=1.$

Для доказательства достаточно дважды применить неравенство $\eqref{eq:m1710_second}$:
$$a^{\alpha}b^{\beta}c^{\gamma}=a^{\alpha} \left ( b^{\frac{\beta}{\beta + \gamma}}c^{\frac{\gamma}{\beta + \gamma}} \right )^{\beta + \gamma} \leqslant \alpha a + \left ( \beta + \gamma \right )b^{\frac{\beta}{\beta + \gamma}}c^{\frac{\gamma}{\beta + \gamma}} \leqslant \\
\leqslant \alpha a + \left ( \beta + \gamma \right )+ \left ( \frac{\beta}{\beta + \gamma}b+\frac{\gamma}{\beta + \gamma}c \right ) \leqslant \alpha a + \beta b + \gamma c,$$что и требовалось доказать.

Аналогично можно было бы совершить и переход от $n$ к $n + 1$ и доказать — по методу математической индукции — общее неравенство, которое (в измененных обозначениях) имеет вид
$$\begin{equation}\label{eq:m1710_third} {a_1}^{q_1}{a_2}^{q_2} \ldots {a_n}^{q_n} \leqslant q_1a_1 + q_2a_2 + \ldots + q_na_n, \end{equation}$$ (где $a_1,\ldots,a_n, \ q_1,\ldots,q_n\gt0, \ q_1+\ldots+q_n=1$).
Равенство достигается лишь тогда, когда $a_1 = \ldots = a_n.$

Перейдем теперь к доказательству неравенства задачи.
Воспользуемся неравенством Коши — Буняковского
$$\left (u_1 u_2 + v_1 v_2 + w_1 w_2 \right )^2 \leqslant \left ( {u_1}^2 + {v_1}^2 + {w_1}^2 \right )\left ( {u_2}^2 + {v_2}^2 + {w_2}^2 \right ),$$ где $u_i, \ v_i, \ w_i \ \left (i = \overline {1, 2} \right )$ — действительные числа. Полагая
$$u_1 = \frac{px}{\sqrt{qy+rz}}, \ v_1 = \frac{qy}{\sqrt{px+rz}}, \ w_1 = \frac{rz}{\sqrt{px+qy}},\\
u_2 = \sqrt{qy+rz}, \ v_2 = \sqrt{px+rz}, \ w_2 = \sqrt{px+qy},$$ будем иметь неравенство
$$
\begin{multline}\left (px + qy + rz \right )^2 \leqslant \left ( \frac{p^2x^2}{qy + rz} + \frac{q^2y^2}{px + rz} + \frac{r^2z^2}{pz + qy} \right ) \times \\ \times 2 \left (px + qy + rz \right ),\end{multline}$$ из которого следует, что
$$\frac{p^2x^2}{qy + rz} + \frac{q^2y^2}{px + rz} + \frac{r^2z^2}{pz + qy} \geqslant \frac{1}{2} \left (px + qy + rz \right ).$$ Так как $p + q + r = 1$, то для оценки суммы $px + qy + rz$ снизу можно применить неравенство леммы 3:
$$px + qy + rz \geqslant x^p y^q z^r = 1.$$ Неравенство задачи доказано.

Замечание 1. Полагая в неравенстве $\eqref{eq:m1710_third}$ $q_1 = \ldots = q_n=\frac{1}{n}$, получим
$$\sqrt[n]{a_1 a_2 \ldots a_n} \leqslant \frac{a_1 + a_2 + \ldots + a_n}{n}.$$ Из неравенства $\eqref{eq:m1710_third}$ нетрудно вывести также и некоторые другие классические утверждения. Например, легко получить так называемое неравенство Коши — Гёльдера:
$$\left \{ \sum\limits_{i=1}^n a_i b_i \right \} \leqslant \left \{ \sum\limits_{i=1}^n a_i ^k \right \} ^ \frac{1}{k} \cdot \left \{ \sum\limits_{i=1}^n b_i ^{{k}’} \right \} ^ \frac{1}{{k}’}$$ (где $a_i, \ b_i \gt 0, \ k, \ {k}’ \gt 1, \ \frac{1}{k} + \frac{1}{{k}’} = 1$), а также неравенство, носящее имя Минковского:
$$\left \{ \sum\limits_{i=1}^n \left ( a_i + b_i \right ) ^k \right \} ^ \frac{1}{k} \leqslant \left \{ \sum\limits_{i=1}^n a_i ^k \right \} ^ \frac{1}{k} + \left \{ \sum\limits_{i=1}^n b_i ^k \right \} ^ \frac{1}{k}$$ (где $a_i, \ b_i \gt 0, \ k \gt 1$).

Замечание 2. Положим в неравенстве задачи $p = q = r = \frac{1}{3}:$
$$\frac{x^2}{y + z} + \frac{y^2}{z + x} + \frac{z^2}{x + y} \geqslant \frac{3}{2}.$$ Теперь положим $a = \frac{1}{x}, \ b = \frac{1}{y}, \ c = \frac{1}{z}.$ Получим:
$$\frac{1}{a^3 \left (b + c \right )} + \frac{1}{b^3 \left (c + a \right )} + \frac{1}{c^3 \left (a + b \right )} \geqslant \frac{3}{2},$$ где $a \gt 0, \ b \gt 0, \ c \gt 0, \ abc = 1.$

Эта задача предлагалась в 1995 году на Международной математической олимпиаде (см. задачу М1526).

С.Калинин, В.Сендеров