Задача 78740

Тема:    [ Разбиения на пары и группы; биекции ]

Сложность: 3 Классы: 10,11

Условие

Масса каждой из 19 гирь не больше 70 г и равна целому числу граммов. Доказать, что из этих гирь нельзя составить более 1230 различных по массе наборов.

Решение

Разобьём все наборы на две части: те, в которых не более семнадцати гирь и все остальные. Масса каждого набора из первой части не превосходит  17 ^. 70 = 1190, а значит, среди них не более 1190 различных по массе. С другой стороны, количество наборов во второй части равно 19 + 1 = 20. Следовательно, всего из данных гирь можно составить не более, чем  1190 + 20 = 1210 < 1230 различных по массе наборов.

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

олимпиада
Название	Московская математическая олимпиада
год
Номер	33
Год	1970
вариант
Класс	10
Тур	1
задача
Номер	1