将棋の千日手に関して

質問

将棋の千日手のルールは１０数年前に、同じ手順を３回連続して繰り返すと成立するという条件から、同一局面が４回出現したら成立すると変更されました。こうなったのは、同じ局面に戻る手順が２通りあるときに、この２つを繰り返すと無限に千日手にならない手順を続けられるということだったと思います。この方法と証明を御教え願えないでしょうか？
話を単純にするため、aとbの２つの文字で、文字列のどの部分を見ても同じ文字列の３回連続することのない無限に長い列を生成する手続きを教えてください。
私は、a(n)、b(n)があったとき、a(n+1)=a(n)+a(n)+b(n)、b(n+1)=a(n)+b(n)+b(n),というやりかたで出来るように思ったのですが、証明が思いつきませんでした。

回答No.1

adinat · ベストアンサー

過去ログをご覧ください。私がかつて同じ疑問を持って質問したものです。いちばん最後の回答がa,b,c3文字による文字列で、どこにも同じパターンが2回連続しない無限列に対する答えです。なかなか骨があります。

moritan2様の問いはa,b2文字による文字列で、どこにも同じパターンが3回連続しない無限列ということですので、3文字版の無限列で、たとえば、a→ab、b→aab、c→abbとでも置き換えればよいかと思います。

私の疑問の出発点は、「【同一手順を3回繰り返して千日手】は無限に勝負が終わらない可能性がある」が、「【同一手順を2回繰り返して千日手】も無限に勝負が終わらない可能性があるか？」という問いでした。つまり同一局面4回ではなくて、3回繰り返す→2回繰り返す、という方面にルールを強化するのではダメか？という問いだったのですね。この場合は、2文字では無限列は作りようがないため、3文字の無限列を考えたのが先の質問です。2回なら繰り返してもよいという条件があれば、2文字でも作れるわけです。

たとえば先手玉が59にいて、後手玉が51にいるとして、ともに上下左右に別の駒がないとします。
a=▲49玉、△41玉、▲59玉、△51玉
b=▲69玉、△61玉、▲59玉、△51玉
c=▲58玉、△52玉、▲59玉、△51玉
とすれば、同一手順が2回繰り返すこと一度もなく、無限におわらない手が作れる、というわけですね。

moritan2様の方法でも証明は出来ると思います。参考URLの手法が参考になると思います。たとえばa(n)+a(n)+b(n)という文字列があって、これを漸化式を用いてa(1)、b(1)の3^n個の文字列に書きなおすとします。このとき、「もし同じパターンが3回続くところがあれば、a(2)、b(2)で書きなおした3^{n-1}個の文字列にも同じパターンが3回続くところがある」、ということを証明するのです。つまり「子が同一パターン3回を持てば、親が同一パターン3回を持つ」を示すわけです。あとは数学的帰納法と背理法を組み合わせれば、無限列が存在することが証明できるでしょう。初期値a(n)+a(n)+b(n)には同一パターン3回は存在しないですから。

キーになるのは、「子が同一パターン3回を持てば、親が同一パターン3回を持つ」という事実であって、このような配列をうまくとってやれば求めたいことが実現するわけですね。

参考URL：

http://okwave.jp/kotaeru.php3?q=1715716