Областная олимпиада по математике, 2014 год, 11 класс

У школьника имеется 600 карточек с записанными на них числами. На 200 карточках записано число 1, на других 200 карточках записано число 2 и, наконец, на оставшихся 200 карточках записано число 5. Школьнику нужно разложить карточки на несколько групп так, чтобы в каждой группе сумма чисел на карточках была равна 9. При этом некоторые карточки, возможно, не будут использованы. Какое наибольшее количество групп карточек может получиться у школьника?

Комментарий/решение

Всего карточек, на которых написано число 5, 200 штук. Понятно, что в одной группе не может быть более одной такой карточки. Чем меньше в группе карточек, тем больше групп. $9=5+2+2$- 100 групп; $9=5+1+1+1+1$-50 групп. Итого 150 групп

Ответ: $150.$

Все группы сумма элементов которых $9$ это:

$$(5,2,2),(5,2,1,1),(5,1,1,1,1),(2,2,2,2,1),(2,2,2,1,1,1),(2,2,1,1,1,1,1),(2,1,1,1,1,1,1,1),(1,1,1,1,1,1,1,1,1)\quad (i)$$

Сперва приведем пример для $150$ и относительно примера построим оценку.

Пример: Рассмотрим 100 групп вида $(5,2,2)$ и 50 групп $(5,1,1,1,1).$

Оценка: Через $a,b,c,d,e,f,g,h\ge 0$ обозначим количество групп каждого вида соответственно порядку в $(i).$ Тогда количество $2$ (двоек) суммарно равно

$$(1)\quad 2a+b+4d+3e+2f+g\le 200,$$

а количество $1$ (единиц) равно

$$(2)\quad 2b+4c+d+3e+5f+7g+9h\le 200.$$

Так как в примере $a=100,b=0,c=50,$ то $a+b+c=150$, а сумма всех остальных равна $0.$ (это равенство не обязательно верное, это просто ориентир благодаря которому мы строим оценку)

Поэтому просуммируем неравенство $(1)$ два раза и $(2)$ один раз:

$$4(a+b+c+d+e+f+g+h)\le 4(a+b+c)+9(d+e+f+g+h)\le 600$$

$$\implies a+b+c+d+e+f+g+h\le 150.\quad \square$$