HMMT 二月 2021 · ALGNT 赛 · 第 6 题

HMMT February 2021 — ALGNT Round — Problem 6

Suppose that m and n are positive integers with m < n such that the interval [ m, n ) contains more multiples of 2021 than multiples of 2000. Compute the maximum possible value of n − m .

解析

Suppose that m and n are positive integers with m < n such that the interval [ m, n ) contains more multiples of 2021 than multiples of 2000. Compute the maximum possible value of n − m . Proposed by: Carl Schildkraut Answer: 191999 Solution: Let a = 2021 and b = 2000. It is clear that we may increase y − x unless both x − 1 and y + 1 are multiples of b , so we may assume that our interval is of length b ( k + 1) − 1, where there are k multiples of b in our interval. There are at least k + 1 multiples of a , and so it is of length at least ak + 1. We thus have that ⌊ ⌋ b − 2 ak + 1 ≤ b ( k + 1) − 1 = ⇒ ( a − b ) k ≤ b − 2 = ⇒ k ≤ . a − b So, the highest possible value of k is 95, and this is achievable by the Chinese remainder theorem, giving us an answer of 191999.