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

HMMT February 2010 — Guts Round — Problem 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

解析

[ 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 random 6 variables converges to a Gaussian distribution, in this case with a mean of 1000 and a variance of √ 2 3000 · = 667. Since 667 ≈ 26, 1026 is a good guess, as Gaussians tend to differ from their mean by 9 approximately their variance. 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]) 6 See http://en.wikipedia.org/wiki/Central_limit_theorem . Guts Round maxes = [0]*3001 M = 1075 for a in range(0,3001): for b in range(0,3001-a): c = 3000-a-b m = 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],a if maxes[best] <= maxes[a]: best = a print maxes[best] print best 7 We can use arguments involving the Chernoff bound to show that the answer is necessarily less than
Alternately, if we wanted to be really careful, we could just set M = 3001, but then we’d have to wait a while for the script to finish.