一个简单的组合问题及相关的思考

Like
Like Love Haha Wow Sad Angry

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

Like
Like Love Haha Wow Sad Angry

发表评论

邮箱地址不会被公开。 必填项已用*标注

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax