HMMT 二月 2015 · COMB 赛 · 第 8 题

英文解析

8. Let S be the set of all 3-digit numbers with all digits in the set { 1 , 2 , 3 , 4 , 5 , 6 , 7 } (so in particular, allthree digits are nonzero ). For how many elements abc of S is it true that at least one of the (notnecessarily distinct) “digit cycles”
   abc, bca, cabis divisible by 7? (Here, abc denotes the number whose base 10 digits are a , b , and c in that order.)
   Answer: 127 Since the value of each digit is restricted to { 1 , 2 , . . . , 7 } , there is exactly one digitrepresentative of each residue class modulo 7.
   Note that 7 | abc if and only if 100 a + 10 b + c ≡ 0 (mod 7) or equivalently 2 a + 3 b + c ≡ 0. So we wantthe number of triples of residues ( a, b, c ) such that at least one of 2 a + 3 b + c ≡ 0, 2 b + 3 c + a ≡ 0,
   2 c + 3 a + b ≡ 0 holds.
   Let the solution sets of these three equations be S , S , S respectively, so by PIE and cyclic symmetry
   1 2 3
   we want to find 3 | S | − 3 | S ∩ S | + | S ∩ S ∩ S | .
   1 1 2 1 2 3
   Clearly | S | = 7 , since for each of a and b there is a unique c that satisfies the equation.2
   For S ∩ S , we may eliminate a to get the system 0 ≡ 2(2 b + 3 c ) − (3 b + c ) = b + 5 c (and a ≡ − 2 b − 3 c ),1
   1 2
   which has 7 solutions (one for each choice of c ).
   For S ∩ S ∩ S ⊆ S ∩ S , we have from the previous paragraph that b ≡ − 5 c and a ≡ 10 c − 3 c ≡ 0.
   1 2 3 1 2
   By cyclic symmetry, b, c ≡ 0 as well, so there’s exactly 1 solution in this case.
   Thus the answer is 3 · 7 − 3 · 7 + 1 = 127.2