Задача 79288

Темы:    [ Взвешивания ] [ Делимость чисел. Общие свойства ] [ Разбиения на пары и группы; биекции ] [ Процессы и операции ]

Сложность: 4+ Классы: 8,9,10

Условие

Автор: Конягин С.В.

Имеется несколько гирь, масса каждой из которых равна целому числу. Известно, что их можно разбить на k равных по массе групп.
Доказать, что не менее чем k способами можно убрать одну гирю так, чтобы оставшиеся гири нельзя было разбить на k равных по массе групп.

Решение

  Возьмём две коробки и разложим в них наши гири так, чтобы в первой коробке оказалось менее k гирь. Раскладывать же гири будем следующим образом. Сначала возьмём гири, веса которых не делятся на k. Если таких гирь меньше k, то положим их в первую коробку и перейдём к следующему шагу. Если же таких гирь окажется больше k, то положим все гири во вторую коробку. В первом случае возьмём те гири, веса которых делятся на k, но не делятся на k². Если они уместятся в первой коробке, то положим их туда; если же нет, то положим все гири, не лежащие в первой коробке, во вторую. Если опять будет иметь место первый случай, возьмём затем те гири, веса которых делятся на k², но не делятся на k³ и так далее, Так как всего гирь не меньше k штук, то часть гирь обязательно попадёт во вторую коробку.
  Пусть первой группой гирь, не поместившихся в первой коробке, будут гири, веса которых делятся на k^r, но не делятся на k^r+1. Во второй коробке окажутся те гири, веса которых делятся на k^r, а в первой  – те, веса которых не делятся на k^r (r может оказаться равным нулю; это соответствует тому, что все гири попадают во вторую коробку, а первая остаётся пустой). По условию гири можно разложить на k равных по весу групп. Поскольку в первой коробке меньше k гирь, в ней никак не могут быть представлены все k групп, и значит, существует группа, все гири из которой оказались во второй коробке. Следовательно, суммарный вес этой (а значит, и каждой) группы делится на k^r. Так как всего у нас k равных по весу групп, то суммарный вес гирь делится на k^r+1. Предположим теперь, что мы убрали какую-нибудь гирю и оставшиеся гири смогли разделить на k равных по весу групп. Как и раньше, получим, что сумма весов оставшихся гирь делится на k^r+1. Вес гири, которую мы убрали, равен разности суммарных весов всех гирь и оставшихся гирь; следовательно, он делится на k^r+1. Значит, если бы мы убрали гирю, вес которой не делится на k^r+1, то оставшиеся гири нельзя было бы разложить на k равных по весу групп. Но в силу выбора числа r гирь, веса которых не делятся на k^r+1, не меньше k, так как иначе они все были бы помещены в первую коробку.

Источники и прецеденты использования

журнал
Название	"Квант"
год
Год	1974
выпуск
Номер	10
Задача
Номер	М289
олимпиада
Название	Московская математическая олимпиада
год
Номер	37
Год	1974
вариант
Класс	9
Тур	2
задача
Номер	3