Problem: If the decimal expansion of a contains all 10 digits (0,...,9), then the number of length n strings (shorted as n-strings) is greater than n+8.

If you’ve established the simple lemma, the solution is instant. Otherwise very impossible.

Lemma: The number C_n of n-strings is strictly greater than C_{n-1}, that of n-1-strings.
Actually,  we always have C_n \ge C_{n-1}: Every n-1-string corresponds to an n-string by continuing 1 more digit. The map is clearly injective. If C_n=C_{n-1}, it is bijective, meaning we have a way to continue uniquely, which means rationality. Rigidly, at least one of the n-1-strings occurs infinitely, but all digits after some n-1-string is totally determined by it. So if an n-1-string appears twice, it must appear every such distances, and so do the digits between.

(Further discussion: For a rational number, split it into a finite part, and a recurring part. If the minimal length of recurring string is n, then any m-string starting in the recurring part has exactly n variations, if m \ge n. Additional variations brought by the finite irregular part is finite (regardless of m), as the starting point is finite. So C_n in this case is not decreasing but bounded. So it reaches some certain number and stays stable. In a purely recurring case, the number is exactly n (meaning afore-defined).

Now C_n \ge C_{n-1}+1 \ge ... \ge 9+1, as 10 > 9=1+8 holds, the problem is solved.

This may not be really hard. But the most important thing is to see the principle behind it.

(I  WILL FURTHER COMPLETE THIS POST.)

Saturday, August 10, 2013