Condition for Sums in a Set

Question

Let $$ S = \{ a_1,a_2, \cdots , a_k \}$$ be comprised of divisors of $n \in \mathbb{N}, n>1$ and $n$ not prime. Suppose we select $p$ elements from the set $S$ (possibly more than once for each divisor), and the $p$ chosen elements have a total sum of $q$. Prove that it is always possible to select $q$ elements with a sum of $np$.

I suppose that I should add what I have done so far. I tried to roughly calculate the maximum number of times the largest divisor less than $n$ will go into the number, and then repeated the process until I had constructed a number less than $n$ such that the difference between the number I had formed was less than $a_2$ times the number of elements I have left to form the number. This approach seems to lack rigour though, and I have a hunch that a constructive method is not the way to go about this problem. Also, a natural extension would be to do the problem, but with the constraint that we are not allowed to select some of the divisors of $n$ as part of the $p$ elements at all. Thanks

Answer 1

The restriction on $n$ isn't necessary: it's true for $n$ prime as well as $n$ composite (and even, trivially, for $n=1$). Indeed, I came up with the following solution by considering the case where $n$ is prime.

Suppose that $a_1,\dots,a_p$ are (not necessarily distinct) divisors of $n$, and set $q=a_1+\cdots+a_p$. Define a sequence of $q$ divisors of $n$ as follows: first take $a_1$ copies of $\frac n{a_1}$, then $a_2$ copies of $\frac n{a_2}$, and so on through $a_p$ copies of $\frac n{a_p}$.

• The total number of divisors in this sequence is indeed $a_1+\cdots+a_p=q$.
• Each batch of divisors sums to $a_j \cdot \frac n{a_j} = n$, and there are $p$ batches of divisors; so the total sum is $np$.

(Side note: if you iterate this process twice, you get back the concatenation of $n$ copies of the original sequence.)