ありえない局面

ありえない局面

すべての盤面の中からありえない局面をとりのぞき、
オセロ局面を満足する盤面数を減らすために必要な証明。
ここでは２パターン取り組んでる。

314 256 sage 2006/02/25(土) 14:40:55 
ある石の周囲にある石の数をとりあえず接続数と呼ぶことにします。 
接続数について考えてみました。 
オセロで実際に存在する盤面は、（当たり前のもありますが、、） 
・全ての石の接続数は１以上。 
・接続数が１の石に接続している石の接続数は２以上。 
・接続数が１の石とそれに接続している石は同じ色。 
↓こういうのは存在しない。 
●＋＋＋＋＋＋＋ 
＋○＋＋＋＋＋＋ 
＋＋●●○○＋＋ 
＋＋●○●○○＋ 
＋＋○●○○＋＋ 
＋＋○●●○＋＋ 
＋＋●●●●＋＋ 
＋●●●●●＋＋ 
・接続数が１の石から３個以下石を辿ると接続数が３以上の石がある。 
↓こういう細長いのは存在しない 
＋＋＋＋＋＋＋＋ 
＋●●●＋●●＋ 
＋●＋●＋＋●＋ 
＋●＋●●＋●＋ 
＋●＋●●＋●＋ 
＋●＋＋＋＋●＋ 
＋●●●●●●＋ 
＋＋＋＋＋＋＋＋ 
最後のは証明してませんが反例はまだ見つかってません。 
どなたか検証お願いします。 

315 293 sage 2006/02/25(土) 15:48:58 
>>314 
＞・接続数が１の石とそれに接続している石は同じ色。 
に対しては反例を挙げておきます。もう少し限定をかければ成立するかもしれませんが。 
↓の石に関して。 
●＋＋＋＋＋＋＋　→　●＋☆＋＋＋＋＋ 
＋●＋＋＋＋＋＋　→　＋○＋＋＋＋＋＋　 
○○○○○○＋＋　→　○○○○○○＋＋ 
＋＋●○●○○＋　→　＋＋●○●○○＋ 
＋＋○●○○＋＋　→　＋＋○●○○＋＋ 
＋＋○●●○＋＋　→　＋＋○●●○＋＋ 
＋＋●●●●＋＋　→　＋＋●●●●＋＋ 
＋●●●●●＋＋　→　＋●●●●●＋＋ 
＞・接続数が１の石から３個以下石を辿ると接続数が３以上の石がある。 
の具体例に関しては（極端な例だからかもしれないけど）他の点からも指摘できます。 
＋＋＋＋＋＋＋＋ 
＋④③②＋●●＋ 
＋⑤＋①＋＋●＋ 
＋●＋●●＋●＋ 
＋●＋●●＋●＋ 
＋●＋＋＋＋●＋ 
＋●●●●●●＋ 
＋＋＋＋＋＋＋＋ 
2と3の順番は逆になるかもしれませんが…とりあえず5は挟む物がないので置けません。 
ついでに、最後のは分かりにくい気がするので言い換えを提案します。 
・接続数が１の石から接続数が２以下の石だけを辿ると２個分までしか辿れない。 

316 256 sage 2006/02/25(土) 15:57:36 
>>315 
ああ、なるほど。 
もうちょっとよく考えて色んなふるいを作りたいと思います。