Olympiad Maths Prep

Library / /7 of 16

Number theory Difficulty 5.1 AIME, harder Prove it Ukraine

Find all integers nn that have more than n2\frac{n}{2} divisors.

Solution

Answer: n{1;2;3;4;6}n \in \{1; 2; 3; 4; 6\}.

Clearly a number cannot have divisors greater than n2\frac{n}{2}, besides nn itself. Therefore, in order to have more than n2\frac{n}{2} divisors it must be divisible by all numbers from 11 to n2\frac{n}{2} and by nn. Denote by mm the integer number which equals either n2\frac{n}{2} or n12\frac{n-1}{2}. Then if n10n \ge 10, either mm or m1m-1 is coprime with 33. Hence, n3mn \ge 3m, because it must be divisible by both 33 and mm. However, in this case n3(n121)n \ge 3 \cdot (\frac{n-1}{2} - 1), or 2n3n92n \ge 3n - 9, which contradicts the assumption that n10n \ge 10. All numbers n<10n < 10 can be checked by hand.

Looking for a route rather than 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.