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 k = 0 n
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
W ( n, k ) =
{
n n k = 0
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 k = 0 n
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 haven n +1
n n n
W ( n, 1) = W ( W ( n, 0) , 0) = ( n ) = n .
Thus,
555556
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
W (555 , 2) = W ( N, 1) = NNis 0 (mod 125) and 3 (mod 8).
From this we can conclude (by the Chinese Remainder Theorem) that the answer is 875.