CombinatoricsDifficulty 5.7AIME, harderProve itUnited States
Problem:
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?
Solution
Solution:
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 objects specifies a substring that is contained between the two dividers, for a total of (252) substrings. 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 10⋅(25) substrings. Our total number of strings similar to S is therefore (252)−100−10⋅(25)=1126.
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.
Source: MathNet,
licensed CC-BY-4.0.
Statement reproduced verbatim; metadata (topic, difficulty) added by this project.