Предположим, у вас есть k камней и m типов камней. У вас есть камни f1 первого типа, f2 второго и так далее.
(т.е. сумма (f_i) = k).
Кроме того, нам дано натуральное число r.
Какое минимальное количество ведер потребуется, чтобы мы могли распределить типы камней по ведрам, размер каждого из которых не превышает r? (Мы также знаем, что для каждого i f_i ‹= r).
Этот вопрос на самом деле является чем-то вроде упаковки в мусорное ведро, поэтому я не уверен, что на него есть точный ответ, но можем ли мы дать ему верхнюю границу?
Примером тривиальной верхней границы является m, так как это позволит нам упаковать каждый тип камня в его собственное ведро.
Примером границы, которая не работает, является k/r. Причина в том, что если k=9, r=3 и у нас есть 5 типов камней, f1 = 2, f2 = 2, f3 = 2, f4 = 2, f5=1,
Тогда независимо от того, как мы разделяем типы камней, должно быть ведро размером >= 4.
Все камни одного типа должны быть отправлены в одно ведро.
Какие-либо предложения :) ?
РЕДАКТИРОВАТЬ: m и f_i неизвестны, и я ищу границу, которая позволяет мне распределять камни для всех комбинаций (m, f_i).
Другой пример: предположим, что r = 3. Я докажу, что достаточно k/2 ведер:
Обозначим через x количество видов, для которых имеется 3 камня. y будет обозначать количество типов, из которых есть ровно 2 камня, а z будет обозначать количество типов с одним камнем.
По определению: 3x + 2y + z = k. Мы можем выделить x ведер для типов с 3 камнями.
Если (y > z) {первый случай}: Сопоставьте один из типов y вместе с одним из типов z в ведре {у нас есть z таких ведер}.
Установите остальные типы y по одному в ведро.
Поскольку y > z, мы использовали ровно x+y ведер, а поскольку 3x + 2y + z = k => x+y ‹= k/2.
Если (z >= y) {второй случай}: легко видеть, что мы можем поместить все камни в k/3 ведер (каждое ведро может быть полным, содержащим ровно 3 камня).
Кроме того, для r=3 это жестко ограничивает его (если x=z=0 и y=k/2, то нам нужно ровно k/2 ведер).
Теперь возникает вопрос: выполняется ли ограничение k/2 сегментов для всех значений r?
Я могу показать, что нижняя граница (т. е. плотный пример) 2k/(r+1) сегментов, но она довольно далека от k/2. Кто-нибудь может подтянуть связку?
