• ベストアンサー

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

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

質問者が選んだベストアンサー

  • ベストアンサー
  • eatern27
  • ベストアンサー率55% (635/1135)
回答No.4

>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のどれを選んでも、繰り返しができてしまうわけですよね。この手前にCを置いたって、繰り返しができてしまう事は変わりませんよね。 問題となるとしたら、Cを置いたことによって、途中で繰り返しができてしまう事です。例えば、Bを置いたことにすれば、例2の方では、 BABCAC BABCAC のように繰り返しができてしまうので、この方法では後手が負けます。(後手が別の手を選べば勝つ余地があるのかもしれませんが確かめていません) でも、Cであればそのような事はありませんね。

corpus
質問者

お礼

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

その他の回答 (4)

  • eatern27
  • ベストアンサー率55% (635/1135)
回答No.5

C AB/C ACのどっちにするかは後手が決める事ですよね。 C ABを選べば後手が勝てるのですから、後手必勝です。 C ACを選んだ場合に、先手が勝つかどうかは関係ありません。

corpus
質問者

お礼

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

  • fjfsgh
  • ベストアンサー率16% (5/30)
回答No.3

もともとの問題、 A,B,C3種類の文字で連続する繰り返しのない無限列を作る は解決したのでしょうか? 組合せで考えるのはいかがでしょう。 項が2つの列は3^2=9通り。 1項目と2項目が同じなのは、3*1=3通り。 連続する繰り返しのない列は、9-3=6通り。 項が3つの列は3^3=27通り。 1項目と2項目が同じ(3項目は何でも良い)なのは、3*1*3=9通り。 2項目と3項目が同じ(1項目は何でも良い)なのは、3*3*1=9通り。 1項目と2項目と3項目が同じなのは、3*1*1=3通り。 連続する繰り返しのない列は、27-(9+9-3)=12通り。 ・・・・・・

corpus
質問者

補足

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

  • eatern27
  • ベストアンサー率55% (635/1135)
回答No.2

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

corpus
質問者

お礼

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

  • eatern27
  • ベストアンサー率55% (635/1135)
回答No.1

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

corpus
質問者

補足

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