{"id":47,"date":"2017-04-01T03:10:04","date_gmt":"2017-03-31T19:10:04","guid":{"rendered":"http:\/\/colliot.me\/?p=47"},"modified":"2017-11-20T07:12:31","modified_gmt":"2017-11-19T23:12:31","slug":"a-simple-combinatorial-problem-and-related-thoughts","status":"publish","type":"post","link":"https:\/\/colliot.org\/en\/2017\/04\/a-simple-combinatorial-problem-and-related-thoughts\/","title":{"rendered":"A Simple Combinatorial Problem and Related Thoughts"},"content":{"rendered":"<p><b>Problem:<\/b> If the decimal expansion of <span class=\"wp-katex-eq\" data-display=\"false\">a<\/span> contains all <span class=\"wp-katex-eq\" data-display=\"false\">10<\/span> digits (<span class=\"wp-katex-eq\" data-display=\"false\">0,...,9<\/span>), then the number of length <span class=\"wp-katex-eq\" data-display=\"false\">n<\/span> strings (shorted as <span class=\"wp-katex-eq\" data-display=\"false\">n<\/span>-strings) is greater than <span class=\"wp-katex-eq\" data-display=\"false\">n+8<\/span>.<\/p>\n<p>If you&#8217;ve established the <span style=\"color: #274e13;\">simple<\/span> lemma, the solution is instant. Otherwise <span style=\"color: #351c75;\">very impossible<\/span>.<\/p>\n<p><b>Lemma:<\/b> The number <span class=\"wp-katex-eq\" data-display=\"false\">C_n<\/span> of <span class=\"wp-katex-eq\" data-display=\"false\">n<\/span>-strings is strictly greater than <span class=\"wp-katex-eq\" data-display=\"false\">C_{n-1}<\/span>, that of <span class=\"wp-katex-eq\" data-display=\"false\">n-1<\/span>-strings.<br \/>\nActually, \u00a0we always have <span class=\"wp-katex-eq\" data-display=\"false\">C_n \\ge C_{n-1}<\/span>: Every <span class=\"wp-katex-eq\" data-display=\"false\">n-1<\/span>-string corresponds to an <span class=\"wp-katex-eq\" data-display=\"false\">n<\/span>-string by <span style=\"color: #b45f06;\">continuing 1 more digit<\/span>. The map is clearly injective. If <span class=\"wp-katex-eq\" data-display=\"false\">C_n=C_{n-1}<\/span>, it is bijective, meaning we have a way to <span style=\"color: #a64d79;\">continue uniquely<\/span>, which means rationality. Rigidly, at least one of the <span class=\"wp-katex-eq\" data-display=\"false\">n-1<\/span>-strings occurs infinitely, but all digits after some <span class=\"wp-katex-eq\" data-display=\"false\">n-1<\/span>-string is totally determined by it. So if an <span class=\"wp-katex-eq\" data-display=\"false\">n-1<\/span>-string appears twice, it must appear every such distances, and so do the digits between.<!--more--><\/p>\n<p>(Further discussion: For a rational number, split it into a <span style=\"color: cyan;\">finite part<\/span>, and a <span style=\"color: orange;\">recurring part<\/span>. If the minimal length of recurring string is <span class=\"wp-katex-eq\" data-display=\"false\">n<\/span>, then any <span class=\"wp-katex-eq\" data-display=\"false\">m<\/span>-string starting in the recurring part has exactly <span class=\"wp-katex-eq\" data-display=\"false\">n<\/span> variations, if <span class=\"wp-katex-eq\" data-display=\"false\">m \\ge n<\/span>. Additional variations brought by the finite irregular part is finite (regardless of <span class=\"wp-katex-eq\" data-display=\"false\">m<\/span>), as the starting point is finite. So <span class=\"wp-katex-eq\" data-display=\"false\">C_n<\/span> in this case is <span style=\"color: red;\">not decreasing but bounded<\/span>. So it reaches some certain number and stays stable. In a purely recurring case, the number is exactly <span class=\"wp-katex-eq\" data-display=\"false\">n<\/span> (meaning afore-defined).<\/p>\n<p>Now <span class=\"wp-katex-eq\" data-display=\"false\">C_n \\ge C_{n-1}+1 \\ge ... \\ge 9+1<\/span>, as <span class=\"wp-katex-eq\" data-display=\"false\">10 &gt; 9=1+8<\/span> holds, the problem is solved.<\/p>\n<p>This may not be really hard. But the most important thing is to <span style=\"color: #134f5c;\">see the principle behind it<\/span>.<\/p>\n<p>(I \u00a0WILL FURTHER COMPLETE THIS POST.)<\/p>\n<p style=\"text-align: right;\">Saturday, August 10, 2013<\/p>\n<p><\/p>","protected":false},"excerpt":{"rendered":"<p>Sorry, this entry is only available in \u4e2d\u6587. For the sake of viewer convenience, the content is shown below in the alternative language. You may click the link to switch the active language.Problem: If the decimal expansion of contains all digits (), then the number of length strings (shorted as -strings) is greater than . &hellip; <a href=\"https:\/\/colliot.org\/en\/2017\/04\/a-simple-combinatorial-problem-and-related-thoughts\/\" class=\"more-link\">Continue reading<span class=\"screen-reader-text\"> &#8220;A Simple Combinatorial Problem and Related Thoughts&#8221;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[8],"tags":[],"_links":{"self":[{"href":"https:\/\/colliot.org\/en\/wp-json\/wp\/v2\/posts\/47"}],"collection":[{"href":"https:\/\/colliot.org\/en\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/colliot.org\/en\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/colliot.org\/en\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/colliot.org\/en\/wp-json\/wp\/v2\/comments?post=47"}],"version-history":[{"count":4,"href":"https:\/\/colliot.org\/en\/wp-json\/wp\/v2\/posts\/47\/revisions"}],"predecessor-version":[{"id":419,"href":"https:\/\/colliot.org\/en\/wp-json\/wp\/v2\/posts\/47\/revisions\/419"}],"wp:attachment":[{"href":"https:\/\/colliot.org\/en\/wp-json\/wp\/v2\/media?parent=47"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/colliot.org\/en\/wp-json\/wp\/v2\/categories?post=47"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/colliot.org\/en\/wp-json\/wp\/v2\/tags?post=47"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}