A,B,C3種類の文字で無限列を作る

質問

将棋の千日手について考えていたところ、次のような問題を思いつきました。

A,B,C3種類の文字を一列に並べる方法を考えます。同じ文字は何度も使ってよいですが、同一パターンが続けて並ばないようにします。たとえば簡単な例でいうと、AAとかBBとかCCなどという文字の列は認めないし、ABAB、ABCABCのようにもなってはダメということです。

ABACABCABACABAC…

のような配列を考えるわけです。このような無限列は存在するか？という問題を考えています。たとえば、[ABAC]、[ABC]、[BAC]などいくつかの文字の塊を考えて、それを新たにひとつの文字と思いつなげて行く方法などを考えて見ましたが、この塊というのが曲者で、塊の途中から同じパターンが繰り替えされたりすることもあるので一筋縄ではいきません。

3種の文字で無限列を作ることは可能でしょうか？あるいは不可能なら、文字を増やせば可能でしょうか？

ちなみに将棋の千日手というのは、かつては同一手順を3回繰り返したら引き分けにする、というルールでした。しかしそれでは無限に続く手が存在するということから、現在は同一局面が4回出現したら引き分けにする、というルールに変っています。このルールにより将棋は必ず有限回で終了するゲームということになっています。ここで同一手順2回でも無限に続く可能性があるのか？ということを考えたくなって上の問題に行き着きました。下は千日手に関する記述のあるwebページです。
http://www.webspace-jp.com/~mozu/mozuiro/moromoro/senkou.html

回答No.10

corpus · ベストアンサー

＃９です。
＃９は間違っていました。
ABCACでは次にABCBACが来るとABCACABCBACでCACAが作られてしまいます。

そこで次のように改良しました。
初期値を適当に決める。
例えばabcab

(1)
a→A
b→B
c→C
このように大文字に変換する。

(2)
A→abacb
B→abcbac
C→abcacbc
このように大文字をなくし小文字のみにする。

(3)この(1)(2)を繰り返す。

以上

お礼

お礼大変遅くなりました。たびたび貴重なご回答を提供していただきとても感謝しています。ありがとうございました。補題2（あるいは同じことですが補題1）に相当することがどうして正しいのか少し不安になっていたのですが、正しく証明できるのですね。

回答No.9

corpus

#8です。

ABCACBをABCACにすればひょっとしたらよいかもしれません。

回答No.8

corpus

＃２です。
今回は＃６のeatern27さんのを参考にして３文字の場合を考えました。

規則は次のとおりです。

(A_1,B_1,C_1)=(a,b,c)
(A_(n+1) , B_(n+1) , C_(n+1))
=(A_nB_nA_nC_nB_nC_n , A_nB_nC_nA_nC_nB_n , A_nB_nC_nB_nA_nC_n)

です。

例えば、
(A_2,B_2,C_2)=(abacbc,abcacb,abcbac)
(A_3,B_3,C_3)=(abacbc|abcacb|abacbc|abcbac|abcacb|abcbac, abacbc|abcacb|abcbac|abacbc|abcbac|abcacb, abacbc|abcacb|abcbac|abcacb|abacbc|abcbac)です。

なお"|"とか","は見やすさのために便宜的に置いたものです。

このようにしていくと無限に行くと思います。

なぜABACBCとABCACBとABCBACにしたかというと、
Aからはじめるということ。
それ自身に繰り返しを含まないこと。（例えばABCABCは繰り返しています。）
それぞれの文字列の終わりとそれぞれの文字列の始まりが一致しないこと。（例えばABCACBとACBCBAはACBが前者の後半部と後者の前半部にある。）

書いている途中で気づきましたが、これはやっぱりダメです、。ABCACBとABACBCはABCACBABACBCという文字列を作ってしまいます。これはBABAというものが接続部に作られてしまいました。ショック！！この戦略ではダメなのでしょうか？あるいはBAを取り除いていくなど多少の処理をすれば済むのでしょうか？

回答No.7

graphaffine

圧縮方式はいろいろありますが、そのうちのLZ77圧縮方式の原理と大いに関連しそうな話ですね。
この方式では、前に出てきた文字列と同じものを符号化します。詳細は参考サイトを見てください。

