組合せ１０－８
658 名前：１３２人目の素数さん[] 投稿日：2005/11/23(水) 14:26:04 0と1からなるword(つまり有限の数列)A=(a1,...,ak), B=(b1,...,bl)に対してその結合ABをAB=(a1,...,ak,b1,...,bl) と定義する。さらにwordの無限列B(1)=A1,B(2)=A1A2,B(3)=A1A2A3,... に対してU_i B(i)を無限列 A1A2A3....として定義する。 wordの列 S(0),S(1),...,T(0),T(1),... を帰納的に次のように定義する。 (1) S(1)=0, T(0)=1, (2)S(i+1)=S(i)S(i)T(i), T(i+1)=S(i)T(i)T(i). このとき S(∞)=U_i S(i)とおく。 S(∞)=001 001 011 001 001 011 001 011 011 001 001 011 001 001 011 001 011 011 001 001 011 001 011 011 001 011 011 このときS(∞)の中にはCをwordとして、...CCC..という パターンは決して現れないと思われるがどうだろうか？ (いかにも正しそうだが証明できるのだろうか？)
659 名前：１３２人目の素数さん[] 投稿日：2005/11/23(水) 17:33:41 658です。 訂正 (1) S(1)=0, T(0)=1, でなく、 (1) S(0)=0, T(0)=1, でした。
解答
660 名前：１３２人目の素数さん[sage] 投稿日：2005/11/23(水) 18:45:25 それどっかで見たことあるな。 結果は肯定的だったと思うけど証明は思い出せない。
661 名前：１３２人目の素数さん[sage] 投稿日：2005/11/23(水) 20:13:43 >>658 S(∞) の最初の文字を 0文字目とする。 非負整数 n を３進法で表して、下の桁から見ていったときに、 2 よりも 0 が先に現れるなら、S(∞) の n文字目は 0、 0 よりも 2 が先に現れるなら、S(∞) の n文字目は 1。 よって、k を非負整数として、 n ≡ 0*3^k + (3^k-1)/2 (mod 3^(k+1)) のとき、S(∞) の n文字目は 0、 n ≡ 2*3^k + (3^k-1)/2 (mod 3^(k+1)) のとき、S(∞) の n文字目は 1。 m を非負整数として、m ≠ 0 (mod 3^k), m ≡ 0 (mod 3^(k-1)) とする。 n ≡ (3^k-1)/2 (mod 3^k) なら、 S(∞) 中の n, (n+m), (n+2m) 文字目、の３文字のうちひとつは 0 で、ひとつは 1。 よって、S(∞) に m 文字から成る語の３回以上の繰り返しは存在しない。
662 名前：１３２人目の素数さん[sage] 投稿日：2005/11/23(水) 21:30:00 それで証明できるけどｋが一つ違う。
670 名前：１３２人目の素数さん[] 投稿日：2005/11/24(木) 00:59:53 >>661 658です。たしかにmの条件でkがひとつずれていますが。 あと111...1タイプ は 0 になりますね。 しかしこれは美しい証明です！ありがとうございます！
