Determine the number of subsets of that satisfy the following conditions: - has 19 elements, and - the sum of the elements in any non-empty subset of is not divisible by 20 .
Solution
First we prove that each subset must consist of elements that have the same residue mod 20. Let a subset consist of elements , and consider two lists of partial sums The residues mod 20 of the partial sums in each list must be pairwise distinct, otherwise subtracting the sum with less terms from the sum with more terms yields a subset whose sum of elements is 0 . Since the residues must also be nonzero, each list forms a complete nonzero residue class . Since the latter 18 sums in the two lists are identical, . By symmetric arguments, for any . Furthermore this residue must be relatively prime to 20, because if then any elements of the subset will sum to a multiple of 20. Hence there are possible residues. Since there are 50 elements in each residue class, the answer is . We can see that any such subset whose elements are a relatively prime residue works because the sum of any elements will be