## November 2007 solution

The answer is that there are 5852800 7-digit strings that can be represented as the concatenation of n<5 odd-length palindromes by changing at most one of their digits, and that a calculation that reaches this number is 107-1029283. (This is much shorter than the required maximum of 25 characters.)

The riddle requires a concatenation of n<5 odd-length palindromes to result in an odd-length (seven digit) figure. As only an odd number n of odd-length strings can sum to an odd-length string, n should be either 1 or 3. The option n=1 can safely be ignored, as any 7-digit palindrome can equally be considered as the concatenation of three palindromes, the first and last being identical 1-digit palindromes. Therefore, let us only consider the case n=3. Here are possible patterns that create such palindrome concatenation schemes:

A ? A B ? B ?

C A ? A C ? ?

? C A ? A C ?

? ? C A ? A C

? B ? B A ? A

Here, each question mark can be replaced by any digit (possibly a different digit for each question mark), whereas each letter must be consistently replaced with the same digit every time (though two different letters or a letter and a question mark can represent the same digit).

Notably, as we required three odd-length palindromes to sum up to a 7-digit string, three digits must compose the non-repeating middle-digits of the three palindromes, leaving four digits in two pairs. Because we can change one digit, we can create one pair, meaning that in order for a string to have the potential to become representable in the required format, it must already have a pair of equal digits that can become part of an odd-length palindrome, meaning a pair of equal digits separated by an even-length distance. In particular, we are interested in pairs that are 2-digits and 4-digits apart. A pair that is six digits apart (meaning that the first and last digits of our original string are equal) is not usable, because it can only contribute to a 7-digit palindrome, not to a palindrome that is one of a triplet that, together, forms a 7-digit string.

What the table of patterns above shows is that any digit that repeats itself two or four digits apart can be used as part of a valid pattern. If it is two digits apart, it can be used as the "A" digit in one of the patterns. If it is four digits apart, it can be used as the "C".

We must therefore count how many 7-digit strings have such repeating digits. This, however, is difficult to do directly. Instead, we'll calculate how many do not have such repeating digits, and subtract this from the total number of strings (107, there being seven places, each of which can be filled by one of 10 different digits).

In order to count the number of strings lacking such repeating digits, let us try to populate the string from left to right. The first two digits have no constraint on them (hence, 102 possibilities). The next two digits must not repeat the digit that was two positions before them (hence only 92 possibilities for these). Finally, the last three positions must neither repeat the digit two places before them nor the digit four places before them. As these two places must have different digits (or else they, themselves, form an unallowed pair), this leaves 8 possibilities for each of the remaining three digits (so, 83 possibilities).

Putting all together, we reach the aforementioned computation: 107-1029283.