返回题库

HMMT 十一月 2019 · 冲刺赛 · 第 28 题

HMMT November 2019 — Guts Round — Problem 28

专题
Contest Math / 竞赛数学
难度
L3
来源
HMMT

题目详情

英文原题

  1. [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 .
    √
解析

英文解析

  1. [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 .
    √