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

HMMT February 2012 — Guts Round — Problem 24

[ 13 ] Franklin has four bags, numbered 1 through 4. Initially, the first bag contains fifteen balls, numbered 1 through 15, and the other bags are empty. Franklin randomly pulls a pair of balls out of the first bag, throws away the ball with the lower number, and moves the ball with the higher number into the second bag. He does this until there is only one ball left in the first bag. He then repeats this process in the second and third bag until there is exactly one ball in each bag. What is the probability that ball 14 is in one of the bags at the end? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . TH 15 ANNUAL HARVARD-MIT MATHEMATICS TOURNAMENT, 11 FEBRUARY 2012 — GUTS ROUND

解析

[ 13 ] Franklin has four bags, numbered 1 through 4. Initially, the first bag contains fifteen balls, numbered 1 through 15, and the other bags are empty. Franklin randomly pulls a pair of balls out of the first bag, throws away the ball with the lower number, and moves the ball with the higher number into the second bag. He does this until there is only one ball left in the first bag. He then repeats this process in the second and third bag until there is exactly one ball in each bag. What is the probability that ball 14 is in one of the bags at the end? 2 Answer: Pretend there is a 16th ball numbered 16. This process is equivalent to randomly 3 drawing a tournament bracket for the 16 balls, and playing a tournament where the higher ranked ball always wins. The probability that a ball is left in a bag at the end is the probability that it loses to 1 1 ball 16. Of the three balls 14, 15, 16, there is a chance 14 plays 15 first, a chance 14 plays 16 3 3 1 first, and a chance 15 plays 16 first. In the first case, 14 does not lose to 16, and instead loses to 15; 3 2 otherwise 14 loses to 16, and ends up in a bag. So the answer is . 3 Guts