HMMT 十一月 2017 · 冲刺赛 · 第 2 题

(2) Every ball has been drawn at least once. What is the probability that condition (1) is met before condition (2)? If the correct answer is C and (⌊ ( )⌋ ) 1 your answer is A , you get max 30 1 − | log C − log A | , 0 points. 2 2 2 Proposed by: Yuan Yao Answer: 0 . 02236412255 . . . Below is a python implementation to compute the probability, using the same method as the solution to the easier version (with three balls). from fractions import Fraction N = 12 probs = [{} for i in range((N-1)(N-1)+2)] prob1 = Fraction() prob2 = Fraction() init = tuple(0 for i in range(N)) probs[0][init] = Fraction(1,1) for i in range((N-1)(N-1)+1): for t in probs[i]: for j in range(N): val = probs[i][t] * Fraction(1,N) l = list(t) l[j] += 1 l.sort() l = tuple(l) if (l[-1] == N): prob1 = prob1 + val elif (l[0] == 1): prob2 = prob2 + val else: probs[i+1][l] = probs[i+1].setdefault(l, Fraction()) + val print(prob1) Intuitively the probability should be quite small, since the distribution tends towards the second M condition instead of the first. Indeed, the exact fraction is p = , where N M =663659309086473387879121984765654681548533307869748367531 919050571107782711246694886954585701687513519369602069583 , N =2967517762021717138065641019865112420616209349876886946382 1672067789922444492392280614561539198623553884143178743808 . Note: This is a simplified variant of the Bingo Paradox, which is a phenomenon where horizontal bingos are significantly more frequent than vertical bingos. For more information, see https://www. maa.org/sites/default/files/pdf/Mathhorizons/pdfs/The_Bingo_Paradox_MH_Sept17.pdf .