返回题库

HMMT 二月 2017 · 冲刺赛 · 第 20 题

HMMT February 2017 — Guts Round — Problem 20

专题
Contest Math / 竞赛数学
难度
L3
来源
HMMT

题目详情

  1. [ 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#

解析

英文解析

  1. [ 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.