HMMT 二月 2015 · 冲刺赛 · 第 21 题

英文解析

21. [ 14 ] Define a sequence a of integers such that a = n for n ≥ 1 and a = a + a fori,j 1 ,n i,j i − 1 ,j i − 1 ,j +1
    all i, j ≥ 1. Find the last (decimal) digit of a .
    128 , 1
    n n +1
    Answer: 4 By applying the recursion multiple times, we find that a = 1, a = n +( n +1) ,
    1 , 1 2 ,nn n +1 n +2
    and a = n + 2( n + 1) + ( n + 2) . At this point, we can conjecture and prove by induction
    3 ,nthat
    ( ) ( )
    m − 1
    ∑ ∑
    m − 1 m − 1
    n + k n + ka = ( n + k ) = ( n + k ) .
    m,nk kk =0 k ≥ 0
    ( )
    (The second expression is convenient for dealing with boundary cases. The induction relies on =m
    ( ) ( ) ( ) ( )0
    m − 1 m m − 1 m − 1
    on the k = 0 boundary, as well as = + for k ≥ 1.) We fix m = 128. Note that
    0 k k k − 1
    ( ) ( )
    127 127
    ≡ 1 (mod 2) for all 1 ≤ k ≤ 127 and ≡ 0 (mod 5) for 3 ≤ k ≤ 124, by Lucas’ theorem onk kbinomial coefficients. Therefore, we find that
    ( )
    127 127
    ∑ ∑
    k +1 k +1127
    a = ( k + 1) ≡ ( k + 1) ≡ 0 (mod 2)
    128 , 1
    k =0 k =0 kand
    ( )
    ∑
    k +1127
    a ≡ ( k + 1) ≡ 4 (mod 5) .
    128 , 1
    k ∈ [0 , 2] ∪ [125 , 127]k
    Therefore, a ≡ 4 (mod 10).
    128 , 1