HMMT 二月 2010 · 冲刺赛 · 第 34 题

英文解析

34. [ 25 ] 3000 people each go into one of three rooms randomly. What is the most likely value for the maximum number of people in any of the rooms? Your score for this problem will be 0 if you write
    | A − C |
    down a number less than or equal to 1000. Otherwise, it will be 25 − 27 .
    min( A,C ) − 1000
    Answer: 1019 To get a rough approximation, we can use the fact that a sum of identical randomvariables converges to a Gaussian distribution, in this case with a mean of 1000 and a variance of 6
    √
    3000 · = 667. Since 667 ≈ 26, 1026 is a good guess, as Gaussians tend to differ from their mean by 2
    approximately their variance.9
    The actual answer was computed with the following python program:
    facts = [0]3001
    facts[0]=1
    for a in range(1,3001):
    facts[a]=afacts[a-1]
    def binom(n,k):
    return facts[n]/(facts[k]*facts[n-k])
    See http://en.wikipedia.org/wiki/Central_limit_theorem .6
    Guts Roundmaxes = [0]*3001
    M = 1075
    for a in range(0,3001):
    for b in range(0,3001-a):
    c = 3000-a-bm = max(a,max(b,c))
    if m < M:
    maxes[m] += facts[3000]/(facts[a]*facts[b]*facts[c])
    print [a,b]
    best = 1000
    for a in range(1000,1050):
    print maxes[a],aif maxes[best] <= maxes[a]:
    best = aprint maxes[best]
    print best
    We can use arguments involving the Chernoff bound to show that the answer is necessarily less than 7
35. Alternately, if we wanted to be really careful, we could just set M = 3001, but then we’d haveto wait a while for the script to finish.