A,B,C３種類の文字で無限列を作るゲーム

質問

下記のURLはadinatさんが過去に質問してくれた問題です。
http://oshiete1.goo.ne.jp/qa1715716.html
結論としてはある指定された任意の有限列を作ることができると言うことだったと思います。無限に長く作ることができると言ってもいいと思います。
私はこれを先手後手のようなゲームでやって勝負がつくかどうかを考えました。
文字の種類はやはり３文字A,B,Cで、
先手が１文字、後手も１文字のときは先手が必勝する。
例 A B A C A B A
先手が２文字、後手が１文字のときは先手が必勝する。
例1 AB A CA B CB A CA B CB
例2 AB C AC B AB C AC
というところまではわかりましたが、
先手が１文字、後手が２文字のときはどちらが勝つかわかりません。
可能性としては、先手が必勝するか後手が必勝するか勝負がつかないか三つのうちのどれかだと思うのですが、私には見当がつきません。勝負がつかないとしたら、その証明はとても難しくなることだけは感じています。

回答No.4

eatern27 · ベストアンサー

>C AB A CA B CB A CA B CB　や
>C AB C AC B AB C AC　が
>隣接して繰り返しているようには思えません。

いやいや、
>例1 AB A CA B CB A CA B CB
>例2 AB C AC B AB C AC
この次にA,B,Cのどれを選んでも、繰り返しができてしまうわけですよね。この手前にＣを置いたって、繰り返しができてしまう事は変わりませんよね。

問題となるとしたら、Ｃを置いたことによって、途中で繰り返しができてしまう事です。例えば、Ｂを置いたことにすれば、例２の方では、
BABCAC BABCAC
のように繰り返しができてしまうので、この方法では後手が負けます。(後手が別の手を選べば勝つ余地があるのかもしれませんが確かめていません)
でも、Ｃであればそのような事はありませんね。

お礼

なんだか、後手必勝は確実のように思えてきました。あまりにも単純だったので、理解しにくかったのかもしれません。
ただ、C ABと始まったら後手必勝になるだけで、もし、C ACで始まったら、どうなるかということも考えなくてはならないことにも気づきました。ひょっとしたら、先手必勝の可能性も残っているかもしれません。

回答No.5

eatern27

C AB/C ACのどっちにするかは後手が決める事ですよね。
C ABを選べば後手が勝てるのですから、後手必勝です。

C ACを選んだ場合に、先手が勝つかどうかは関係ありません。

お礼

そうでした。そうでした。昨日、寝ているときに気がつきました。後手に決定権があるのですよね。そして、先手が最初にCではなくAと置けば後手はBCというように置けばいいのですよね。
本当に今までおつきあいいただきありがとうございました。

回答No.3

fjfsgh

もともとの問題、
A,B,C3種類の文字で連続する繰り返しのない無限列を作る
は解決したのでしょうか?

組合せで考えるのはいかがでしょう。

項が２つの列は3^2=9通り。
１項目と２項目が同じなのは、3*1=3通り。
連続する繰り返しのない列は、9-3=6通り。

項が３つの列は3^3=27通り。
１項目と２項目が同じ（３項目は何でも良い）なのは、3*1*3=9通り。
2項目と3項目が同じ（1項目は何でも良い）なのは、3*3*1=9通り。
１項目と２項目と３項目が同じなのは、3*1*1=3通り。
連続する繰り返しのない列は、27-（9+9-3）=12通り。

・・・・・・

補足

もともとの問題は解けたと思っています。ただし、前から順番に文字を決めていくことはできていません。
組み合わせで考えていくというのは一つのやり方だと思います。ただし、上手に文字を並べていけば、無限列を作ることはわかっています。
ここで、問題としたいのは、先手と後手がそれぞれ自分が有利になるように最善の手をとってゲームをしたときに、それでも、無限列ができてしまうのか、それとも、どちらかが打つべき手がなくなってしまう事態が起こるのか、ということです。

回答No.2

eatern27

とりあえず、
>例1 AB A CA B CB A CA B CB
>例2 AB C AC B AB C AC
こいつの前に、Cを付け加えてやれば、後手の必勝パターンになりますね。

お礼

私の考えていなかったアイデアでした。
ただ、例１や例２の前にCをつけた
C AB A CA B CB A CA B CB　や
C AB C AC B AB C AC　が
隣接して繰り返しているようには思えません。
このゲームを続けていくと、後手の必勝になるということでしょうか。

回答No.1

eatern27

ルールが全く分からないのですが・・・。
特に、何をどうやったら勝つのでしょうか？

補足

確かに、説明不足でした。
繰り返しを作ったほうが負けというルールだと考えてください。
簡単な例でいうとaaは"a"をababは"ab"を隣接して繰り返しています。
ですから、勝つためには、相手がどの文字を置いても、相手が繰り返しを作ってしまうようにすればいいということになります。
ABACABAという文字列に対して、Aと置けば"A"が隣接して繰り返され、Bと置けば"AB"が隣接して繰り返され、Cと置けば"ABAC"が隣接して繰り返されるので、この場合、後手が負けとなります。よって先手が勝ちということになります。
先手も後手もそれ以前に置かれた文字列を見て、どの文字を置くかを判断することになります。