17
$\begingroup$

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.

$\endgroup$
5
  • 3
    $\begingroup$ If we want to construct a counter-example, the number of occurrences $f_d$ of a divisor $d\gt 1$ in $S$ is clearly smaller than $n/d$, and often much smaller because it is also limited by the number of (disjoint) submultisets of $S$ that sum to $d$. On the other hand, $\sum_{d\gt 1} f_d$ must be large enough (s.t. number of $1$'s in $S$ is small enough). Idea is proof by contradiction, but problem is showing that divisors $d\gt 1$ sum to other divisors often enough when there is a lot of them. $\endgroup$
    – Vepir
    Commented Dec 6, 2021 at 0:09
  • $\begingroup$ I can show that if the multiset only have proper divisors greater than 1 then the property follows, but i cant show the property if there are $k$ ones such that $n-k>k$ $\endgroup$
    – Tom Keen
    Commented Dec 7, 2021 at 3:47
  • $\begingroup$ @TomKeen I'd be interested to see your argument when there are no $1$s. But I'm confused about the last part of your comment; do you mean $n-k < k$, because $k=0$ gives $n-k>k$? $\endgroup$
    – mathworker21
    Commented Dec 7, 2021 at 4:12
  • $\begingroup$ @mathworker21 the idea is to infer from extreme cases, if $\hat{x}$ is the number of propers divisors of $n$, then some proper divisor in the multiset appears at least $n/\hat{x}$ times $\endgroup$
    – Tom Keen
    Commented Dec 7, 2021 at 16:24
  • $\begingroup$ @TomKeen If you want to post your proof that "If all elements of $S$ are greater than 1, the property holds", I'd be very interested in that partial result. $\endgroup$
    – isaacg
    Commented Dec 7, 2021 at 18:31

1 Answer 1

Reset to default
5
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .