Maths Olympiad Prep

Library / /705 of 740

Combinatorics Difficulty 5.7 AIME, harder Prove it United 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 101101 and 110110 are similar, but the strings 34433443 and 43344334 are not. (Note that a string is always similar to itself.) Consider the string of digits
S=01234567890123456789012345678901234567890123456789 S=01234567890123456789012345678901234567890123456789
consisting of the digits from 00 to 99 repeated five times. How many distinct strings are similar to SS?

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 5050 digits, each arrangement of 22 dividers among the 5252 total objects specifies a substring that is contained between the two dividers, for a total of (522)\binom{52}{2} substrings. Next, we account for overcounting. Every substring of length 00 or 11 will give the identity string when reversed, so we are overcounting here by 51+501=10051+50-1=100 substrings. Next, for any longer substring ss that starts and ends with the same digit, removing the digit from both ends results in a substring ss', such that reversing ss would give the same string as reversing ss'. Therefore, we are overcounting by 10(52)10 \cdot \binom{5}{2} substrings. Our total number of strings similar to SS is therefore (522)10010(52)=1126\binom{52}{2}-100-10 \cdot \binom{5}{2}=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.