PUMaC 2016 · 数论（A 组） · 第 2 题
PUMaC 2016 — Number Theory (Division A) — Problem 2
题目详情
- For positive integers i and j , define d as follows: d = 1, d = 1 for all i and j , and ( i,j ) (1 ,j ) ( i, 1) for i, j > 1, d = d + d + d . Compute the remainder when d is ( i,j ) ( i − 1 ,j ) ( i,j − 1) ( i − 1 ,j − 1) (3 , 2016) divided by 1000.
解析
- For j > 1, we have d = d + 2, which gives d = 2 j − 1. This means that for j > 1, (2 ,j ) (2 ,j − 1) (2 ,j ) we have d = d + 2 j − 1 + 2 j − 3 = d + 4( j − 1) . (3 ,j ) (3 ,j − 1) (3 ,j − 1) Thus, 2015 · 2016 d = 1 + 4 + 8 + · · · + 4 · 2015 = 1 + 4 · ≡ 1 + 2 · 15 · 16 ≡ 481 (mod 1000) . (3 , 2016) 2 Problem written by Ryan Lee.