Let S={a1,a2,...,ap-1}, and define a function f(A)=SUM(a | a in A) (mod p). Also, for 1<=k<=p-1, define Sk to be {a1,...,ak}.
Claim: For any k<p, at least k+1 distinct values occur as sums of subsets of Sk (mod p).
Note that the desired result would follow from the case k=p-1. It thus suffices to prove the claim.
Proof: When k=1, the claim is clear, as 0 and a1 are two distinct values that occur as sums of subsets of S1 (mod p) (namely, the empty set and S1, respectively).
We proceed by induction. Suppose the claim is true for some k<p-1. Then, there exist subsets T0,...,Tk of Sk with distinct sums (mod p) of t0,...,tk, respectively.
Consider the subsets T'0,...,T'k defined by the following relation:
It follows from the inductive hypothesis that the values f(T'0),f(T'1),...,f(T'k) are distinct, since t'i=ti+ak+1 and t'j=tj+ak+1 are distinct whenever ti and tj are. It suffices to show that at least one of those values are distinct from the values t0,...,tk. For if t'i is distinct from t0,...,tk, then t0,...,tk, t'i, represent k+2 distinct values that occur as sums of subsets of Sk+1 (mod p).
Suppose the contrary. Then, {t0, t1,...,
tk} represents a permutation of {t'0, t'1,..., t'k}. Adding, we have
t0+t1+...+tk = t'0+t'1+...+t'k (mod p)
= (t0+ak+1)+(t1+ak+1)+...+(tk+ak+1) (mod p)
=(t0+t1+...+tk)+(k+1)ak+1 (mod p)
or
(k+1)ak+1=0 (mod p)
Now, since k<p-1, we have that (k+1) is not divisible by p, implying that ak+1=0 (mod p), a contradiction. This completes the proof. |
