Maths Olympiad Prep

Library / /612 of 740

Number theory Difficulty 5.3 AIME, harder Prove it United States

Problem:
Find the number of ordered triples of divisors (d1,d2,d3)\left(d_{1}, d_{2}, d_{3}\right) of 360360 such that d1d2d3d_{1} d_{2} d_{3} is also a divisor of 360360.

Solution

Solution:
Answer: 800800

Since 360=23325360=2^{3} \cdot 3^{2} \cdot 5, the only possible prime divisors of did_{i} are 22, 33, and 55, so we can write di=2ai3bi5cid_{i}=2^{a_{i}} \cdot 3^{b_{i}} \cdot 5^{c_{i}}, for nonnegative integers ai,bia_{i}, b_{i}, and cic_{i}. Then, d1d2d3360d_{1} d_{2} d_{3} \mid 360 if and only if the following three inequalities hold.
a1+a2+a33b1+b2+b32c1+c2+c31 \begin{aligned} a_{1}+a_{2}+a_{3} & \leq 3 \\ b_{1}+b_{2}+b_{3} & \leq 2 \\ c_{1}+c_{2}+c_{3} & \leq 1 \end{aligned}
Now, one can count that there are 2020 assignments of aia_{i} that satisfy the first inequality, 1010 assignments of bib_{i} that satisfy the second inequality, and 44 assignments of cic_{i} that satisfy the third inequality, for a total of 800800 ordered triples (d1,d2,d3)\left(d_{1}, d_{2}, d_{3}\right).

(Alternatively, instead of counting, it is possible to show that the number of nonnegative-integer triples (a1,a2,a3)\left(a_{1}, a_{2}, a_{3}\right) satisfying a1+a2+a3na_{1}+a_{2}+a_{3} \leq n equals (n+33)\binom{n+3}{3}, since this is equal to the number of nonnegative-integer quadruplets (a1,a2,a3,a4)(a_{1}, a_{2}, a_{3}, a_{4}) satisfying a1+a2+a3+a4=na_{1}+a_{2}+a_{3}+a_{4}=n.)

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.