返回题库

HMMT 二月 2013 · COMB 赛 · 第 5 题

HMMT February 2013 — COMB Round — Problem 5

专题
Discrete Math / 离散数学
难度
L3
来源
HMMT

题目详情

  1. At a certain chocolate company, each bar is 1 unit long. To make the bars more interesting, the company 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 chosen uniformly at random between 0 and 1. Each of the two bars is cut p units from the left, and the pieces on the left are switched: each is grafted onto the opposite bar where the other piece of length p was previously attached. For example, the bars might look like this after the first step: p 0 1 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 same type of chocolate as that 2 / 3 units from the left?
解析
  1. At a certain chocolate company, each bar is 1 unit long. To make the bars more interesting, the company 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 chosen uniformly at random between 0 and 1. Each of the two bars is cut p units from the left, and the pieces on the left are switched: each is grafted onto the opposite bar where the other piece of length p was previously attached. For example, the bars might look like this after the first step: p 0 1 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 same type of chocolate as that 2 / 3 units from the left? [ ] ( ) 100 1 1 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 even i 1 2 number of p are in ( , ). Summing, this is equal to i 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 out between the two terms.