HMMT 十一月 2022 · 冲刺赛 · 第 34 题

HMMT November 2022 — Guts Round — Problem 34

[20] A random binary string of length 1000 is chosen. Let L be the expected length of its longest (contiguous) palindromic substring. Estimate L . E L 10 An estimate of E will receive ⌊ 20 min( , ) ⌋ points. L E 2

解析

[20] A random binary string of length 1000 is chosen. Let L be the expected length of its longest (contiguous) palindromic substring. Estimate L . E L 10 An estimate of E will receive ⌊ 20 min( , ) ⌋ points. L E Proposed by: Gabriel Wu Answer: L ≈ 23 . 120 Solution: The probability that there exists a palindromic substring of length 2 n + 1 is approximately − n 2 · 1000. Thus, we can expect to often see a length 21 palindrome, and sometimes longer ones. This leads to a guess a bit above 21. 7 L was approximated with 10 simulations (the answer is given with a standard deviation of about − 3 10 ). 2