返回题库

HMMT 二月 2019 · 冲刺赛 · 第 24 题

HMMT February 2019 — Guts Round — Problem 24

专题
Contest Math / 竞赛数学
难度
L3
来源
HMMT

题目详情

  1. [ 12 ] Let S be the set of all positive factors of 6000. What is the probability of a random quadruple
    ( a, b, c, d ) ∈ S satisfies 4
    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
( a, b, c, d ) ∈ S 4 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#

解析

英文解析

  1. [ 12 ] Let S be the set of all positive factors of 6000. What is the probability of a random quadruple
    ( a, b, c, d ) ∈ S satisfies 4
    lcm(gcd( a, b ) , gcd( c, d )) = gcd(lcm( a, b ) , lcm( c, d ))?
    Proposed by: Yuan Yao
    Answer:41
    For each prime factor, let the greatest power that divides a, b, c, d be p, q, r, s . WLOG assume that 512
    p ≤ q and r ≤ s , and further WLOG assume that p ≤ r . Then we need r = min( q, s ). If q = r thenwe have p ≤ q = r ≤ s , and if r = s then we have p ≤ r = s ≤ q , and in either case the conditionreduces to the two “medians” among p, q, r, s are equal. (It is not difficult to see that this condition isalso 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 threenumbers and 4! / 2 = 12 ways to assign them (it must be a 1-2-1 split). If there are two distinct numbers 3
    ( )
    n +1
    then there are ways to choose the numbers and 4 + 4 = 8 ways to assign them (it must be a 3-1
    or a 1-3 split). If there is one distinct number then there are n + 1 ways to assign. Together we have 2
    ( ) ( )
    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 getthe overall probability to be
    41 25 5 41
    · · = .
    125 64 8 512