返回题库

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

HMMT November 2017 — Guts Round — Problem 23

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

题目详情

英文原题

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

英文解析

  1. [ 12 ] A string of digits is defined to be similar to another string of digits if it can be obtained byreversing some contiguous substring of the original string. For example, the strings 101 and 110 aresimilar, but the strings 3443 and 4334 are not. (Note that a string is always similar to itself.) Considerthe 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 weinsert two dividers into the sequence of 50 digits, each arrangement of 2 dividers among the 52 total
    ( )
    objects specifies a substring that is contained between the two dividers, for a total of substrings.52
    Next, we account for overcounting. Every substring of length 0 or 1 will give the identity string when 2
    reversed, so we are overcounting here by 51 + 50 − 1 = 100 substrings. Next, for any longer substrings 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