Maths Olympiad Prep

Library / /463 of 860

Number theory Difficulty 5.2 AIME, harder Find the answer

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

A number or a short expression. Spacing and $ signs are ignored.

Solution

Let a=2021a=2021 and b=2000b=2000. It is clear that we may increase yxy-x unless both x1x-1 and y+1y+1 are multiples of bb, so we may assume that our interval is of length b(k+1)1b(k+1)-1, where there are kk multiples of bb in our interval. There are at least k+1k+1 multiples of aa, and so it is of length at least ak+1a k+1. We thus have that ak+1b(k+1)1(ab)kb2kb2aba k+1 \leq b(k+1)-1 \Longrightarrow(a-b) k \leq b-2 \Longrightarrow k \leq\left\lfloor\frac{b-2}{a-b}\right\rfloor So, the highest possible value of kk is 95, and this is achievable by the Chinese remainder theorem, giving us an answer of 191999.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.