おしどり遊び（テイトの飛び石ゲーム）の最小手数

「おしどりの遊び」というパズルがあります。
2色の石を１つずつ交互に並べた状態から、必ず隣り合う2個をいっぺんに移動しながら、色が同じになるようにする、というものです(下図)。

●○●○●○
↓
○○○●●●

この図では、はじめと終わりの石の位置が揃っているかのように見えますが、横にずれていてもかまいません。このパズルは日本では江戸時代に「おしどりの遊び」と呼ばれたのだそうですが、「テイトの飛び石ゲーム」という呼ばれ方もされるそうです。

上図には、2×3＝6個の石がありますが、一般に2n個の石のパズルでの、最小手数はどういった数列になるのでしょうか？
また、解がないこともあるのでしょうか？
検索しましたが調べきれませんでした。

No.2 ベストアンサー 回答者： ORUKA1951 回答日時： 2014/05/25 16:15

４組の場合

● ○ ● ○ ● ○ ● ○
● × × ○ ● ○ ● ○ ○ ●(1)
● ● ○ ○ × × ● ○ ○ ●(2)
● ● ○ ○ ○ ○ ● × × ●(3)
× × ○ ○ ○ ○ ● ● ● ●(4)
これが基本、以下
５組の場合
● ○ ● ○ ● ○ ● ○ ● ○
●[× × ○ ● ○ ● ○ ●]○ ○ ●(1)
●[● ○ ○ ● ○ × × ●]○ ○ ●(2)
●[● ○ × × ○ ○ ● ●]○ ○ ●(3)
●[● ○ ○ ○ ○ ○ ● ●]× × ●(4)
× × ○ ○ ○ ○ ○ ● ● ● ● ●(5)
６組の場合
● ○ ● ○ ● ○ ● ○ ● ○ ● ○
● × × ○ ● ○ ● ○ ● ○ ● ○ ○ ●
● ● ○ ○ ● ○ ● ○ ● ○ × × ○ ●
× × ○ ○ ● ● ○ ○ ● ○ ○ ● ● ●
○ ○ ○ ○ ● ● ○ ○ ● × × ● ● ●
○ ○ ○ ○ × × ○ ○ ● ● ● ● ● ●
× × ○ ○ ○ ○ ○ ○ ● ● ● ● ● ●
以降、すべて４個の方法に帰結するので、4組以上は、セットの数になる。


私も探してみましたが
　⇒鴛鴦の問題とその拡張について( http://www.ed.ehime-u.ac.jp/~hirata/publish/1209 … )
かな？？

この回答へのお礼

最小手数がnと簡単になるのはおどろきでした。ありがとうございます。

お礼日時：2014/05/25 22:54