HMMT 十一月 2015 · 冲刺赛 · 第 20 题

英文解析

20. [ 11 ] Let n be a three-digit integer with nonzero digits, not all of which are the same. Define f ( n ) to bethe greatest common divisor of the six integers formed by any permutation of n s digits. For example,
    f (123) = 3, because gcd(123 , 132 , 213 , 231 , 312 , 321) = 3. Let the maximum possible value of f ( n ) bek . Find the sum of all n for which f ( n ) = k .
    Proposed by: Alexander Katz
    Answer: 5994
    Let n = abc , and assume without loss of generality that a ≥ b ≥ c . We have k | 100 a + 10 b + c andk | 100 a + 10 c + b , so k | 9( b − c ). Analogously, k | 9( a − c ) and k | 9( a − b ). Note that if 9 | n , then 9
    also divides any permutation of n s digits, so 9 | f ( n ) as well; ergo, f ( n ) ≥ 9, implying that k ≥ 9. If kis not a multiple of 3, then we have k | c − a = ⇒ k ≤ c − a < 9, contradiction, so 3 | k .
    Let x = min( a − b, b − c, a − c ). If x = 1, then we have k | 9, implying k = 9 - irrelevant to ourinvestigation. So we can assume x ≥ 2. Note also that x ≤ 4, as 2 x ≤ ( a − b ) + ( b − c ) = a − c ≤ 9 − 1,
    and if x = 4 we have n = 951 = ⇒ f ( n ) = 3. If x = 3, then since 3 | k | 100 a +10 b + c = ⇒ 3 | a + b + c ,
    we have a ≡ b ≡ c (mod 3) (e.g. if b − c = 3, then b ≡ c (mod 3), so a ≡ b ≡ c (mod 3) - the other casesare analogous). This gives us the possibilites n = 147 , 258 , 369, which give f ( n ) = 3 , 3 , 9 respectively.
    Hence we can conclude that x = 2; therefore k | 18. We know also that k ≥ 9, so either k = 9 ork = 18. If k = 18, then all the digits of n must be even, and n must be a multiple of 9; it is clear that these are sufficient criteria. As n ’s digits are all even, the sum of them is also even, and hence theirsum is 18. Since a ≥ b ≥ c , we have a + b + c = 18 ≤ 3 a = ⇒ a ≥ 6, but if a = 6 then a = b = c = 6,
    contradicting the problem statement. Thus a = 8, and this gives us the solutions n = 882 , 864 alongwith their permutations.
    It remains to calculate the sum of the permutations of these solutions. In the n = 882 case, each digitis either 8, 8, or 2 (one time each), and in the n = 864 case, each digit is either 8, 6, or 4 (twice each).
    Hence the desired sum is 111(8 + 8 + 2) + 111(8 · 2 + 6 · 2 + 4 · 2) = 111(54) = 5994 .