Maths Olympiad Prep

Library / /484 of 860

Number theory Difficulty 5.2 AIME, harder Find the answer

Let SS be the set of all positive factors of 6000. What is the probability of a random quadruple (a,b,c,d)S4(a, b, c, d) \in S^{4} satisfies lcm(gcd(a,b),gcd(c,d))=gcd(lcm(a,b),lcm(c,d))?\operatorname{lcm}(\operatorname{gcd}(a, b), \operatorname{gcd}(c, d))=\operatorname{gcd}(\operatorname{lcm}(a, b), \operatorname{lcm}(c, d)) ?

A number or a short expression. Spacing and $ signs are ignored.

Solution

For each prime factor, let the greatest power that divides a,b,c,da, b, c, d be p,q,r,sp, q, r, s. WLOG assume that pqp \leq q and rsr \leq s, and further WLOG assume that prp \leq r. Then we need r=min(q,s)r=\min (q, s). If q=rq=r then we have pq=rsp \leq q=r \leq s, and if r=sr=s then we have pr=sqp \leq r=s \leq q, and in either case the condition reduces to the two 'medians' among p,q,r,sp, q, r, s are equal. (It is not difficult to see that this condition is also sufficient.) Now we compute the number of quadruples (p,q,r,s)(p, q, r, s) of integers between 0 and nn inclusive that satisfy the above condition. If there are three distinct numbers then there are (n+13)\binom{n+1}{3} ways to choose the three numbers and 4!/2=124!/ 2=12 ways to assign them (it must be a 1211-2-1 split). If there are two distinct numbers then there are (n+12)\binom{n+1}{2} ways to choose the numbers and 4+4=84+4=8 ways to assign them (it must be a 313-1 or a 1-3 split). If there is one distinct number then there are n+1n+1 ways to assign. Together we have 12(n+13)+8(n+12)+(n+1)=2(n+1)n(n1)+4(n+1)n+(n+1)=(n+1)(2n(n+1)+1)12\binom{n+1}{3}+8\binom{n+1}{2}+(n+1)=2(n+1) n(n-1)+4(n+1) n+(n+1)=(n+1)(2 n(n+1)+1) possible quadruples. So if we choose a random quadruple then the probability that it satisfies the condition is (n+1)(2n(n+1)+1)(n+1)4=2n(n+1)+1(n+1)3\frac{(n+1)(2 n(n+1)+1)}{(n+1)^{4}}=\frac{2 n(n+1)+1}{(n+1)^{3}}. Since 6000=2453316000=2^{4} \cdot 5^{3} \cdot 3^{1} and the power of different primes are independent, we plug in n=4,3,1n=4,3,1 to get the overall probability to be 41125256458=41512\frac{41}{125} \cdot \frac{25}{64} \cdot \frac{5}{8}=\frac{41}{512}

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.