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

Даны $n$ $(n \ge 2)$ гирь с массами $m_1,$ $m_2,$ $\ldots,$ $m_n,$ где $m_k$ — целое число такое, что $1 \le m_k\le k$ для всех $k=1,2,\ldots,n.$ Докажите, что если сумма $m_1+m_2+\ldots+m_n$ четна, то данные гири можно разбить на две группы с одинаковой суммарной массой.

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

Разобьём все гирьки на две части.И будем перемещять некоторые гирьки, по следующему правилу: если две части отличаются на массу $x$ по после переноса гирьки массой меньшой $x$, массы весов будут отличаться меньше чем на $x$. Это верно из того что, если массы были $m+x+k$ и $m$, то стали $m+k$ и $m+x$ и разница стала не более $|k-x|<x$. То есть за ход можно уменьшить разницу масс на весах. Причём в наших операциях мы использовали гирьку массой не больше чем разница масс на чашах.В итоге применяя эту операцию мы получим набор гинее на весах массы которых отличаются не более чем на $2$.Используя первую гирьку, чья масса $1$( это следует из того что масс этой гирьки натуральное число не большее $1$) перенося ее на другую чашу получаем равные по массе чаши(массы на чашах не могут отличаться ровно на $1$, так как масса всех гирек четное число)

Пусть даны чашечные весы с пустыми чашами.Расположим гири на чашах по шагам, следуя по "житейскому" алгоритму. Шаги алгоритма пронумерованы в обратном порядке: от $n$ до $1.$

Шаг n. Положим гирю с весом $m_{n}$ на любую чашу

Шаг k $(n>k\ge1).$ Если весы показывают неравенство, то положим гирю с весом $m_{k}$ на "легкую" чашу; если - равенство, то положим эту же гирю на любую чашу.

Легко видеть, что из-за ограничения $1\ge m_{k}\ge k$ следует, что после $k$-го шага разность суммарных весов на чашах не превосходит k (если строго, это тоже надо доказать по индукции: база индукции $k=n$ очевиден, а шаг индукции $k+1\rightarrow k$ следует из индуктивного предположения, если "легкая" чаша останется таковой после добавления гири с весом $m_{k}$, иначе - прямо из ограничения $1\ge m_{k}\ge k).$

После шага $2,$ разность весов будет не более $2,$ но условие четности суммарного веса влечет, что разность равна $1.$ Значит, после последнего шага с $m_{1}$ весы будут показывать равенство.

Итак, после завершения алгоритма получаем нужное разбиение гирь, соответствующее разбиению гирь по чашам.

Пусть нам даны эти $n$ $(n \ge 4)$ гирь с суммарной массой $2k$ (для $n=2, 3$, проверка осуществляется элементарно).

1-случай) Все гири различны по массе:

Здесь для $m_{1}$, $ 1 \le m_{1} \le 1 \Rightarrow m_{1} = 1$, для $m_{2}$, $m_{2} \ne m_{1}=1$, и $1 \le m_{2} \le 2 \Rightarrow m_{2}=2$, для $m_{i+1}$, при условий что, $\forall t\le i, m_{t}=t, i+1 \le n$, получаем, $1 \le m_{i+1} \le i+1, m_{i+1} \ne m_{1}, m_{2}, ..., m_{i} \Rightarrow m_{i+1} \in \{1, 2, ..., i+1 \} \backslash \{1, 2, ..., i \}=i+1 \Rightarrow m_{i+1}=i+1$.

Из чего следует, что $\forall i, m_{i}=i$, для данных $m_{k}$. Тогда, $2k=m_{1}+m_{2}+...+m_{n}=1+2+...+n=\dfrac{n(n+1)}{2} \Rightarrow n(n+1)=4k \Rightarrow 4 \mid n(n+1)$, а $n$, и $n+1$ имеют различную четность, поэтому либо $4 \mid n$, либо $4 \mid n+1$.

1.1-случай) $n=4a, a \in \mathbb{N}$:

Вместо доказательства существования разбиения гирь на две группы с одинаковой суммарной массой, покажем как можно набрать гири так, что их суммарная масса равна $k$, из чего последует что остальная куча гирь тоже будет суммарно весить $k$:

Возьмем гири $m_{1}, m_{2}, ..., m_{a}, m_{3a+1}, m_{3a+2}, ..., m_{4a}$, их суммарная масса равна, $1+2+...+a+(3a+1)+(3a+2)+...+4a=1+2+...+a+(4a-(a-1))+(4a-(a-2))+...+4a=(4a+1)+((4a-1)+(1+1))+((4a-2)+(1+2))+...+((4a-(a-1))+(1+(a-1)))=a(4a+1)=\dfrac{1}{2} \cdot \dfrac{4a(4a+1)}{2}=\dfrac{1}{2} (1+2+...+4a)=\dfrac{1}{2} 2k=k$

