HMMT 二月 2017 · 冲刺赛 · 第 20 题
HMMT February 2017 — Guts Round — Problem 20
题目详情
- [ 10 ] For positive integers a and N , let r ( a, N ) ∈ { 0 , 1 , . . . , N − 1 } denote the remainder of a whendivided by N . Determine the number of positive integers n ≤ 1000000 for whichr ( n, 1000) > r ( n, 1001) .
February 2017, February 18, 2017 — GUTS ROUND
Organization Team Team ID#
英文原题
[ 10 ] For positive integers a and N , let r ( a, N ) ∈ { 0 , 1 , . . . , N − 1 } denote the remainder of a when
divided by N . Determine the number of positive integers n ≤ 1000000 for which
r ( n, 1000) > r ( n, 1001) .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
February 2017, February 18, 2017 — GUTS ROUND
Organization Team Team ID#
解析
英文解析
- [ 10 ] For positive integers a and N , let r ( a, N ) ∈ { 0 , 1 , . . . , N − 1 } denote the remainder of a whendivided by N . Determine the number of positive integers n ≤ 1000000 for whichr ( n, 1000) > r ( n, 1001) .
Proposed by: Pakawut Jiradilok
Answer: 499500
( )
1000
Note that 0 ≤ r ( n, 1000) ≤ 999 and 0 ≤ r ( n, 1001) ≤ 1000 . Consider the = 499500 ways tochoose pairs ( i, j ) such that i > j .By the Chinese Remainder Theorem, there is exactly one n such that 2
1 ≤ n ≤ 1000 · 1001 such that n ≡ i (mod 1000) and n ≡ j (mod 1001) . Finally, it is easy to check thatnone of the n in the range 1000001 to 1001000 satisfy the condition, so the answer is exactly 499500.