Сумма 35 чисел равно 100

[daogiauvang]

Дано 35 положительных целых чисел, которые не более 50 и сумма этих чисел равна 100. Доказать, что можно расделить эти числа на две группы, сумма каждой группы равна 50.

[waxtep]

Пусть $m$ - наибольшее из этих чисел (очевидно, $m>2$), $n_i$ - количество чисел $i$.

Случай №1: $m$ - четное или ($m$ - нечетное и $n_1>0$) - в этом случае нельзя позволить набрать из единичек и двоек $50-m$, т.е. должно быть $n_1+2n_2<50-m$; с другой стороны, $\frac{100-n_1-2n_2}{35-n_1-n_2}\ge3$ (оставшиеся числа не меньше трех), т.е. $2n_1+n_2\ge5$. Это дает $n_2<45-m+n_1$ и $40+3n_1<m$, т.е. $m\ge41$ и $n_1\le8$. Что невозможно, т.к. в самом благоприятном случае $8\cdot1+26\cdot2+1\cdot41=101>100$.
Случай №2: $m$ - нечетное и $n_1=0$. Здесь, $\frac{100-2n_2-3n_3}{35-n_2-n_3}\ge4$, т.е. $2n_2+n_3\ge40$. Рассмотрим различные возможные значения $n_3$:
если $n_3=0$, $n_2\ge20$ и $m<5$ (иначе можно сложить $50$ из двух нечетных чисел и имеющихся двоек) - что невозможно;
если $n_3=1$, единственный вариант: $20$ двоек, тройка, пятерка и $13$ четверок - его можно разбить на две половинки;
если $n_3=2$ - так же один вариант из $19$ двоек и $14$ четверок, бьется пополам;
для $n_3=3,4,5$ - то же самое;
для $n_3\ge6$ - $50$ всегда можно сложить из двоек и троек.

[waxtep]

Упс, в первом случае грубая ошибка, $40+3n_1<m$ ниоткуда не следует. Решения нет

[waxtep]

Вторая попытка, навороченная, но, кажется, рабочая.
Пусть по-прежнему $n_i$ - количество чисел $i$ в наборе.
1. Легко показать, рассматривая количество чисел $>2$, что $2n_1+n_2\ge5$
2. Случай $n_1=0$ будем считать (коряво) разобранным в предыдущей попытке, в нем $2n_2+n_3\ge40$, и, либо, большое количество двоек не позволяет иметь слишком большое максимальное число в наборе, либо троек становится так много, что $50$ можно сложить из одних двоек и троек.
3. Далее считаем $n_1>0$, и, следовательно (см. п.1), в наборе есть хотя бы одна единица и одна двойка, либо хотя бы три единицы. Значит, сложив из других чисел $47$, $48$ или $49$, мы сможем добраться и до $50$.
4. Основная часть. Рассмотрим $L_m$ - сумму всех чисел $\le m$, и $H_m(x)$ - сумму любых чисел $>m$, взятых в количестве $x$ штук. Для каких-то значений $m, x$ возможны следующие варианты:
а. $H_m(x)=0$ - в наборе нет $x$ чисел $>m$
б. $H_m(x)\ge51$ - сумма больших чисел чересчур велика, добавление к ней чисел маленьких не поможет сложить $50$.
в. $H_m(x)+L_m\le49$ - сложение $x$ больших и всех маленьких чисел не дотягивает до $50$; в частности, это означает, что $n_1\le49-H_m(x)$. С другой стороны, величина всех прочих чисел не меньше $m+1$, т.е. $100-L_m-H_m(x)\ge (m+1)(35-x-\sum_{i=1}^{m}{n_i})$. Оставляя в этом неравенстве от $L_m$ только $n_1$ и комбинируя с предыдущим, получим ограничение сверху на сумму $x$ больших чисел:

$$H_m(x)\le14+x+\frac{51}{m+1}$$

Возьмем $m=4$, $H_4(x)\le x+24$, т.е.:
$H_4(1)\le25$
$H_4(2)\le26\Rightarrow H_4(1)\le21$ (случай $H_4(2)\ge51$ невозможен)
$H_4(3)\le27\Rightarrow H_4(1)\le17$ (случай $H_4(3)\ge51$ так же невозможен)
и так мы добираемся до $H_4(6)\le30$ (шесть пятерок; более шести чисел $>4$ быть не может, т.к. $H_4(7)\le31$ невозможно).
Таким образом, $H_4(x)$ "отвечает" не более чем за $30$ из $100$; как минимум $70$ сложено из чисел $1,2,3,4$. А тогда отложим в сторону единицы и двойки из п.3 выше, сложим из оставшихся $1,2,3,4$ число в диапазоне $47-50$ и добьем ими до $50$, если понадобится!

