I have a positive integer $n$, and a multiset $S$ of positive integers. $S$ has $n$ elements. For all $s \in S$, $s$ is a divisor of $n$.
I believe that there must exist a subset (submultiset) $S' \subset S$ such that the elements of $S'$ sum to $n$.
For example, $n$ could be 6, and $S$ could be $[1,1,1,2,2,3]$. In this case, the conjecture is true, because $S'$ could be $[1,1,1,3], [1,1,2,2],$ or $[1,2,3]$.
Must such an $S'$ always exist?
Partial results:
-
If $n$ is a prime power, such an $S'$ always exists. In particular, if we order the elements of $S$ from largest to smallest, some prefix of that ordering must sum to exactly $n$.
-
More generally, if every element of $S$ is divisible by all smaller elements of $S$, then an $S'$ exists which is a prefix of the largest-to-smallest ordering.
-
If $S$ had $\sigma(n)$ elements, rather than just $n$ elements, then there would always exist such an $S'$ whose elements were all the same integer.
Best Answer
Well, it was extremely messy, but I solved it. Such an $S'$ (which I call a perfect subset) always exists. I wrote up the proof here: https://isaacg1.github.io/2021/12/11/divisors.html.
The basic structure of the proof is a strong induction on $n$, the size of the multiset. I then did a case analysis on the factorization of $n$, and the amounts of different kinds of elements of $S$. When $S$ has many elements that are multiples of a given prime factor of $n$, it is possible to construct a perfect subset. When $S$ has many 1s, it is possible to construct a perfect subset. When $S$ has many elements greater than 1 that are not multiples of a given prime factor of $n$, it is possible to construct a perfect subset. Using these three scenarios repeatedly to eliminate various cases, I was eventually able to cover every possibility, showing that a perfect subset always exists.
A complete proof can be found in Appendix A of the full version of my paper "WCFS: a new framework for analyzing multiserver systems", published in the Queueing Systems journal.