Let $ n \in \mathbb{N} $, $ n>1 $ and $ a_1,\ldots,a_k \in \mathbb{N} $ (not necessarily distinct!) with $ a_i \mid n $ for all $ i=1,\ldots,k $ be given. Assume that $ \sum_{i=1}^k a_i = K\cdot n $ for some $ K \in \mathbb{N} $. A subset $ M \subseteq \lbrace 1,\ldots,k \rbrace $ is called strong, if $ \sum_{i \in M} a_i \ge n$. Let $ m:=m(n,a) \in \mathbb{N} $ denote the maximum number of pairwise disjoint strong subsets.
- Clearly $ m\le K $. In which cases we have $ m=K $? Is there a characterization?
- Is it always possible to find at least $ K-1 $ pairwise disjoint strong subsets?
- Is there a closed expression for $ m(n,a) $, depending on the input data $ n $ and the vector of divisors $ a=(a_1,\ldots,a_k)^{\top} $?
If anyone has an idea, please write it. Thanks for your help.
(This question arises e.g. in covering problems. With the help of some small pieces, the $ a_i $'s, as many items of length $ n $ as possible have to be covered.)
As an initial step one could do the following: Let us consider minimal strong subsets $ M \subseteq \lbrace 1,\ldots,k \rbrace $, i.e., no real subset $ M' \subset M $ is strong. For such a set obviously $ \sum_{i\in M} a_i \le n-1+a^\star $ holds, where $ a^\star:= \max \left\lbrace a_i \, : \, a_i < \max_{j \in \lbrace 1\ldots,k \rbrace} \lbrace a_j \rbrace \right\rbrace $, i.e., the second largest (with resprect to "$ < $") number $ a_i $. Thus we have: $ m \ge \left\lfloor \frac{n\cdot K}{n-1+a^\star} \right\rfloor $
But this is only a beginning. I hope, there are other people who know stronger bounds for $ m $.