2019-01-21
На столе лежат две кучки монет. Известно, что суммарный вес монет из первой кучки равен суммарному весу монет из второй кучки, а для каждого натурального числа $k$, не превосходящего числа монет как в первой, так и во второй кучке, суммарный вес $k$ самых тяжелых монет из первой кучки не больше суммарного веса $k$ самых тяжелых монет из второй кучки. Докажите, что если заменить каждую монету, вес которой не меньше $x$, на монету веса $x$ (в обеих кучках), то первая кучка монет окажется не легче второй, каково бы ни было положительное число $x$.
Решение:
Пусть в первой кучке $n$ монет с весами $x_1 \geq x_2 \geq \cdots \geq x_n$, а во второй кучке $m$ монет с весами $y_1 \geq у_2 \geq \cdots \geq y_m,$ причем $x_1 \geq \cdots \geq x_s \geq x \geq x_{s+1} \geq \cdots \geq x_n$ и $у_1 \geq \cdots \geq y_t \geq x \geq y_{t+1} \geq \cdots \geq y_m$ (если монет, вес которых не меньше $x$, вообще нет, то доказываемое утверждение очевидно). Тогда нужно доказать, что $x_s + x_{s+1} + \cdots + x_n \geq xt + y_{t+1} + \cdots + y_m$. Так как $x_1 +\cdots + x_n = y_1 + \cdots + y_m = A$, то доказываемое неравенство преобразуется к виду
$xs + (A - (x_1 + \cdots + x_s)) \geq xt +(A - (y_1 + \cdots + y_t))$,
следовательно, оно равносильно такому:
$x_1 + \cdots + x_s + x(t - s) \leq y_1 + \cdots + y_t$,
которое мы и докажем. Если $t \geq s,$ то
$x_1 + \cdots + x_s + x(t - s) = (x_1 + \cdots + x_s) + \underset{t-s}{ \underbrace{(x + \cdots + x)}} \leq (y_1 + \cdots + y_s) + (y_{s + 1} + \cdots + y_t)$,
так как $x_1 + \cdots + x_s \leq y_1 + \cdots + y_s$ (что немедленно вытекает из условия), а $y_{s+1} \geq x, \cdots , y_t \geq x$.
Если $t < s,$ то $x_1 + \cdots + x_s + x(t - s) \leq y_1 + \cdots + y_t$ равносильно
$x_1 + \cdots + x_s \leq y_1 + \cdots + y_t + \underset{t-s}{\underbrace{(x + \cdots + x)}}$.
Последнее неравенство следует из того, что
$x_1 + \cdots + x_s \leq y_1 + \cdots + y_s = (y_1 + \cdots + y_t) + (y_{t+1} + \cdots + y_s)$, а $y_{t+1} \leq x, \cdots ,y_s \leq x$.