PUMaC 2023 · 组合（B 组） · 第 8 题
PUMaC 2023 — Combinatorics (Division B) — Problem 8
题目详情
- For a positive integer n , let P be the set of sequences of 2 n elements, each 0 or 1, where n there are exactly n 1’s and n 0’s. I choose a sequence uniformly at random from P . Then, I n partition this sequence into maximal blocks of consecutive 0’s and 1’s. Define f ( n ) to be the expected value of the sum of squares of the block lengths of this uniformly random sequence. What is the largest integer value that f ( n ) can take on? 1 Name: Team: Write answers in table below: Q1 Q2 Q3 Q4 Q5 Q6 Q7 Q8 2
解析
- For a positive integer n , let P be the set of sequences of 2 n elements, each 0 or 1, where n there are exactly n 1’s and n 0’s. I choose a sequence uniformly at random from P . Then, I n partition this sequence into maximal blocks of consecutive 0’s and 1’s. Define f ( n ) to be the expected value of the sum of squares of the block lengths of this uniformly random sequence. What is the largest integer value that f ( n ) can take on? Proposed by Kevin Ren Answer: 121 P a It’s easier to compute the expected value of , where the a ’s are the block lengths. Note 2 that hX i X a a 2 E a = E 2 + a = 2 E + 2 n, 2 2 P n ( n − 1) a since the sum of block lengths is clearly 2 n . Hence, it suffices to show E = 2 · . 2 n +2 P a Note that equals the number of pairs of indices ( i, j ) such that ( i, j ) belong to the same 2 block. We take advantage of this by instead computing the expectation that ( i, j ) belong to the same block, and sum over ( i, j ) (this amounts to a change of summation). The probability 2 n −| j − i +1 | 2 n that ( i, j ) belong to the same block is 2 · / . And then by various binomial n n identities, 2 n 2 n X X X 2 n − | j − i + 1 | 2 n − k 2 n − k + 1 2 · = 2(2 n − k + 1) = 2( n + 1) n n n + 1 i<j k =2 k =2 2 n = 2( n + 1) . n + 2 P n ( n − 1) a 2 n 2 n Finally, E = 2( n + 1) / = 2 · , as desired. This gives the actual desired 2 n +2 n n +2 2 6( n − 2)( n +2) 6 n 24 expected value as . In order for this to be an integer, note that it equals + , n +2 n +2 n +2 which is an integer precisely when n + 2 | 24. It is evidently maximized for n = 22, giving an 2 6 · 22 answer of = 121. 24 4