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

HMMT February 2015 — Guts Round — Problem 21

[ 14 ] Define a sequence a of integers such that a = n for n ≥ 1 and a = a + a for i,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

解析

[ 14 ] Define a sequence a of integers such that a = n for n ≥ 1 and a = a + a for i,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 ,n n n +1 n +2 and a = n + 2( n + 1) + ( n + 2) . At this point, we can conjecture and prove by induction 3 ,n that ( ) ( ) m − 1 ∑ ∑ m − 1 m − 1 n + k n + k a = ( n + k ) = ( n + k ) . m,n k k k =0 k ≥ 0 ( ) m (The second expression is convenient for dealing with boundary cases. The induction relies on = 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 on k k binomial coefficients. Therefore, we find that ( ) 127 127 ∑ ∑ 127 k +1 k +1 a = ( k + 1) ≡ ( k + 1) ≡ 0 (mod 2) 128 , 1 k k =0 k =0 and ( ) ∑ 127 k +1 a ≡ ( k + 1) ≡ 4 (mod 5) . 128 , 1 k k ∈ [0 , 2] ∪ [125 , 127] Therefore, a ≡ 4 (mod 10). 128 , 1