ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 79288
Темы:    [ Взвешивания ]
[ Делимость чисел. Общие свойства ]
[ Разбиения на пары и группы; биекции ]
[ Процессы и операции ]
Сложность: 4+
Классы: 8,9,10
В корзину
Прислать комментарий

Условие

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


Решение

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

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

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

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .