「教えて!ピックアップ」リリース!

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

●○●○●○

○○○●●●

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

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

A 回答 (1件)

4組の場合


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


私も探してみましたが
 ⇒鴛鴦の問題とその拡張について( http://www.ed.ehime-u.ac.jp/~hirata/publish/1209 … )
かな??
    • good
    • 1
この回答へのお礼

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

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

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!


人気Q&Aランキング