HMMT 二月 2018 · COMB 赛 · 第 9 题
HMMT February 2018 — COMB Round — Problem 9
题目详情
- How many ordered sequences of 36 digits have the property that summing the digits to get a number and taking the last digit of the sum results in a digit which is not in our original sequence? (Digits range from 0 to 9.)
解析
- How many ordered sequences of 36 digits have the property that summing the digits to get a number and taking the last digit of the sum results in a digit which is not in our original sequence? (Digits range from 0 to 9.) Proposed by: Kevin Sun 36 Answer: 9 + 4 We will solve this problem for 36 replaced by n . We use [ n ] to denote { 1 , 2 , . . . , n } and σ to denote s the last digit of the sum of the digits of s . Let D be the set of all sequences of n digits and let S be the set of digit sequences s such that s = σ , i i s ∣ ∣ n ∣ ∣ ⋃ ∣ ∣ th the i digit of s . The quantity we are asked to compute is equal to D \ S . We use the principle ∣ ∣ i ∣ ∣ i =1 of inclusion-exclusion to compute this: ∣ ∣ ∣ ∣ ∣ ∣ n ∣ ∣ ⋃ ∑ ⋂ ∣ ∣ ∣ ∣ | J | ∣ ∣ D \ S = ( − 1) S ∣ ∣ i j ∣ ∣ ∣ ∣ ∣ ∣ i =1 J ⊆ [ n ] j ∈ J Note that a digit sequence is in S if and only if the n − 1 digits which are not i sum to a multiple of i n − 2 n − 1 th n − 2