HMMT 二月 2013 · COMB 赛 · 第 5 题

英文解析

5. At a certain chocolate company, each bar is 1 unit long. To make the bars more interesting, thecompany has decided to combine dark and white chocolate pieces. The process starts with two bars,
   one completely dark and one completely white. At each step of the process, a new number p is chosenuniformly at random between 0 and 1. Each of the two bars is cut p units from the left, and the pieceson the left are switched: each is grafted onto the opposite bar where the other piece of length p waspreviously attached. For example, the bars might look like this after the first step:
   0 1 p
   Combinatorics Test
   Each step after the first operates on the bars resulting from the previous step. After a total of
   100 steps, what is the probability that on each bar, the chocolate 1 / 3 units from the left is the sametype of chocolate as that 2 / 3 units from the left?
   [ ]
   ( )
   1 1100
   Answer: + 1 If the values of p chosen are p , . . . , p , then note that the color of a
   1 100
   2 3
   bar changes at each value of p . Consequently, we want to find the probability that exactly an eveni
   1 2
   number of p are in ( , ). Summing, this is equal toi
   3 3
   ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )
   0 100 2 98 100 0
   100 1 2 100 1 2 100 1 2 + + . . . .
   0 3 3 2 3 3 100 3 3
   To compute, we note that this is equal to
   [ ]
   ( ) ( )
   100 100
   1 2 1 2 1 + + −
   2 3 3 3 3
   after expanding using the binomial theorem, since any terms with odd exponents are cancelled outbetween the two terms.