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

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

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

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

Для начала, изучим возможность использования 151 карточки с числом "5". Понятно, что в одной группе не может быть больше одной карточки с числом "5", иначе сумма превысила бы 9. Тогда все 151 карточек должны быть в разных 151 группах. Для того чтобы все 151 группы соответствовали условию, сумма в группах должна равняться 9, то есть каждой группе не хватает карточек с суммой 4. Получается, всем 151 группам нужна сумма карточек, которая как минимум равна 151*4=604. Как отмечалось ранее, группы не могут использовать больше 1 карточки с "5", а сумма всех 200 карточек с числом "1" и с числом "2" равняется 200(1+2)=600 что меньше чем 604. Получается больше чем 150 карточек с числом "5" использоваться не может. Но тогда сумма всех возможно используемых карточек равна: 5*150+2*200+1*200=1350. А 1350:9=150, что значит что наибольшее количество групп карточек-150.

Пример: 100 групп с (5;2;1;1) и 50 групп с (5;2;2).

Ответ 150

Покажу сначала пример (5,2,2) таких 100 (5,1,1,1,1) таких 50, тогда остаётся 50 карточек которые мы не использовали с знаком 5.

Докажем что больше нельзя, сумма карточек без пятерки с суммой 4

200*2+200*1 =600=4*150 ,то есть сумма чисел неиспользованных карточек не меньше 250 отсюда ,тогда количество групп не более (200*1+200*2+150*5):9=150 что и требовалась доказать отсюда ответ 150