HMMT 十一月 2019 · 冲刺赛 · 第 28 题
HMMT November 2019 — Guts Round — Problem 28
题目详情
英文原题
- [15] A palindrome is a string that does not change when its characters are written in reverse order. Let
S be a 40-digit string consisting only of 0’s and 1’s, chosen uniformly at random out of all such strings.
Let E be the expected number of nonempty contiguous substrings of S which are palindromes. Computethe value of b E c .
√
解析
英文解析
- [15] A palindrome is a string that does not change when its characters are written in reverse order.
Let S be a 40-digit string consisting only of 0’s and 1’s, chosen uniformly at random out of all suchstrings. Let E be the expected number of nonempty contiguous substrings of S which are palindromes.
Compute the value of b E c .
Proposed by: Benjamin Qi
Answer: 113
Note that S has 41 − n contiguous substrings of length n, so we see that the expected number of −b n/ 2 cpalindromic substrings of length n is just (41 − n ) · 2 . By linearity of expectation, E is just the sum of this over all n from 1 to 40 . However, it is much easier to just compute
∞
∑
−b n/ 2 c
(41 − n ) · 2 .
n =1
The only difference here is that we have added some insignificant negative terms in the cases wheren > 41 , so E is in fact slightly greater than this value (in fact, the difference between E and this sumis ). To make our infinite sum easier to compute, we can remove the floor function by pairing 7
1048576
up consecutive terms. Then our sum becomes
∞
∑
81 − 4 n
40 + ,
2 nn =1
which is just 40 + 81 − 8 = 113 . E is only slightly larger than this value, so our final answer isb E c = 113 .
√