Problem:
For m a positive integer, let s(m) be the sum of the digits of m. For n≥2, let f(n) be the minimal k for which there exists a set S of n positive integers such that s(∑x∈X​x)=k for any nonempty subset X⊂S. Prove that there are constants 0<C1​<C2​ with
C1​log10​n≤f(n)≤C2​log10​n
Solution:
For the upper bound, let p be the smallest integer such that 10p≥n(n+1)/2 and let
S={10p−1,2(10p−1),…,n(10p−1)}
The sum of any nonempty set of elements of S will have the form k(10p−1) for some 1≤k≤n(n+1)/2. Write k(10p−1)=[(k−1)10p]+[(10p−1)−(k−1)]. The second term gives the bottom p digits of the sum and the first term gives at most p top digits. Since the sum of a digit of the second term and the corresponding digit of k−1 is always 9 , the sum of the digits will be 9p. Since 10p−1<n(n+1)/2, this example shows that
f(n)≤9p<9log10​(5n(n+1))
Since n≥2,5(n+1)<n4, and hence
f(n)<9log10​n5=45log10​n
For the lower bound, let S be a set of n≥2 positive integers such that any nonempty X⊂S has s(∑x∈X​x)=f(n). Since s(m) is always congruent to m modulo 9,∑x∈X​x≡ f(n)(mod9) for all nonempty X⊂S. Hence every element of S must be a multiple of 9 and f(n)≥9. Let q be the largest positive integer such that 10q−1≤n. Lemma 1 below shows that there is a nonempty subset X of S with ∑x∈X​x a multiple of 10q−1, and hence Lemma 2 shows that f(n)≥9q.
Lemma 1. Any set of m positive integers contains a nonempty subset whose sum is a multiple of m.
Proof. Suppose a set T has no nonempty subset with sum divisible by m. Look at the possible sums mod m of nonempty subsets of T. Adding a new element a to T will give at least one new sum mod m, namely the least multiple of a which does not already occur. Therefore the set T has at least ∣T∣ distinct sums mod m of nonempty subsets and ∣T∣<m.
Lemma 2. Any positive multiple M of 10q−1 has s(M)≥9q.
Proof. Suppose on the contrary that M is the smallest positive multiple of 10q−1 with s(M)<9q. Then Mî€ =10q−1, hence M>10q. Suppose the most significant digit of M is the 10m digit, m≥q. Then N=M−10m−q(10q−1) is a smaller positive multiple of 10q−1 and has s(N)≤s(M)<9q, a contradiction.
Finally, since 10q+1>n, we have q+1>log10​n. Since f(n)≥9q and f(n)≥9, we have
f(n)≥29q+9​>29​log10​n
Weaker versions of Lemmas 1 and 2 are still sufficient to prove the desired type of lower bound.
This problem was proposed by Titu Andreescu and Gabriel Dospinescu.
The problems on this page are the property of the MAA's American Mathematics Competitions