参考URL：

http://star.endless.ne.jp/users/graph/part3/3no2.htm

お礼

お礼大変遅くなりました。ありがとうございます。

回答No.6

eatern27

3文字の場合は分かりませんが、４文字(以上)の場合なら,おそらく無限列を作れます。(勘違いの可能性が高いので、どなたか、間違いを見つけたら、ご指摘をお願いします)

※adinatさんは、大文字のA,B,Cを並べていますが、説明の都合上、小文字のa,b,c,dを並べます。

a,b,c,dの４つの文字から以下のルールで、４つの文字列の組(A_n,B_n,C_n,D_n)を作ります。

(A_1,B_1,C_1,D_1)=(a,b,c,d)
(A_(n+1),・・・,D_(n+1))=(A_nB_n , A_nC_n , A_nD_nB_nD_n , A_nD_nC_nD_n)　(n≧1)

例えば、(A_2,B_2,C_2,D_2)=(ab,ac,adbd,adcd)です。

このような文字列はいくらでも長く作ることができ、
そして、これらの文字列には、同一パターンは連続して並んでいません。(・・・と思います)

この後が、その証明(というより説明の概略？)です。

(A,B,C,D)=(A_2,B_2,C_2,D_2)=(ab,ac,adbd,adcd)とし,
「a,b,c,dを並べた文字列」のことを「小文字列」。「A,B,C,Dを並べた文字列」の事を「大文字列」と呼びます。
また、N(X)を大文字列Xの文字数、n(x)を小文字列xの文字数とします。

--------------------------------------------------

補題１
大文字列X_1,X_2を小文字列に直したもの(例:AC→abadbd,ABD→abacadcd)をx_1,x_2とします。(n(x_1)≦n(x_2)とする)
x_2の最初のn(x_1)文字からなる文字列をxとして、
x_1=xならば、X_2の最初のN(X_1)文字はX_1に一致する。
(回りくどい表現になってますが、「小文字列が一致すれば、元になっている大文字列も一致する」というイメージです。)

x_1,xの最初の文字はいずれもaです。
x_1,xの2番目の文字がbならX_1,X_2の最初の文字はAと決まります。
同様に2番目の文字がcならX_1,X_2の最初の文字はBと決まり、2番目の文字がdなら3文字目を見ることで、X_1,X_2の最初の文字が決まります。

これを繰り返せば、補題１が正しいと分かります。(厳密には帰納法？)

--------------------------------------------------

補題２
ある大文字列Xを小文字列xに直します。
もし、xの途中で同一パターンが並んでいれば、Xの途中でも同一パターンが並んでいる。

1)その同一パターンの最初の文字がaの場合。
(I)・・・(a？？？)(a？？？)・・・
後者の(a？？？)のaはA,B,C,Dのいずれかに由来します。

1-i)Aに由来する場合
(I)は、・・・(ab ？？？)(ab ？？？)・・・
のようになります。
abの並びはAにしか存在しなので、前者の(a？？？)のaもAに由来することになります。
したがって、もとの大文字列は
・・・A X_1 A X_2
のようになっている事になります。補題１からX_2の最初のN(X_1)文字はX_1に一致する事がわかるので、
従って、・・・A X_1 A X_1 ・・・
と表せることになり、A X_1というパターンが繰り返されます。

aがB,C,Dに由来する場合や、
同一パターンがb,c,dから始まる場合も同様に、大文字列のパターンが繰り返される事が分かります。(多分。必要なら補足を)

従って、補題２が成り立ちます。(成り立つはずです)

補題２の対偶は
「同一パターンがでないように大文字列を並べれば、小文字列にも同一パターンがない」のようになり、これと、A_n等の構成の仕方から、
A_n,B_n,C_n,D_nをa,b,c,dについての文字列に直したときに、同一パターンが存在しない事が分かります。(おそらく)

a,b,cの3文字から、同じように(A_n,B_n,C_n)という組の列が作れればよいのですが...

長文＆乱文ですいません。(日本語が下手なので、お許しをm(_ _)m)
分かりにくい表現があれば、補足を。。。

A,B,Cの3文字で、同じように(A_n,B_n,C_n)という組の列が作れればよいのですがねぇ...

お礼

