将棋の千日手について考えていたところ、次のような問題を思いつきました。
A,B,C3種類の文字を一列に並べる方法を考えます。同じ文字は何度も使ってよいですが、同一パターンが続けて並ばないようにします。たとえば簡単な例でいうと、AAとかBBとかCCなどという文字の列は認めないし、ABAB、ABCABCのようにもなってはダメということです。
ABACABCABACABAC…
のような配列を考えるわけです。このような無限列は存在するか?という問題を考えています。たとえば、[ABAC]、[ABC]、[BAC]などいくつかの文字の塊を考えて、それを新たにひとつの文字と思いつなげて行く方法などを考えて見ましたが、この塊というのが曲者で、塊の途中から同じパターンが繰り替えされたりすることもあるので一筋縄ではいきません。
3種の文字で無限列を作ることは可能でしょうか?あるいは不可能なら、文字を増やせば可能でしょうか?
ちなみに将棋の千日手というのは、かつては同一手順を3回繰り返したら引き分けにする、というルールでした。しかしそれでは無限に続く手が存在するということから、現在は同一局面が4回出現したら引き分けにする、というルールに変っています。このルールにより将棋は必ず有限回で終了するゲームということになっています。ここで同一手順2回でも無限に続く可能性があるのか?ということを考えたくなって上の問題に行き着きました。下は千日手に関する記述のあるwebページです。
http://www.webspace-jp.com/~mozu/mozuiro/moromor …
No.10ベストアンサー
- 回答日時:
#9です。
#9は間違っていました。
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.8
- 回答日時:
#2です。
今回は#6のeatern27さんのを参考にして3文字の場合を考えました。
規則は次のとおりです。
(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
- 回答日時:
圧縮方式はいろいろありますが、そのうちのLZ77圧縮方式の原理と大いに関連しそうな話ですね。
この方式では、前に出てきた文字列と同じものを符号化します。詳細は参考サイトを見てください。
参考URL:http://star.endless.ne.jp/users/graph/part3/3no2 …
No.6
- 回答日時:
3文字の場合は分かりませんが、4文字(以上)の場合なら,おそらく無限列を作れます。
(勘違いの可能性が高いので、どなたか、間違いを見つけたら、ご指摘をお願いします)※adinatさんは、大文字のA,B,Cを並べていますが、説明の都合上、小文字のa,b,c,dを並べます。
a,b,c,dの4つの文字から以下のルールで、4つの文字列の組(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の文字数とします。
--------------------------------------------------
補題1
大文字列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の最初の文字が決まります。
これを繰り返せば、補題1が正しいと分かります。(厳密には帰納法?)
--------------------------------------------------
補題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
のようになっている事になります。補題1からX_2の最初のN(X_1)文字はX_1に一致する事がわかるので、
従って、・・・A X_1 A X_1 ・・・
と表せることになり、A X_1というパターンが繰り返されます。
aがB,C,Dに由来する場合や、
同一パターンがb,c,dから始まる場合も同様に、大文字列のパターンが繰り返される事が分かります。(多分。必要なら補足を)
従って、補題2が成り立ちます。(成り立つはずです)
補題2の対偶は
「同一パターンがでないように大文字列を並べれば、小文字列にも同一パターンがない」のようになり、これと、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)という組の列が作れればよいのですがねぇ...
お礼大変遅くなって本当に申し訳ございません。また大変貴重なご回答とても嬉しく思います。ありがとうございます。4文字はこの証明で大丈夫なようですね。
No.5
- 回答日時:
提示された条件で曖昧な点が一つあります.しかし結果は同じです.
作られた文字列の中に一度出た部分文字列が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
- 回答日時:
簡単なプログラムを書いて試してみました。
41桁でAから始まるものだけで21万個以上ありました。数学的な証明は出来ませんが、おそらく無限に続くのではないかと思います。
ABACABCACBABCABACABCACBAC(下に続く)
ABACBABCABACABCACBABCABAC(下に続く)
BABCACBACABACBABCABACABCA(下に続く)
CBABCBACABACBABCABACABCAC
プログラムまで書いて試してくださってありがとうございます。僕もいろいろ紙に書いて試してみたのですが、とても必ず有限列になるようには思えないんですよね。うまく証明できたらよいと思っています。
No.2
- 回答日時:
ABCABACABCABA ←この後にABCのいずれが来てもダメ
ABACABA ←この後にABCのいずれが来てもダメ
ABACABCABACABACABCABACA ←この後にABCのいずれが来てもダメ
ABACABCABACABACABCABACBABCAB… ←これはわからない。
No.1
- 回答日時:
とても面白い問題だと思います。
ご質問とはずれるのですが、
ABACABCABACABAC…に同一パターンがないということを確かめることは、簡単にできるのでしょうか。
ポストの対応問題や分割問題などはそう簡単にはできないようです(NPであってPではないよう)。
でも、今回はもっと簡単な問題ですから無限列は作れそうな、そうでないような。。
後続の方にバトンタッチ。
参考URL:http://www.aist-nara.ac.jp/~yasumoto/lecture/tm/ …ポストの対応問題'
同一パターンがないことを確かめるのは、僕にはしらみつぶしをするしか方法を思いつきません。そういう意味では、もし無限に続くのであれば今のところ証明をする方法がないということになります。何か別のアイデアがあればよいのですが。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- Visual Basic(VBA) 特定の文字を簡単な操作で半角スペースに変換するか削除したい 2 2022/11/01 10:35
- Java Java 南京錠 2 2023/02/04 11:46
- その他(Microsoft Office) 逆順 3 2023/08/24 09:30
- C言語・C++・C# C#の問題です。 文字列型の配列 s[100] にキーボードから入力された100文字以内の文字列(単 2 2022/06/22 15:18
- 計算機科学 急ぎです、大学数学再帰の問題難しくてがわからないです。 以下の4つの文字列を連結して新たに生成できる 1 2023/05/17 20:11
- Visual Basic(VBA) VBAで、1つのエクセルで、2つのシートからもう1つのシートに条件のある転記コードを教えてください。 1 2023/03/16 18:07
- C言語・C++・C# プログラミングの問題です。至急教えてください。 /***から***/の部分をプログラミングにしてほし 1 2022/10/13 11:48
- 数学 すべての自然数とすべての実数を1対1で対応させる(すべての実数を一列に並べる)方法について 3 2023/05/26 17:14
- 囲碁・将棋 詰将棋。過去作品との重複、盗作、偶然の一致については誰が検証しているのか? 2 2023/04/26 20:14
- その他(プログラミング・Web制作) プログラミング pythonの問題について 2 2022/04/19 00:41
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
エクセル初心者です 関数の入れ...
-
エクセルで二つの数字の小さい...
-
LOOKUP関数を使えばいいのでし...
-
PowerPointで表の1つの列だけ...
-
エクセルで最初のスペースまで...
-
エクセル 文字数 多い順 並...
-
VBAで文字列を数値に変換したい
-
2つのエクセルのデータを同じよ...
-
Excelで半角の文字を含むセルを...
-
エクセルの並び変えで、空白セ...
-
EXCELで 一桁の数値を二桁に
-
エクセルの表から正の数、負の...
-
Excel、市から登録している住所...
-
エクセルで文字が混じった数字...
-
A列がない・・・A列が非表示に...
-
エクセルの項目軸を左寄せにしたい
-
エクセルで一列おきに空白列を...
-
【ACCESS/必須条件とOR条件を組...
-
エクセルの隣り合う列のグループ化
-
エクセル(勝手に太字になる)
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
エクセルで二つの数字の小さい...
-
PowerPointで表の1つの列だけ...
-
エクセルで最初のスペースまで...
-
2つのエクセルのデータを同じよ...
-
エクセル(勝手に太字になる)
-
「B列が日曜の場合」C列に/...
-
エクセル 文字数 多い順 並...
-
EXCELで 一桁の数値を二桁に
-
エクセル 同じ値を探して隣の...
-
VBAで文字列を数値に変換したい
-
エクセルの並び変えで、空白セ...
-
Excelで半角の文字を含むセルを...
-
エクセルで文字が混じった数字...
-
Excel、市から登録している住所...
-
A列がない・・・A列が非表示に...
-
エクセルの表から正の数、負の...
-
[関数得意な方]教えて下さい・...
-
エクセルの項目軸を左寄せにしたい
-
エクセル 時間帯の重複の有無
-
Excelにてある膨大なデータを管...
おすすめ情報