「組合せ20051123142604」の編集履歴（バックアップ）一覧はこちら

「組合せ20051123142604」(2005/12/13 (火) 16:02:07) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

組合せ１０－８
> 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　になりますね。
> しかしこれは美しい証明です！ありがとうございます！