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 numberand taking the last digit of the sum results in a digit which is not in our original sequence? (Digitsrange from 0 to 9.)
解析
英文解析
- How many ordered sequences of 36 digits have the property that summing the digits to get a numberand taking the last digit of the sum results in a digit which is not in our original sequence? (Digitsrange from 0 to 9.)
Proposed by: Kevin Sun
Answer: 9 + 436
We will solve this problem for 36 replaced by n . We use [ n ] to denote { 1 , 2 , . . . , n } and σ to denotesthe 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
⋃
∣ ∣
the i digit of s . The quantity we are asked to compute is equal to D \ S . We use the principleth
∣ ∣
∣ ∣ii =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 ofin − 2 n − 1 th n − 2