Maths Olympiad Prep

Library / /10 of 740

Number theory Difficulty 4.0 AIME Find the answer United States

Problem:
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

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,2,2\}, {0,1,3}\{0,1,3\}, {1,1,2}\{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: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.