|
|
 |
Условие
На столе лежат две кучки монет. Известно, что суммарный вес монет из первой кучки равен суммарному весу монет из второй кучки, а для каждого натурального числа k, не превосходящего числа монет как в первой, так и во второй кучке, суммарный вес k самых тяжелых монет из первой кучки не больше суммарного веса k самых тяжелых монет из второй кучки. Докажите, что если заменить каждую монету, вес которой не меньше x, на монету веса x (в обеих кучках), то первая кучка монет окажется не легче второй, каково бы ни было положительное число x.
Решение
Пусть в первой кучке n монет с весами x1 ≥ x2 ≥ ... ≥ xn, а во второй кучке m монет с весами y1 ≥ y2 ≥ ... ≥ ym, причём x1 ≥ ... ≥ xs ≥ x ≥ xs+1 ≥ ... ≥ xn и
y1 ≥ ... ≥ yt ≥ x ≥ yt+1 ≥ ... ≥ ym (если монет, вес которых не меньше x, вообще нет, то доказываемое утверждение очевидно). Тогда нужно доказать, что
xs + xs+1 + ... + xn ≥ xt + yt+1 + ... + ym. Так как x1 + ... + xn = y1 + ... + ym = A, то доказываемое неравенство преобразуется к виду
xs + (A – (x1 + ... + xs)) ≥ xt + (A – (y1 + ... + yt)), следовательно, оно равносильно такому:
x1 + ... + xs + x(t – s) ≤ y1 + ... + yt, которое мы и докажем.
Если t ≥ s, то x1 + ... + xs + x(t – s) ≤ (y1 + ... + ys) + (ys+1 + ... + yt), так как по условию x1 + ... + xs ≤ y1 + ... + ys, а ys+1 ≥ ... ≥ yt ≥ x.
Если t < s, то x1 + ... + xs ≤ y1 + ... + yt + x(t – s), так как x1 + ... + xs ≤ y1 + ... + ys = (y1 + ... + yt) + (yt+1 + ... + ys), а yt+1 ≤ ... ≤ ys ≤ x.
