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. Compute the 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 such strings. 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 c palindromic 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 where n > 41 , so E is in fact slightly greater than this value (in fact, the difference between E and this sum 7 is ). To make our infinite sum easier to compute, we can remove the floor function by pairing 1048576 up consecutive terms. Then our sum becomes ∞ ∑ 81 − 4 n 40 + , n 2 n =1 which is just 40 + 81 − 8 = 113 . E is only slightly larger than this value, so our final answer is b E c = 113 . √