[Rak so dna]

waxtep в сообщении #1245502 писал(а):

$H_m(x)$ - сумму любых чисел $>m$, взятых в количестве $x$ штук.

waxtep в сообщении #1245502 писал(а):

Таким образом, $H_4(x)$ "отвечает" не более чем за $30$ из $100$; как минимум $70$ сложено из чисел $1,2,3,4$. А тогда отложим в сторону единицы и двойки из п.3 выше, сложим из оставшихся $1,2,3,4$ число в диапазоне $47-50$ и добьем ими до $50$, если понадобится!

Возьмем набор:
$1\cdot9+2\cdot1+3\cdot18+5\cdot7=100$ тогда, в ваших обозначениях, $H_4(7)=35$

(Оффтоп)

Возможно я что-то ни так понял.

[waxtep]

Rak so dna в сообщении #1245531 писал(а):

Возможно я что-то ни так понял.

Эх, снова ерунда! Во втором неравенстве п.3в нельзя оставлять только $n_1$, это делает неравенство более сильным, а не наоборот. Спасибо! Снова нет решения + пора в третий класс переучиваться

[waxtep]

Третья попытка должна быть без осечки
1. Снова $n_i$ - количество чисел $i$ в наборе; начнем с верного для любого $1\le m \le35$ неравенства $100-\sum_{i=1}^{m}{in_i}\ge (m+1)(35-\sum_{i=1}^{m}{n_i})$, которое дает

$$\sum_{i=1}^{m}{(m+1-i)n_i}\ge35m-65$$

и, поскольку $(1-i)\le0$, тем более верно

$$\sum_{i=1}^{m}{in_i}\ge\sum_{i=1}^{m}{n_i}\ge35-\frac{65}m$$

Нам понадобятся следующие частные случаи этих формул:

$$2n_1+n_2\ge5\eqno(a)$$

$$3n_1+2n_2+n_3\ge40\eqno(b)$$

$$\sum_{i=1}^{6}{in_i}\ge\sum_{i=1}^{6}{n_i}\ge24\eqno(c)$$

2. В случае $n_1=0$, из $(a,b)$ следует $n_2\ge5, 2n_2+n_3\ge40$. Если $n_3\ge5$, $50$ всегда можно сложить из двоек и троек. Предположение о невозможности разбиения на две группы по $50$ для $0\le n_3\le4$ легко приводится к противоречию (не может быть $n_2\ge25$, но и чисел $\ge4$ не может быть слишком много).

3. Далее $n_1>0$. Из $(a,b)$ следует, что набор содержит хотя бы одну из групп $(1,1,1,3)$ или $(1,1,2,3)$ или $(1,2,2,2)$. Это означает, что сложив из других чисел некую сумму $S$, сможем сложить и любую из $S+1, S+2,...S+6$ (любое значение остатка по модулю $6$ нам доступно).

4. В частности, если в наборе все числа $\le6$, $50$ всегда можно будет сложить.
Более того, если $\sum_{i=1}^{6}{in_i}\ge50$, всегда можно сложить $50$ из чисел $\le6$.

5. В завершение, докажем, что в наборе, который невозможно разбить на две группы по $50$, не может быть чисел $>6$, дающих в сумме $\ge51$. Предположим обратное.
Из формулы $(c)$ и п.3 выше следует, что из чисел $\le6$ можно сложить любое число от $1$ до $24$. Значит, каждое из чисел $>6$ должно быть $\le25$, любая их частичная сумма $\le25$ или $\ge51$, а сумма их всех $\ge51$. Что невозможно ни при каком их количестве (очевидно, их не может быть одно или два, а для трех: сумма любых двух $\le25$, третье так же $\le25$, а сумма всех трех $\ge51$ - так не бывает; аналогично для более чем трех чисел).

[waxtep]

waxtep в сообщении #1245684 писал(а):

3. Далее $n_1>0$. Из $(a,b)$ следует, что набор содержит хотя бы одну из групп $(1,1,1,3)$ или $(1,1,2,3)$ или $(1,2,2,2)$. Это означает, что сложив из других чисел некую сумму $S$, сможем сложить и любую из $S+1, S+2,...S+6$ (любое значение остатка по модулю $6$ нам доступно).

небольшое уточнение: или $(1,1,1,1,1,1)$

В формуле $(c)$ можно смело добавить единичку, т.е. $\ge25$

И п.2 можно сформулировать аккуратнее, для $n_3=5$ понадобится еще одно из нечетных чисел, неравных $3$, для сложения $50$.