HMMT 二月 2014 · 冲刺赛 · 第 24 题

HMMT February 2014 — Guts Round — Problem 24

[ 14 ] Let A = { a , a , . . . , a } be a set of distinct positive integers such that the mean of the elements 1 2 7 of any nonempty subset of A is an integer. Find the smallest possible value of the sum of the elements in A . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . HMMT 2014, 22 FEBRUARY 2014 — GUTS ROUND Organization Team Team ID#

解析

[ 14 ] Let A = { a , a , . . . , a } be a set of distinct positive integers such that the mean of the elements 1 2 7 of any nonempty subset of A is an integer. Find the smallest possible value of the sum of the elements in A . Answer: 1267 For 2 ≤ i ≤ 6, we claim that a ≡ . . . ≡ a (mod i ). This is because if we consider 1 7 any i − 1 of the 7 numbers, the other 7 − ( i − 1) = 8 − i of them must all be equal modulo i , because we want the sum of all subsets of size i to be a multiple of i . However, 8 − i ≥ 2, and this argument applies to any 8 − i of the 7 integers, so in fact all of them must be equal modulo i . We now have that all of the integers are equivalent modulo all of 2 , . . . , 6, so they are equivalent modulo 60, their least common multiple. Therefore, if the smallest integer is k , then the other 6 integers must be at least k + 60 , k + 60 · 2 , . . . , k + 60 · 6. This means the sum is 7 k + 60 · 21 ≥ 7 + 60 · 21 = 1267. 1267 is achievable with { 1 , 1 + 60 , . . . , 1 + 60 · 6 } , so it is the answer.