HMMT 二月 2015 · COMB 赛 · 第 8 题
HMMT February 2015 — COMB Round — Problem 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, all three digits are nonzero ). For how many elements abc of S is it true that at least one of the (not necessarily distinct) “digit cycles” abc, bca, cab is divisible by 7? (Here, abc denotes the number whose base 10 digits are a , b , and c in that order.)
解析
- 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, all three digits are nonzero ). For how many elements abc of S is it true that at least one of the (not necessarily distinct) “digit cycles” abc, bca, cab is 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 digit representative 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 want the 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 2 Clearly | S | = 7 , since for each of a and b there is a unique c that satisfies the equation. 1 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 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. 2 Thus the answer is 3 · 7 − 3 · 7 + 1 = 127.