HMMT 二月 2019 · 冲刺赛 · 第 24 题
HMMT February 2019 — Guts Round — Problem 24
题目详情
- [ 12 ] Let S be the set of all positive factors of 6000. What is the probability of a random quadruple 4 ( a, b, c, d ) ∈ S satisfies lcm(gcd( a, b ) , gcd( c, d )) = gcd(lcm( a, b ) , lcm( c, d ))? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . HMMT February 2019, February 16, 2019 — GUTS ROUND Organization Team Team ID#
解析
- [ 12 ] Let S be the set of all positive factors of 6000. What is the probability of a random quadruple 4 ( a, b, c, d ) ∈ S satisfies lcm(gcd( a, b ) , gcd( c, d )) = gcd(lcm( a, b ) , lcm( c, d ))? Proposed by: Yuan Yao 41 Answer: 512 For each prime factor, let the greatest power that divides a, b, c, d be p, q, r, s . WLOG assume that p ≤ q and r ≤ s , and further WLOG assume that p ≤ r . Then we need r = min( q, s ). If q = r then we have p ≤ q = r ≤ s , and if r = s then we have p ≤ r = s ≤ q , and in either case the condition reduces to the two “medians” among p, 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 ) of integers between 0 and n inclusive that satisfy ( ) n +1 the above condition. If there are three distinct numbers then there are ways to choose the three 3 numbers and 4! / 2 = 12 ways to assign them (it must be a 1-2-1 split). If there are two distinct numbers ( ) n +1 then there are ways to choose the numbers and 4 + 4 = 8 ways to assign them (it must be a 3-1 2 or a 1-3 split). If there is one distinct number then there are n + 1 ways to assign. Together we have ( ) ( ) n + 1 n + 1 12 + 8 + ( n + 1) = 2( n + 1) n ( n − 1) + 4( n + 1) n + ( n + 1) = ( n + 1)(2 n ( n + 1) + 1) 3 2 possible quadruples. So if we choose a random quadruple then the probability that it satisfies the ( n +1)(2 n ( n +1)+1) 2 n ( n +1)+1 condition is = . 4 3 ( n +1) ( n +1) 4 3 1 Since 6000 = 2 · 5 · 3 and the power of different primes are independent, we plug in n = 4 , 3 , 1 to get the overall probability to be 41 25 5 41 · · = . 125 64 8 512