Maths Olympiad Prep

Library / /203 of 348

Number theory Difficulty 4.9 AIME Find the answer

How many 3-element subsets of the set {1,2,3,,19}\{1,2,3, \ldots, 19\} have sum of elements divisible by 4?

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Consider the elements of the sets mod 4. Then we would need to have sets of the form {0,0,0}\{0,0,0\}, {0,2,2},{0,1,3},{1,1,2}\{0,2,2\},\{0,1,3\},\{1,1,2\}, or {2,3,3}\{2,3,3\}. In the set {1,2,,19}\{1,2, \ldots, 19\} there are four elements divisible by 4 and 5 elements congruent to each of 1,2,3mod41,2,3 \bmod 4. Hence the desired number is given by (43)+(41)(52)+(41)(51)(51)+(52)(51)+(51)(52)=244\binom{4}{3}+\binom{4}{1}\binom{5}{2}+\binom{4}{1}\binom{5}{1}\binom{5}{1}+\binom{5}{2}\binom{5}{1}+\binom{5}{1}\binom{5}{2}=244

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.