Задание 20 ЕГЭ по математике №00045673

Чтобы доказать максимум, нужны и подходящая покупка, и запрет всех больших количеств. Упорядочим количества по убыванию: $m_1\ge m_2\ge m_3\ge m_4$. Самая дешёвая расстановка связывает наибольшее количество с наименьшей ценой: обмен двух неправильно расположенных количеств уменьшает стоимость на произведение разностей цены и количества.

Положим $m_4=t$, $d_1=m_1-m_2$, $d_2=m_2-m_3$, $d_3=m_3-m_4$. По условию $0\le d_i\le2$. Всего $N=4t+d_1+2d_2+3d_3$ маркеров.

Минимально возможная стоимость при этих количествах равна $S=233t+45d_1+97d_2+161d_3$, поскольку сумма цен $45+52+64+72=233$.

Выразив $t$ через $N$, получим $S=233N/4-(53d_1+78d_2+55d_3)/4$. Так как каждое $d_i\le2$, имеем $S\ge233N/4-93$. Эта оценка действует при любом распределении цветов.

В пункте а можно купить $7$ чёрных и по $6$ остальных: всего $25$, стоимость $7\cdot45+6\cdot52+6\cdot64+6\cdot72=1443$ рубля. Соседние разности $1,0,0$ допустимы.

Для $35$ маркеров нижняя оценка равна $233\cdot35/4-93=1945{,}75\gt1700$, поэтому такая покупка невозможна.

Уже для $31$ маркера стоимость не меньше $233\cdot31/4-93=1712{,}75\gt1700$. Для ещё большего числа эта оценка возрастает. Значит, купить можно не больше $30$.

Покажем достижимость: $9$ чёрных, $9$ синих, $7$ красных и $5$ зелёных. Их $30$, разности количеств $0,2,2$. Стоимость $405+468+448+360=1681\le1700$. Оба направления проверки выполнены.