|
|
 |
Условие
Все имеющиеся на складе конфеты разных сортов разложены по n коробкам, на которые установлены цены в 1, 2, ..., n у. е. соответственно. Требуется купить такие k из этих коробок наименьшей суммарной стоимости, которые содержат заведомо не менее k/n массы всех конфет. Известно, что масса конфет в каждой коробке не превосходит массы конфет в любой более дорогой коробке.
а) Какие коробки следует купить при n = 10 и k = 3 ?
б) Тот же вопрос для произвольных натуральных n ≥ k.
Решение
Пусть a1 ≤ a2 ≤ ... ≤ an – массы конфет в коробках стоимостью в 1, 2, ..., n у. е. соответственно, а n1 < n2 < ... < nk – номера тех коробок, которые нужно купить.
1. Обозначим mj = jn/k (j = 1, ..., k) и докажем, что для искомого набора номеров должны быть выполнены неравенства nj ≥ mj. (*)
Действительно, предположим, что nj < mj для некоторого j.
Тогда, например, в случае
a1 = ... = anj = nj < anj + 1 = ... = an = n + nj
получаем
a1 + ... + an = nj2 + (n – nj)(n + nj) = n2,
an1 + ... + ank = (k – j)(n + nj) + jnj < (k – j)n + nj = kn,
то есть нарушено требование задачи.
2. Пусть теперь все неравенства (*) верны. Докажем, что тогда требование задачи выполнено.
а) При n = 10, k = 3 имеем n1 ≥ 10/3, n2 ≥ 20/3, n1 ≥ 10, т.е. достаточно взять 4-ю, 7-ю и 10-ю коробки. И действительно:
(добавив к группе чисел число, меньшее их всех, мы уменьшим среднее арифметическое).
б) Положим n0 = m0 = a0 = 0 и возьмём целые числа nj = mj + εj, где 0 ≤ ε < 1. Рассмотрим ступенчатую функцию, задаваемую равенствами f(x) = aj при j – 1 < x ≤ j. Поскольку функция не убывает, её среднее значение на промежутке уменьшается, когда оба конца промежутка сдвигают влево (даже с изменением длины промежутка). (Среднее значение – это площадь под графиком функции на заданном промежутке, деленная на длину этого промежутка.) В частности,
Поэтому
так как все знаменатели равны n/k, nk = mk = n, εk = 0.
Итак, стоимость набора из k коробок, удовлетворяющего требованию задачи, будет наименьшей для наименьших целых чисел nj, удовлетворяющих неравенствам (*).
Ответ
Коробки стоимостью а) 4, 7 и 10 у. е.; б) у. е.
Замечания
Задача восходит к телевизионной игре "Сто к одному", где на
заключительном этапе двум игрокам задают по пять вопросов. На каждый из них заготовлено по пять наиболее популярных (по результатам опроса) ответов, суммарная стоимость которых составляет 100 очков. Ни сами эти ответы,
ни тем более их стоимости, соответствующие их популярности, игрокам не известны.
Если игроки на все вопросы дадут по паре самых популярных из пяти ответов, то заработают за каждый вопрос не менее 100·⅖ = 40 очков, а за все пять вопросов – не менее 200 очков, которые как раз и требуется набрать для выигрыша, то есть игра, в общем-то, честная.
Исходя из решения задачи, можно утверждать, что при любом распределении очков по ответам игрокам позволено немного ошибаться: они заведомо не проиграют, если на каждый вопрос в паре с самым популярным ответом угадают не следующий, а лишь средний по популярности ответ.
