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

HMMT November 2016 — Guts Round — Problem 9

[ 7 ] How many 3-element subsets of the set { 1 , 2 , 3 , . . . , 19 } have sum of elements divisible by 4? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . HMMT November 2016, November 12, 2016 — GUTS ROUND Organization Team Team ID#

解析

[ 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