Условие
Каково наименьшее число гирь в наборе, который можно разложить и на 3, и на
4, и на 5 кучек равной массы?
Решение
Ответ: 9.
Докажем сначала, что в наборе не может быть меньше девяти гирь. Предположим,
что это не так, то есть их не более восьми. Пусть 60
m — общая масса всех
гирь в наборе. Заметим сначала, что в наборе не может быть гирь массой
больше 12
m (так как набор можно разделить на пять кучек массой 12
m
каждая). Следовательно, в каждой из четырёх кучек массой 15
m не менее двух
гирь. Следовательно, всего гирь не менее восьми. Значит, их ровно восемь, а
каждая из четырёх кучек массы 15
m состоит ровно из двух гирь. Когда мы
раскладываем эти восемь гирь на пять кучек, в каких-то двух из них будет по
одной гире. Следовательно, в наборе не менее двух гирь массой 12
m.
Докажем, что в наборе не менее шести гирь массой вида 3
km, где
число
k — натуральное.
Допустим сначала, что в наборе не менее трёх гирь массой 12
m. Тогда в нём
не менее трёх гирь массой 3
m, а значит, не менее шести гирь массой
вида 3
km. Теперь рассмотрим случай, когда в наборе есть ровно две гири
массой 12
m. Тогда в этом наборе есть две гири массой 3
m. А значит, массы
гирь, лежащих в тех же кучках при разбиении на пять кучек, что и гири
массой 3
m, равны 9
m. Следовательно, в наборе не менее шести гирь массой
вида 3
km. Итак, в любом случае в наборе не менее шести гирь массой
вида 3
km, где число
k — натуральное.
Тогда при разбиении на три кучки одна из кучек должна состоять только из
гирек такого вида, а значит её масса не может равняться 20
m.
Осталось доказать, что существует набор из девяти гирь. Подходит, например,
набор из гирь массой
3, 4, 5, 6, 6, 7, 8, 9, 12 грамм.
Проверку того, что этот набор можно разложить и на 3, и на 4, и на 5 кучек
равной массы, мы оставляем читателю в качестве упражнения.
Источники и прецеденты использования
