これが解けたら天才！コミュのとある数列内に３連続同一パターンが無い証明？

この証明方法がわかりません。

解答は、この場に書き込んで下さい。よろしくお願いします。

２進数列を次のように作っていきます。　直前の数列の０と１とを反転したパターンを後に繋げていくだけです。

Ｘ0 = 0
Ｘ1 = 01　　　　・・・Ｘ0にＸ0の反転　１を追加
Ｘ2 = 0110　　　・・・・Ｘ1の　01　に　Ｘ1の反転　10　を追加　
Ｘ3 = 01101001　・・・・ 0110　の反転 1001を接続
Ｘ4 = 0110100110010110　・・・・・01101001 に 10010110を接続：以下同様。
Ｘ5 = 01101001100101101001011001101001
Ｘ6 = 0110100110010110100101100110100110010110011010010110100110010110

・・・・

Ｘn = (Ｘn-1) * (2^(2^(n-1))) + （(2^(2^(n-1)))－１）－(Ｘn-1)
= (Ｘn-1 ＋１) * ((2^(2^(n-1)))－１）　を２進表示して先頭に０を
　　　　補った形：先頭の桁の０以外、この式で数値としては一致。

あるいは、Ｘn は、０から　2^ｎ－１までの　連続する整数を
２進表記した場合の１のビットの総数が奇数か偶数かを示すパリティ
（奇数の時を１とする）の並びとも解釈できます。

例えば　Ｘ3 は　０から７までの２進数表記で
(000)(001)(010)(011)(100)(101)(110)(111)　各２進数表記での１の総数は：
⇒(０)(１)（１）（２)（１）(２）(２）(３）・・・奇数を１、偶数を０として
偶数奇数奇数偶数奇数偶数偶数奇数の並びから
Ｘ3＝01101001が得らえ、ここから、Ｘ4の後半８～15までの
２進数のパリティは上位桁に１が追加されることで、前半の０～７までの
パリティすなわちＸ3のビットパターンの反転が追加されていくという具合です。

さて、ここからが問題です。

　この無限長の数列　Ｘ∞　の途中のどこからででも、何桁であれ
　３回以上連続しては、同じビットパターンが存在しない訳を説明して下さい。

例えば：
・　０も　１も　３回以上連続しない
・01 も、10 も　３回以上連続しない。
　　　（もちろん00も11も２回以上連続しない）
・001も　010も、011も、100も　101も,110　も　３回以上連続しない。
・0010も　0011も,0100も　0110も　1001も1011も1100も1101も
　　　３回以上連続しない。
　　　　（0101,1010も２回以上連続しないし、0000も1111も存在しない）
・・・という具合に　任意の符号長の任意の２進数列のパターンが、
　　この数列中には３回以上連続しては現れない

という事が言えるでしょうか？あるいは、間違っていて反例があるのでしょうか？

簡単に説明できるかと思ったのですが、うまく説明できません。よろしくお願いします。

コメント(8)

最初
全て
最新の40件

[1] mixiユーザー 02月26日 20:46

はじめまして>コミュの皆様

あまり綺麗ではないのですが、たぶんできたと思ったのでコメントします。

補題（証明略します）
(1) Xn の奇数番目を取り出した数列は X_{n-1} である
(2) Xn の 2k 番目は 2k-1 番目の反転である

本証明
(3) 奇数桁の3回連続するビットパターンは存在しない

そのようなビットパターンが存在したとして a_{i} とする。
3回連続するビットパターンが現れる Xn について、
ビットパターンが現れる箇所を全体に前に1ずらしたものを考える。
ビットパターンのそれぞれの項は1回目のビットパターンか
2回目のビットパターンのどちらかで Xn の偶数番目に当たる。
(2) より、a_{i} は a_{i-1} の反転である。
a_{1} は2回目のビットパターンか3回目のビットパターンのどちらかで
Xn の偶数番目に当たるので a_{i} の最後尾の反転である。
したがって、a_{1} は自分自身を奇数回反転したものとなり、矛盾。

(4) 偶数桁の3回連続するビットパターンは存在しない

3回連続するビットパターンが現れる Xn について、奇数番目だけを取り出すと、
(1) より X_{n-1} について3回連続するビットパターンが現れる。
帰納法と (3) よりこの様なビットパターンは存在しない。

[2] mixiユーザー 02月26日 22:48

さっそくの御回答ありがとうございました。補題(1)の視点は、気がついてませんでした。いろんな見方がありそうですね。

この問題は、将棋の千日手のルール改正（３回同一手順反復から、４回同一局面発生にルールが変更された。）に絡んだ問題です。

　同一局面に至る手順の途中に、例えば　成りと不成りのどちらでも良いという具合に、２つ以上の選択肢があると、同一手順を３回連続では反復しないようにしながら、無限に手を延ばすことができるということで、ルール改正に至ったという話は知っていたんですが：

　では、それを、どうやったら実現できるか？　というところで、ようやく、それらしい方法の一つを見つけたものの証明しきれなかったので、この場を借りた次第です。　
　もっと違う３連続同一反復の無いパターン生成方法はあるでしょうか？

この方法なら３回連続反復どころか、２回連続の反復パターンが現れる箇所や長さも、２^（N+2）の整数倍の地点から、２^Nの長さで４区間に分けた２番目と３番目の区間に限られるように思います。　１番目と４番目の区間では、その反転パターンが並ぶので３回連続反復は無いと証明できることになります。

・・・ぜひ、これについても、コメントがあればうれしいです。

[5] mixiユーザー 02月27日 00:06

自己解決しました
　
●２回連続同一パターンのパターン長は２^Nの長さに限られる。

３以上の奇数長で２回連続同一パターンの並びは存在しない。

　>>1 より、
　　　補題(1)から、あるパターンの先頭位置の奇偶により
　　そのパターン内の偶数番目のビットの右隣か左隣かのどちらかが
　　反転していることと　その後続でも同一パターンが並ぶことから
　　全ビットが隣接ビットの反転になっていなければならなくなる。
　　
　元の数列の構成方法から、このようなビットパターンの最長は　
　0101か1010の長さ４に限られ長さ６以上の連続した
　ビット反転パターンは存在しない。

　これと補題(2)とから、
　　　偶数長の２回連続パターンがあるとすると、その半分に間引いたパターンも
　　　２回連続していることになる。これを反復していった結果として長さ３以上の
　　　奇数になることがないことから、２回連続の同一パターンの、符号長は
　　　２の整数乗の長さに限られる。　長さ１に戻るまで、半分に間引いた結果として
　　　数列の４ｎ＋１番目と４ｎ＋２番目の位置で同一パターンが並ぶことから、

●２回連続同一パターンの配置は、2^(N+2)の整数倍の位置からの、2^N桁目から始まる。
　　２^N長のビットパターンに限定される。

とまぁ、こんな具合でいかがでしょう。

[7] mixiユーザー 02月27日 00:17

↑・・・あ、補題(1)と補題(2)と番号取り違えてました、すみません。

> 数列の４ｎ＋１番目と４ｎ＋２番目の位置で同一パターンが並ぶことから、．．．
> 2^(N+2)の整数倍の位置からの、2^N桁目から始まる．．．．

ここの説明では、先頭を０桁目として、書いてます。　
　　先頭０から始まる２進数で、末尾２桁が、***01と後続の***10　
　　の場所での　パリティが一致しているということです。

[8] mixiユーザー 02月27日 23:47

コメント遅れましたが、

> ●２回連続同一パターンのパターン長は２^Nの長さに限られる。

> ●２回連続同一パターンの配置は、2^(N+2)の整数倍の位置からの、2^N桁目から始まる。２^N長のビットパターンに限定される。

きれいに一般化されたようですね。すっきりしました。

パターン生成方法の族をうまく定式化して、n回連続同一パターンの現れ方を
不変量にするような構造が見えると面白そうです。

ログインすると、みんなのコメントがもっと見れるよ