HMMT 二月 2016 · 冲刺赛 · 第 8 题

HMMT February 2016 — Guts Round — Problem 8

[ 6 ] For each positive integer n and non-negative integer k , define W ( n, k ) recursively by { n n k = 0 W ( n, k ) = W ( W ( n, k − 1) , k − 1) k > 0 . Find the last three digits in the decimal representation of W (555 , 2). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . HMMT February 2016, February 20, 2016 — GUTS ROUND Organization Team Team ID#

解析

[ 6 ] For each positive integer n and non-negative integer k , define W ( n, k ) recursively by { n n k = 0 W ( n, k ) = W ( W ( n, k − 1) , k − 1) k > 0 . Find the last three digits in the decimal representation of W (555 , 2). Proposed by: Answer: 875 For any n , we have n n +1 n n n W ( n, 1) = W ( W ( n, 0) , 0) = ( n ) = n . Thus, 556 555 W (555 , 1) = 555 . Let N = W (555 , 1) for brevity, and note that N ≡ 0 (mod 125), and N ≡ 3 (mod 8). Then, N +1 N W (555 , 2) = W ( N, 1) = N is 0 (mod 125) and 3 (mod 8). From this we can conclude (by the Chinese Remainder Theorem) that the answer is 875.