Осторожный Кузьма – 2
Кузьма, знакомый вам по задаче регионального этапа, влюбился и решил подарить девушке красивый букет. В магазине продаются три вида цветов – $A$, $B$ и $C$. Кузьма знает, что девушка ценит эти цветы по-разному: каждый цветок наиболее предпочтительного с ее точки зрения вида принесет ей 3 единицы радости, каждый цветок наименее предпочтительного вида принесет 1 единицу, а каждый цветок среднего по предпочтительности вида принесет 2 единицы. Проблема в том, что Кузьма забыл, какой именно вид цветов является самым предпочтительным, какой – средним, а какой – наименее предпочтительным, и спрашивать ее об этом ему неловко. Радость девушки от букета равна сумме ее радости от каждого из цветков в букетик (даже если в букете есть цветы разных видов). Девушка поцелует Кузьму, если ее радость от букета будет не меньше 30 единиц. Для простоты считайте, что количество цветов не обязательно нечетное и даже не обязательно целое (но обязательно неотрицательное). Допустим, цветок каждого из трех видов стоит 1 ден. ед. Какую минимальную сумму Кузьма должен потратить на цветы, чтобы девушка гарантированно его поцеловала? Как изменится ваш ответ на пункт 1, если цветок вида $A$ стоит 1 ден. ед., цветок вида $B$ – 2 ден. ед., цветок вида $C$ – 3 ден. ед.? Допустим, радость девушки зависит не только от количества цветов разных видов, но и от их сочетания. А именно, если в букете есть цветы больше чем одного вида, их сочетание может не понравиться девушке: если сочетание цветов неудачное, радость девушки равна сумме её радости от каждого цветка, как выше, минус $Z$ единиц. Параметр $Z$ известен Кузьме. Ответьте на вопрос пункта 1 (при ценах цветов, данных в пункте 1) для $Z=24$; $Z=36$.
Решение
Обозначим количества цветов трех видов в букете за $a$, $b$ и $c$. Девушка гарантированно поцелует Кузьму, если будут выполнены 6 неравенств: $$\begin{equation*} \begin{cases} a + 2b + 3c\ge30 \\ a + 3b + 2c\ge30 \\ 2a + b + 3c\ge30 \\ 2a + 3b + c\ge30 \\ 3a + b + 2c\ge30 \\ 3a + 2b + c\ge30 \end{cases} \end{equation*}$$ Нам нужно найти минимальное значение выражения $a + b + c$, при условии, что $a$, $b$ и $c$ удовлетворяют неравенствам выше. Сложив данные 6 неравенств, получаем, что $12(a+b+c)\ge6⋅30$, откуда $a+b+c\ge15$. При этом нижняя граница в последнем неравенстве достигается: если $a = b = c = 5$, то все 6 неравенств выполнены, и при этом $a + b + c = 15$. Значит, минимальная сумма равна 15 (и для ее достижения Кузьме следует купить букет, состоящий из 5 цветков каждого вида.) Примечание: как видим, покупка «cбалансированного» букета позволяет в данном случае добиться существенной экономии по сравнению с «наивной» стратегией покупки 30 цветков какого-либо одного вида. Как и в задаче регионального этапа, в условиях неопределенности Кузьме выгодно осуществлять диверсификацию «портфеля». В данном случае нам надо минимизировать значение выражения $a+2b+3c$, при условии, что $a$, $b$ и $c$ удовлетворяют неравенствам выше. Из первого неравенства мы знаем, что $a + 2b + 3c\ge 30$. Нижняя граница в этом неравенстве достигается, если взять, например, $a = 30$, $b = c = 0$. (в этом случае все 6 неравенств выполнены, и $a + 2b + 3c = 30$). Таким образом, минимальная сумма в этом случае равна 30 ден. ед. (Для её достижения Кузьма может, например, купить букет, состоящий только из 30 цветов типа A, однако подойдет не только он , а любой букет, в котором $a\ge b\ge c$ и $a + 2b + 3c = 30$.) Примечание: как видим, при новых ценах цветов диверсификация перестает быть выгодной, так как она начинает требовать покупки дорогих цветов, что влечет за собой рост расходов. Ясно, что в этом случае Кузьме нужно отдельно рассмотреть две стратегии: покупка букета, состоящего из только одного вида цветов (в этом случае ситуация неудачного сочетания цветов исключена) и покупка букета, состоящего из более чем одного вида цветов. Если Кузьма покупает однородный букет, ему нужно купить минимум 30 цветков, и минимальные расходы равны 30; неоднородный же букет гарантирует поцелуй, если выполнены новые 6 неравенств: $$\begin{equation*} \begin{cases} a + 2b + 3c −Z\ge30 \\ a + 3b + 2c −Z\ge30 \\ 2a + b + 3c −Z\ge30 \\ 2a + 3b + c −Z\ge30 \\ 3a + b + 2c −Z\ge30 \\ 3a + 2b + c −Z\ge30 \end{cases} \end{equation*}$$ Кузьме нужно вновь минизировать значение $a + b + c$ при этих условиях. Действуя аналогично пункту 1, получаем, что $a + b + c\ge(30 + Z)/2$. При этом нижняя граница достигается (можно взять $a = b = c = (30 + Z)/6$). Поэтому минимальные расходы равны $(30 + Z)/2$. Если $Z = 24$, эти расходы равны $(30 + 24)/2 = 27 < 30$, и значит Кузьме нужно покупать неоднородный букет, состоящий из 9 цветков каждого вида. Если $Z = 36$, расходы равны $(30 + 36)/2 = 33 > 30$, и значит, лучше не рисковать, а купить однородный букет (из 30 цветков какого-либо вида. Примечание: в данном пункте диверсификация по условию сопряжена с определенными издержками сама по себе. Если эти издержки относительно небольшие $(Z = 27)$, то диверсификацию выгодно осуществлять, несмотря на них; если же они достаточно большие $(Z = 36)$, то диверсификация становится невыгодной. Ответ: При $Z = 24$ минимальные расходы равны 27; при $Z = 36$ минимальные расходы равны 30.