お礼大変遅くなって本当に申し訳ございません。また大変貴重なご回答とても嬉しく思います。ありがとうございます。４文字はこの証明で大丈夫なようですね。

回答No.5

noname#178429

提示された条件で曖昧な点が一つあります.しかし結果は同じです.

作られた文字列の中に一度出た部分文字列が2度と発生しない.
という意味ですが,どこで区切るかということが問題になります.仮に,任意に区切ってということであれば,次のようになるものと考えられます.これが主旨にに近いのではないかと思います.
例えば,
　ABACBCという文字列が最初にあったとすれば,2個の文字列(2個列)ではAB,BA,AC,CB,BC,3個列では,ABA,BAC,ACB,
CBCが存在することになり,これ以降はこれらの2個あるいは3個の文字列は出てはならないことになります.
したがって,2個列について考えるとあと残っている文字列は,CA,これらを使って並べてもせいぜいあと1個(実際は隣り合わせの制約があるのでこれ以下)並べられる程度でたくさん並べられません.有限です.
もう一つの考え方は,2個文字列を考える場合は,最初から区切り,2個,3個文字列を考える.
例えば
　ABACBC
2個列の時
　AB,AC,BC,...
3個列の時
　ABA,CBC,.
この場合でも2個列で使える2個文字列はせいぜいあと9個ですからすぐ並べられなくなってしまいます.則ち有限です.
このほかに別の考え方があれば別の話になるかも知れませんが,もし上のいずれかの文字列の定義に従えば,有限ということになります.
文字を増やしても有限であることには,変わりありません.
余談になりますが,本題の条件をゆるめて,循環小数のような繰り返しを認めないというのであれば,無限にすることは可能になります.

お礼

ありがとうございます。もう少し数学的に厳密に言うと、文字列からどの連続する2n個の有限部分列を取り出しても、それらが同じn個の部分列の合併になっていない、という意味です。同じ文字の配列が続けて現れなければよいだけで、何回でも現れてもよいことにしています。もちろんおっしゃるように有限個の文字を並べているのだから、同じ配列は無限回出現しますね。

回答No.4

noname#30727

簡単なプログラムを書いて試してみました。41桁でAから始まるものだけで21万個以上ありました。
数学的な証明は出来ませんが、おそらく無限に続くのではないかと思います。

ABACABCACBABCABACABCACBAC（下に続く）
ABACBABCABACABCACBABCABAC（下に続く）
BABCACBACABACBABCABACABCA（下に続く）
CBABCBACABACBABCABACABCAC

お礼

プログラムまで書いて試してくださってありがとうございます。僕もいろいろ紙に書いて試してみたのですが、とても必ず有限列になるようには思えないんですよね。うまく証明できたらよいと思っています。

回答No.3

corpus

＃２です。さっきのは全部だめでした。

＞ABACABCABACABACABCABACBABCAB…
BACAが繰り返されていました。

お礼

どうもありがとうございます。なかなか手作業だと難しいですよね。てきとうに並べるとほぼ確実にどこかに繰り返しが出現してしまうんです。その意味では結構微妙な問題のような気もします。

回答No.2

corpus

ABCABACABCABA ←この後にABCのいずれが来てもダメ

ABACABA ←この後にABCのいずれが来てもダメ

ABACABCABACABACABCABACA ←この後にABCのいずれが来てもダメ

ABACABCABACABACABCABACBABCAB… ←これはわからない。

回答No.1

sire

とても面白い問題だと思います。

ご質問とはずれるのですが、
ABACABCABACABAC…に同一パターンがないということを確かめることは、簡単にできるのでしょうか。
ポストの対応問題や分割問題などはそう簡単にはできないようです(NPであってPではないよう)。
でも、今回はもっと簡単な問題ですから無限列は作れそうな、そうでないような。。
後続の方にバトンタッチ。

参考URL：

http://www.aist-nara.ac.jp/~yasumoto/lecture/tm/tm2005-7.pdf#search='ポストの対応問題'

お礼

同一パターンがないことを確かめるのは、僕にはしらみつぶしをするしか方法を思いつきません。そういう意味では、もし無限に続くのであれば今のところ証明をする方法がないということになります。何か別のアイデアがあればよいのですが。