HMMT 十一月 2017 · 冲刺赛 · 第 23 题

HMMT November 2017 — Guts Round — Problem 23

[ 12 ] A string of digits is defined to be similar to another string of digits if it can be obtained by reversing some contiguous substring of the original string. For example, the strings 101 and 110 are similar, but the strings 3443 and 4334 are not. (Note that a string is always similar to itself.) Consider the string of digits S = 01234567890123456789012345678901234567890123456789 , consisting of the digits from 0 to 9 repeated five times. How many distinct strings are similar to S ?

解析

[ 12 ] A string of digits is defined to be similar to another string of digits if it can be obtained by reversing some contiguous substring of the original string. For example, the strings 101 and 110 are similar, but the strings 3443 and 4334 are not. (Note that a string is always similar to itself.) Consider the string of digits S = 01234567890123456789012345678901234567890123456789 , consisting of the digits from 0 to 9 repeated five times. How many distinct strings are similar to S ? Proposed by: Kevin Sun Answer: 1126 We first count the number of substrings that one could pick to reverse to yield a new substring. If we insert two dividers into the sequence of 50 digits, each arrangement of 2 dividers among the 52 total ( ) 52 objects specifies a substring that is contained between the two dividers, for a total of substrings. 2 Next, we account for overcounting. Every substring of length 0 or 1 will give the identity string when reversed, so we are overcounting here by 51 + 50 − 1 = 100 substrings. Next, for any longer substring s that starts and ends with the same digit, removing the digit from both ends results in a substring ′ ′ s , such that reversing s would give the same string as reversing s . Therefore, we are overcounting by ( ) ( ) ( ) 5 52 5 10 · substrings. Our total number of strings similar to S is therefore − 100 − 10 · = 1126 . 2 2 2