Maths Olympiad Prep

Library / /4 of 16

Number theory Difficulty 5.2 AIME, harder Prove it Austria

For which number from 20002000 through 21002100 is the probability that a randomly chosen divisor will not be greater than 4545 the largest? (Note: The probability is equal to the number of divisors not greater than 4545 divided by the total number of divisors.)

Solution

We first note that 452=202545^2 = 2025. For any number nn, the number of divisors less than n\sqrt{n} is certainly equal to the number of divisors greater than n\sqrt{n}, since 0<t<n0 < t < \sqrt{n} implies nt>n\frac{n}{t} > \sqrt{n} and tnt|n implies ntn\frac{n}{t}|n (and vice versa).

For all numbers from 20002000 through 21002100, we have 44<n<4644 < \sqrt{n} < 46. For all of these numbers, the number of divisors less than 4545 is therefore equal to the number of divisors greater than 4545. It follows that the probability of a random number being not greater than 4545 is equal to 12\frac{1}{2} for all n2025n \neq 2025.

For n=2025n = 2025, 4545 is also a divisor, but since nt=t\frac{n}{t} = t in this case, the probability for 20252025 is greater than 12\frac{1}{2}, and 20252025 is therefore the number with the required property. \square

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: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.