Олимпиадная задача о гирях для Пети и Васи: равные группы, теория чисел

  Пример. Пусть набор состоит из 20 гирь массой 50 г и 30 гирь массой 40 г. В этом случае Петя может разделить все гири на десять групп, в каждой из которых две гири массой 50 г и три гири массой 40 г; а Вася может разделить все гири на пять групп, в каждой из которых четыре гири массой

50 г, и шесть групп, в каждой из которых пять гирь 40 г. Таким образом, значение  N = 50  возможно.

  Оценка. Предположим, что  N < 50,  и Пете с Васей удалось разложить гири на группы нужным образом. Тогда в одной из петиных групп не более четырёх гирь, и в одной из васиных групп также не более четырёх гирь.   Лемма. Пусть имеются две группы гирь равной суммарной массы, состоящие из k и l гирь, где  k < l.  Тогда  k ≥ 4,  причём в случае  k = 4  имеем

l = 5,  и в каждой из групп массы гирь равны.

  Доказательство. Пусть m – масса самой легкой гири в группе из l гирь, тогда масса второй группы не меньше  lm ≥ (k + 1)m,  а масса первой группы не больше 1,25km, откуда  k + 1 ≤ 1,25k  и  k ≥ 4.  Если  k = 4,  то в указанных выше оценках неравенства обращаются в равенства, поэтому

l = k + 1 = 5,  в группе из пяти гирь все гири одинаковой массы  m = 4x,  а в группе из четырёх гирь все гири массой 5x.   Рассмотрим два случая.

  1) Среди петиных групп есть две группы с разным количеством гирь. Тогда из леммы следует, что в нескольких петиных группах по четыре гири массы 5x, а в остальных петиных группах по пять гирь массы 4x. Общий вес всех гирь тогда равен 200x, что невозможно, так как 200 не делится на 11, а суммарная масса в каждой васиной группе должна быть целым кратным x.

  2) В десяти петиных группах равное число гирь. Тогда N кратно 10. Если среди васиных групп найдутся две группы с разным количеством гирь, то из леммы следует, что в каждой из васиных групп не менее четырёх гирь, откуда  N ≤ 44  ⇒  N ≥ 50  (так как N кратно 10). Противоречие.

  Если же в 11 васиных группах равное число гирь, то N кратно 11   ⇒  N кратно 110  ⇒  N ≥ 110.  Противоречие.