A Simple Combinatorial Problem and Related Thoughts

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