面白い問題おしえて~な@数学板 組合せ20051123142604

※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

組合せ10-8
658 名前:132人目の素数さん[] 投稿日: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 名前:132人目の素数さん[] 投稿日:2005/11/23(水) 17:33:41
658です。
訂正
(1) S(1)=0, T(0)=1,
でなく、
(1) S(0)=0, T(0)=1,
でした。

解答
660 名前:132人目の素数さん[sage] 投稿日:2005/11/23(水) 18:45:25
それどっかで見たことあるな。
結果は肯定的だったと思うけど証明は思い出せない。

661 名前:132人目の素数さん[sage] 投稿日:2005/11/23(水) 20:13:43
>>658
S(∞) の最初の文字を 0文字目とする。

非負整数 n を3進法で表して、下の桁から見ていったときに、
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) 文字目、の3文字のうちひとつは 0 で、ひとつは 1。
よって、S(∞) に m 文字から成る語の3回以上の繰り返しは存在しない。

662 名前:132人目の素数さん[sage] 投稿日:2005/11/23(水) 21:30:00
それで証明できるけどkが一つ違う。

670 名前:132人目の素数さん[] 投稿日:2005/11/24(木) 00:59:53
>>661
658です。たしかにmの条件でkがひとつずれていますが。
あと111...1タイプ は 0 になりますね。
しかしこれは美しい証明です!ありがとうございます!