Loading [MathJax]/jax/output/SVG/jax.js

Математикадан облыстық олимпиада, 2020 жыл, 9 сынып


Салмақтары m1, m2, , mn, болатын n (n2) гір тастары берілген, мұндағы әрбір k=1,2,,n үшін mk — бүтін сан және 1mkk. Егер m1+m2++mn салмақтардың қосындысы жұп сан болса, осы гір тастарын салмақтарының қосындысы тең болатындай екі топқа бөлуге болатынын дәлелдеңіз.
посмотреть в олимпиаде

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

пред. Правка 2   0
5 года 1 месяца назад #

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

  -2
5 года 1 месяца назад #

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

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

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

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

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

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

  0
4 года 2 месяца назад #

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

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

Здесь для m1, 1m11m1=1, для m2, m2m1=1, и 1m22m2=2, для mi+1, при условий что, ti,mt=t,i+1n, получаем, 1mi+1i+1,mi+1m1,m2,...,mimi+1{1,2,...,i+1}{1,2,...,i}=i+1mi+1=i+1.

Из чего следует, что i,mi=i, для данных mk. Тогда, 2k=m1+m2+...+mn=1+2+...+n=n(n+1)2n(n+1)=4k4n(n+1), а n, и n+1 имеют различную четность, поэтому либо 4n, либо 4n+1.

1.1-случай) n=4a,aN:

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

Возьмем гири m1,m2,...,ma,m3a+1,m3a+2,...,m4a, их суммарная масса равна, 1+2+...+a+(3a+1)+(3a+2)+...+4a=1+2+...+a+(4a(a1))+(4a(a2))+...+4a=(4a+1)+((4a1)+(1+1))+((4a2)+(1+2))+...+((4a(a1))+(1+(a1)))=a(4a+1)=124a(4a+1)2=12(1+2+...+4a)=122k=k

1.2-случай) n=4a+3,aN:

Возьмем гири m1,m2,...,ma,m3a+3,m3a+4,...,m4a+2,m4a+3, их суммарная масса равна, 1+2+...+a+(3a+3)+(3a+4)+...+(4a+2)+(4a+3)=1+2+...+a+((4a+2)(a1))+((4a+2)(a2))+...+((4a+3)1)+(4a+3)=(4a+3)+(((4a+3)1)+(1+1))+...+(((4a+3)(a1))+(1+(a1)))=(a+1)(4a+3)=12(4a+4)(4a+3)2=122k=k

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

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

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

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

Пусть ma,mb - те самые гири с одинаковой массой, т.е. ma=mb,ab, M - суммарная масса всех n гирь, m - суммарная масса всех n гирь без ma,mb, т.е. M=m1+m2+...mn,m=M(ma+mb). Тогда, m=M(ma+mb)=2k2ma=2(kma), - четная сумма всех n2 гирь, причем, если гири содержащаяся в сумме m можно разбить на две группы с одинаковой массой, то прибавив к первой группе гирю ma, второй mb, получим разбиение n гирь на две группы с одинаковыми массами, которого не должно существовать, следовательно, и эти n2 гири нельзя разбить на две группы с одинаковой массой, из чего также следует что, все n2 гири не могут быть различными, в ином случае, разбиение возможно (см. 1-случай). По итогу получаем n2 гири, суммарная масса которых четна, среди них есть две гири с одинаковыми массами (что соответствует всем условиям рассматриваемым во 2 случае), и эти гири никак не делятся на две группы с одинаковой массой - противоречие.

пред. Правка 2   2
4 года 2 месяца назад #

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

Переход: Пусть для k утверждение верно, далее докажем для масс m1,mk,mk+1.

Из предположения индукции следует, что числа от 1 до m1++mk можно представить первыми k гирьками. Прибавив к каждому числу гирьку mk+1 получим, что числа от mk+1 до m1++mk+mk+1 можно представить суммой масс гирек. Если mk+1m1+mk, то все искомые числа можно представить. Если k+1mk+1>m1+mkk, то mk+1=k+1 и m1==mk=1 для которых очевидно верно предположение.

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