2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Сумма 35 чисел равно 100
Сообщение08.08.2017, 04:43 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Сумма 35 чисел равно 100
Сообщение04.09.2017, 14:58 
Аватара пользователя


07/01/16
1426
Аязьма
Пусть $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$ всегда можно сложить из двоек и троек.

 Профиль  
                  
 
 Re: Сумма 35 чисел равно 100
Сообщение04.09.2017, 16:18 
Аватара пользователя


07/01/16
1426
Аязьма
Упс, в первом случае грубая ошибка, $40+3n_1<m$ ниоткуда не следует. Решения нет

 Профиль  
                  
 
 Re: Сумма 35 чисел равно 100
Сообщение06.09.2017, 03:48 
Аватара пользователя


07/01/16
1426
Аязьма
Вторая попытка, навороченная, но, кажется, рабочая.
Пусть по-прежнему $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$, если понадобится!

 Профиль  
                  
 
 Re: Сумма 35 чисел равно 100
Сообщение06.09.2017, 10:49 
Аватара пользователя


26/02/14
497
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$

(Оффтоп)

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

 Профиль  
                  
 
 Re: Сумма 35 чисел равно 100
Сообщение06.09.2017, 11:32 
Аватара пользователя


07/01/16
1426
Аязьма
Rak so dna в сообщении #1245531 писал(а):
Возможно я что-то ни так понял.
Эх, снова ерунда! Во втором неравенстве п.3в нельзя оставлять только $n_1$, это делает неравенство более сильным, а не наоборот. Спасибо! Снова нет решения + пора в третий класс переучиваться :facepalm:

 Профиль  
                  
 
 Re: Сумма 35 чисел равно 100
Сообщение06.09.2017, 23:20 
Аватара пользователя


07/01/16
1426
Аязьма
Третья попытка должна быть без осечки :idea:
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$ - так не бывает; аналогично для более чем трех чисел).

 Профиль  
                  
 
 Re: Сумма 35 чисел равно 100
Сообщение07.09.2017, 09:18 
Аватара пользователя


07/01/16
1426
Аязьма
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$.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 8 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group