1.2-случай) $n=4a+3, a \in \mathbb{N}$:

Возьмем гири $m_{1}, m_{2}, ..., m_{a}, m_{3a+3}, m_{3a+4}, ..., m_{4a+2}, m_{4a+3}$, их суммарная масса равна, $1+2+...+a+(3a+3)+(3a+4)+...+(4a+2)+(4a+3)=1+2+...+a+((4a+2)-(a-1))+((4a+2)-(a-2))+...+((4a+3)-1)+(4a+3)=(4a+3)+(((4a+3)-1)+(1+1))+...+(((4a+3)-(a-1))+(1+(a-1)))=(a+1)(4a+3)=\dfrac{1}{2} \cdot \dfrac{(4a+4)(4a+3)}{2}=\dfrac{1}{2} 2k=k$

2-случай) Нашлась пара гирь с одинаковой массой:

Предположим существуют натуральные $n$ для которых не существует разбиения таких гирь на две группы с одинаковой массой. Возьмем за $n$ наименьшее такое число. Убедимся что, в таком случае $n \ge 4$:

При $n=2$, $m_{1}=1, m_{2}=1, 2$, а $m_{2}=2$ быть не может, поэтому $m_{2}=1$. В первую группу берем $m_{1}$, во вторую $m_{2}$, их суммарные массы равны по единице. При $n=3$, нетрудным перебором получаем что, $(m_{1}, m_{2}, m_{3})=(1, 1, 2), (1, 2, 1)$, разбиения соответственно,$(G_{1}, G_{2})=(\{m_{1}, m_{2} \}, \{m_{3} \}), (\{m_{1}, m_{3} \}, \{m_{2} \})$.

Тогда $n-2 \ge 2$, следовательно доказуемое утверждение определяется для $n-2$ (как кол-во данных гирь), и оно верно по тому, что $n$ - наименьшее натуральное, что доказуемое неверно. Но с другой стороны, можно доказать, что оно (случай с $n-2$ гирями) в то же время неверно:

Пусть $m_{a}, m_{b}$ - те самые гири с одинаковой массой, т.е. $m_{a}=m_{b}, a \ne b$, $M$ - суммарная масса всех $n$ гирь, $m$ - суммарная масса всех $n$ гирь без $m_{a}, m_{b}$, т.е. $M=m_{1}+m_{2}+...m_{n}, m=M-(m_{a}+m_{b})$. Тогда, $m=M-(m_{a}+m_{b})=2k-2m_{a}=2(k-m_{a})$, - четная сумма всех $n-2$ гирь, причем, если гири содержащаяся в сумме $m$ можно разбить на две группы с одинаковой массой, то прибавив к первой группе гирю $m_{a}$, второй $m_{b}$, получим разбиение $n$ гирь на две группы с одинаковыми массами, которого не должно существовать, следовательно, и эти $n-2$ гири нельзя разбить на две группы с одинаковой массой, из чего также следует что, все $n-2$ гири не могут быть различными, в ином случае, разбиение возможно (см. 1-случай). По итогу получаем $n-2$ гири, суммарная масса которых четна, среди них есть две гири с одинаковыми массами (что соответствует всем условиям рассматриваемым во 2 случае), и эти гири никак не делятся на две группы с одинаковой массой - противоречие.

Решение: По индукции по $k$ докажем, что числа от $1$ до $m_1 + \ldots + m_k$ можно представить как сумма масс гирек. База для $k=1$ очевидна.

Переход: Пусть для $k$ утверждение верно, далее докажем для масс $m_1\ldots,m_k,m_{k+1}.$

Из предположения индукции следует, что числа от $1$ до $m_1 + \ldots + m_k$ можно представить первыми $k$ гирьками. Прибавив к каждому числу гирьку $m_{k+1}$ получим, что числа от $m_{k+1}$ до $m_1+\ldots +m_k+m_{k+1}$ можно представить суммой масс гирек. Если $m_{k+1}\le m_1+\ldots m_k,$ то все искомые числа можно представить. Если $k+1\ge m_{k+1}>m_1+\ldots m_k\ge k,$ то $m_{k+1}=k+1$ и $m_1=\ldots=m_k=1$ для которых очевидно верно предположение.$\quad\square$

Ясно. что среди чисел от $1$ до $2N-$суммы масс всех гирек, есть число $N,$ откуда все гирьки можно разделить на две группы с равной массой, что требовалось доказать.