HMMT 十一月 2016 · 冲刺赛 · 第 9 题

英文解析

9. [ 7 ] How many 3-element subsets of the set { 1 , 2 , 3 , . . . , 19 } have sum of elements divisible by 4?
   Proposed by: Sam Korsky
   Answer: 244
   Consider the elements of the sets mod 4. Then we would need to have sets of the form { 0 , 0 , 0 } ,
   { 0 , 2 , 2 } , { 0 , 1 , 3 } , { 1 , 1 , 2 } , or { 2 , 3 , 3 } . In the set { 1 , 2 , . . . , 19 } there four elements divisible by 4 and
   5 elements congruent to each of 1 , 2 , 3 mod 4. Hence the desired number is given by
   ( ) ( )( ) ( )( )( ) ( )( ) ( )( )
   4 4 5 4 5 5 5 5 5 5 + + + + = 244
   3 1 2 1 1 1 2 1 1 2