Maths Olympiad Prep

Library / /613 of 860

Combinatorics Difficulty 5.3 AIME, harder Find the answer

Determine the number of subsets SS of {1,2,,1000}\{1,2, \ldots, 1000\} that satisfy the following conditions: - SS has 19 elements, and - the sum of the elements in any non-empty subset of SS is not divisible by 20 .

A number or a short expression. Spacing and $ signs are ignored.

Solution

First we prove that each subset must consist of elements that have the same residue mod 20. Let a subset consist of elements a1,,a19a_{1}, \ldots, a_{19}, and consider two lists of partial sums a1,a1+a2,a1+a2+a3,,a1+a2++a19a2,a1+a2,a1+a2+a3,,a1+a2++a19\begin{aligned} & a_{1}, a_{1}+a_{2}, a_{1}+a_{2}+a_{3}, \ldots, a_{1}+a_{2}+\cdots+a_{19} \\ & a_{2}, a_{1}+a_{2}, a_{1}+a_{2}+a_{3}, \ldots, a_{1}+a_{2}+\cdots+a_{19} \end{aligned} 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 (mod20)(\bmod 20). Since the residues must also be nonzero, each list forms a complete nonzero residue class mod20\bmod 20. Since the latter 18 sums in the two lists are identical, a1a2(mod20)a_{1} \equiv a_{2}(\bmod 20). By symmetric arguments, aiaj(mod20)a_{i} \equiv a_{j}(\bmod 20) for any i,ji, j. Furthermore this residue 1r201 \leq r \leq 20 must be relatively prime to 20, because if d=gcd(r,20)>1d=\operatorname{gcd}(r, 20)>1 then any 20/d20 / d elements of the subset will sum to a multiple of 20. Hence there are φ(20)=8\varphi(20)=8 possible residues. Since there are 50 elements in each residue class, the answer is (5019)\binom{50}{19}. We can see that any such subset whose elements are a relatively prime residue r(mod20)r(\bmod 20) works because the sum of any 1k191 \leq k \leq 19 elements will be kr0(mod20)k r \neq 0(\bmod 20)

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.