Maths Olympiad Prep

Library / /664 of 740

, 2021

Number theory Difficulty 5.6 AIME, harder Prove it United States

Problem:
Find the smallest positive integer nn such that the divisors of nn can be partitioned into three sets with equal sums.

Solution

Solution:
I claim the answer is 120120. First, note that 120=2335120 = 2^{3} \cdot 3 \cdot 5, so the sum of divisors is (1+2+4+8)(1+3)(1+5)=1546=360(1+2+4+8)(1+3)(1+5) = 15 \cdot 4 \cdot 6 = 360. Thus, we need to split the divisors into groups summing to 120120. But then we can just take {120}\{120\}, {20,40,60}\{20, 40, 60\}, {1,2,3,4,5,6,8,10,12,15,24,30}\{1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 24, 30\}. Thus, 120120 works.

Now we need to show 120120 is the lowest. Let s(n)s(n) be the sum of divisors. Since nn will be in one of the piles, we need s(n)3ns(n) \geq 3n. First, we claim that nn must have at least 33 distinct prime divisors. Surely, if it had 22 distinct prime divisors, say pp and qq, so that n=paqbn = p^{a} q^{b}, then the sum of divisors is
(1+p+p2++pa)(1+q+q2++qb)=paqb(1+1p++1pa)(1+1q++1qb) \left(1 + p + p^{2} + \ldots + p^{a}\right)\left(1 + q + q^{2} + \ldots + q^{b}\right) = p^{a} q^{b}\left(1 + \frac{1}{p} + \ldots + \frac{1}{p^{a}}\right)\left(1 + \frac{1}{q} + \ldots + \frac{1}{q^{b}}\right)
However, the expression 1+1p++1pa1 + \frac{1}{p} + \ldots + \frac{1}{p^{a}} is maximized when pp is minimized, and further, as aa is finite, must be at most 111p=pp1\frac{1}{1 - \frac{1}{p}} = \frac{p}{p-1}. Thus, the sum of divisors is less than
paqbpp1qq1n232=3n p^{a} q^{b} \frac{p}{p-1} \frac{q}{q-1} \leq n \cdot 2 \cdot \frac{3}{2} = 3n
Thus, nn can't have 22 distinct prime divisors and must have at least 33 distinct prime divisors.

As we already discovered 120120 works, we need not worry about 44 distinct prime divisors, as the value of nn would be at least 2357=2102 \cdot 3 \cdot 5 \cdot 7 = 210. We now work through the numbers with 33 distinct divisors. If 22 is not one of them, then the only number that works is 105=357105 = 3 \cdot 5 \cdot 7, which has a sum of divisors that is not large enough. Therefore, 22 must be a prime divisor of nn. Additionally, if 33 is not a divisor, then our options are 2572 \cdot 5 \cdot 7 and 25112 \cdot 5 \cdot 11, which also do not work. Therefore, 33 must also be a prime divisor. Then, if 55 is not a prime divisor, then if nn is 23p2 \cdot 3 \cdot p, it has a sum of divisors of (1+2)(1+3)(1+p)=n3243p+1p(1+2)(1+3)(1+p) = n \cdot \frac{3}{2} \cdot \frac{4}{3} \cdot \frac{p+1}{p}, which is only at least 3n3n if pp is exactly 22, which is not feasible. Additionally, if we use 222^{2}, then the sum of divisors is (1+2+4)(1+3)(1+p)=n7443pp+1(1+2+4)(1+3)(1+p) = n \cdot \frac{7}{4} \cdot \frac{4}{3} \cdot \frac{p}{p+1}, so p+1p>97p<4.5\frac{p+1}{p} > \frac{9}{7} \Longrightarrow p < 4.5, which also can't happen. Further, we can't have 323^{2} be a divisor of nn as 23252 \cdot 3^{2} \cdot 5 is the only value less than 120120 with this, and that also does not work. Lastly, we just need to check 233p2^{3} \cdot 3 \cdot p, which has a sum of divisors of (1+2+4+8)(1+3)(1+p)=n15843p+1p=n52pp+1(1+2+4+8)(1+3)(1+p) = n \cdot \frac{15}{8} \cdot \frac{4}{3} \cdot \frac{p+1}{p} = n \cdot \frac{5}{2} \cdot \frac{p}{p+1}, so p=5p=5 and that works. This means that n=120n=120 is the smallest value for which s(n)3ns(n) \geq 3n, and thus is our answer.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.