PUMaC 2017 · 组合（A 组） · 第 8 题
PUMaC 2017 — Combinatorics (Division A) — Problem 8
题目详情
- Bob chooses a 4-digit binary string uniformly at random, and examines an infinite sequence of uniformly and independently random binary bits. If N is the least number of bits Bob has to examine in order to find his chosen string, then find the expected value of N . For example, if Bob’s string is 0000 and the stream of bits begins 101000001 . . . , then N = 7. 1
解析
- Let Bob’s chosen string be s , and let the infinite sequence of bits be S . Let A be the set of finite binary strings that do not contain s , and let A ( z ) be the corresponding generating n function, meaning the coefficient of z in A ( z ) is the number of elements of A with length n . Similarly, let B be the set of finite binary strings whose first occurrence of s is at the very end, and let B ( z ) be the corresponding generating function. Note that A and B are disjoint. n The coefficient of z in A ( z/ 2) is the probability that the first n bits of S do not contain s . Therefore, if p is the probability that the first n − 1 bits of S do not contain s , but the first n n n do, then the coefficient of z in A ( z/ 2) is ∞ ∑ p , k k = n +1 3 and the desired expected value is ∞ ∞ ∞ ∑ ∑ ∑ np = p = A (1 / 2) . n k n =0 n =0 k = n +1 Given sets X and Y of finite strings, let X × Y be the set of strings formed by appending a string in Y to the end of a string in X . Then, if ∅ denotes the empty string, then we have A t B = {∅} t ( A × { 0 } ) t ( A × { 1 } ) . Therefore, A ( z ) + B ( z ) = 1 + 2 zA ( z ) , so B (1 / 2) = 1. On the other hand, the structure of A × { s } depends on the structure of s . For each k ∈ { 0 , 1 , 2 , 3 } , let s denote the first k digits of s (so, in particular, s = ∅ ). We have the following k 0 four cases: Case 1: s ∈ { 0000 , 1111 } We have the decomposition A × { s } = ( B × { s } ) t ( B × { s } ) t ( B × { s } ) t ( B × { s } ), so 0 1 2 3 4 2 3 z A ( z ) = (1 + z + z + z ) B ( z ) , so A (1 / 2) = 30. Case 2: s ∈ { 0001 , 0011 , 0111 , 1000 , 1100 , 1110 } We have the decomposition A × { s } = B × { s } , so 0 4 z A ( z ) = B ( z ) , so A (1 / 2) = 16. Case 3: s ∈ { 0010 , 0100 , 0110 , 1001 , 1011 , 1101 } We have the decomposition A × { s } = ( B × { s } ) t ( B × { s } ), so 0 3 4 3 z A ( z ) = (1 + z ) B ( z ) , so A (1 / 2) = 18. Case 4: s ∈ { 0101 , 1010 } We have the decomposition A × { s } = ( B × { s } ) t ( B × { s } ), so 0 2 4 2 z A ( z ) = (1 + z ) B ( z ) , so A (1 / 2) = 20. 1 3 3 1 These cases appear with probabilities , , , and , respectively, so the expected value of 8 8 8 8 A (1 / 2), and therefore the expected value of the length of the longest sequence of bits of S , 30+3 · 16+3 · 18+20 starting at the beginning, that does not contain s , is = 19 . 8 Problem written by Matt Tyler If you believe that any of these answers is incorrect, or that a problem had multiple reasonable interpretations or was incorrectly stated, you may appeal at http://tinyurl.com/PUMaCappeal2017. All appeals must be in by 1 PM to be considered. 4