- 336 名前：308 [02/02/02 03:40]
- >>325
ただ、今のところまだできるともできないとも
言ってない（わかってない）ので．．．
簡単に「できない」とは言えないって言っただけで。（苦笑）
難しい問題だってことだけは、いやというほどわかった。
>>331
２種類じゃ無限に続けられないことは証明できる．．．のだけど、
一部その証明に感覚的には納得しづらいところがある。
（「無限に続けられる」という言葉の解釈の問題。）
最初がababの場合で考えると、２個目以降の単語は必ず
a...a, b...b, a...ab...b, b...ba...a, a...ab...ba...a, b...ba...ab...b, b...ba...ab...ba...a
の７種のどれかになるが、
a...a, b...bのパターンが、それぞれ有限回しか出現しえないのは明らか。
（１回出てきたら、あとは長さを短くしていくしかないもんね。）
で、他のパターンについてなんだけど
例えばb...ba...ab...ba...a（以降パターンＡと呼ぶ）で考えると、
パターンＡ中の同じ文字でできた４つのブロックそれぞれの文字数を
左から順にn(1),n(2),n(3),n(4)とすると、
最初に出現するパターンＡについて、n(k)＝n_0(k)（k＝1〜4）
だったとすると、以降出現するパターンＡは
n(1)＜n_0(1)またはn(2)＜n_0(2)またはn(3)＜n_0(3)またはn(4)＜n_0(4)
でないといけない。
このうち、n(1)がn_0(1)より小さいある値NであるようなパターンＡが
有限個数しか存在しえないことが言えれば、n(1)＜n_0(1)の任意の値
であるようなパターンＡも有限個数しかないことが言え、
n(k)（k＝1〜4）について同様の議論を繰り返すことにより、
パターンＡ全体が有限個数になる。
で、「n(1)がn_0(1)より小さいある値NであるようなパターンＡが
有限個数しか存在しえないこと」の証明だが、
n(1)＝NであるようなパターンＡ（以降パターンＡ_Nと呼ぶ）
が最初に出現したとき、n(k)＝N_0(k)（k＝2〜4）だったとすると、
以降出現するパターンＡ_Nは
n(2)＜N_0(2)またはn(3)＜N_0(3)またはn(4)＜N_0(4)
でないといけない。
このうち、n(2)がN_0(2)より小さいある値NであるようなパターンＡ_Nが
有限個数しか存在しえないことが言えれば、n(2)＜N_0(2)の任意の値
であるようなパターンＡ_Nも有限個数しかないことが言え、
n(k)（k＝2〜4）について同様の議論を繰り返すことにより、
パターンＡ_N全体が有限個数になる。
・・・
賢明な読者の方ならこのあとの流れはわかると思うので、ここでやめておくが、
「最初がababの場合」についてはこの調子で証明は書き下せるし、
一般の場合については、最初の単語がどんなものであっても、
２単語目以降は、同じ文字の並びを１ブロックとした時のブロック数が
必ずある数以下になることから、その可能なブロックの並びそれぞれに
ついて出現する数が有限であることが、あらゆるパターンについて
言えることを数学的帰納法で証明すればよい。
|
 |
