Maths Olympiad Prep

Library / HMMT February /538 of 1302

HMMT February

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 n−mn-m.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Let a=2021a=2021 and b=2000b=2000. It is clear that we may increase y−xy-x unless both x−1x-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+1≤b(k+1)−1⟹(a−b)k≤b−2⟹k≤⌊b−2a−b⌋a 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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.