返回题库

HMMT 二月 2018 · COMB 赛 · 第 9 题

HMMT February 2018 — COMB Round — Problem 9

专题
Contest Math / 竞赛数学
难度
L3
来源
HMMT

题目详情

英文原题

  1. 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.)
解析

英文解析

  1. 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