記号の並べ替え 　　　　　　　　　　　　　　　　　　

　下図のような、１４個の空所がある。

この空所に、アルファベットの「Ａ」と「Ｂ」が下図のように並んでいる。

　これらの記号を、次のルールに従って並べ替える。

（ルール）　１．　１回の操作で隣り合う２つの記号を他の空所に移動する。

　　　　　　　２．　移動する２つの記号の順番は変えないものとする。

　このとき、記号が、ＡＢＡＢ・・・ＡＢ と隙間なく並べ替えられるには、最低何回の操作
が必要であろうか？

Ｆｌａｓｈ で、数字を実際に動かしてみよう。

　　Ｆｌａｓｈ 版は、こちら　　　　ＨＴＭＬ 版は、こちら　　をクリックしてください。

　セキュリティ保護のため、コンピュータにアクセスできるアクティブ　コンテンツが表示されないように、
Ｉｎｔｅｒｎｅｔ　Ｅｘｐｌｏｒｅｒ　で制限していると、ＨＴＭＬ版、Ｆｌａｓｈ版ともに見られません。ブロックされている
コンテンツを許可してください。（すみません、自己の責任でお願いします。）





















（答）　６回の操作で出来る。次のように並べ替えればよい。

　上記の操作では、ＡＢＡＢ・・・ＡＢ という順番のこだわったが、単に、ＡとＢが交互にな
っていればよいという条件の下では、５回の操作で出来る。

　（参考文献：仲田紀夫　著　算数パズル「出しっこ問題」傑作選　（講談社））


　当ＨＰがいつもお世話になっているＨＮ「ＦＮ」さんが、この問題の拡張を考えられた。
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　（平成２２年７月３日付け）
　空所を「0」、Ａを「1」、Ｂを「2」で表すことにすると、問題は、

　　　00111112222200　を　1212121212 を含む形(0は右端または左端)にせよ

と言い換えられる。このとき、答えとしては、次の６手の手順になる。

　　　　　00111112222200→
　　　　　00100112222211→
　　　　　00122112002211→
　　　　　00122112112200→
　　　　　00122112100212→
　　　　　00120012121212→
　　　　　00121212121200

　まず、問題は、

（１）６手が最短であることを証明せよ。

　　現在、研究中。


　次に、「１が５個、２が５個」であるのを、「１が ｎ 個、２が ｎ 個」に変えてみる。

　ｎ＝１　のときは、０手。ｎ＝２　のときは、．．．（できそうにない！）。

　※　「ｎ＝２　では不可能であること」の証明を当ＨＰがいつもお世話になっている、ＨＮ「ら
　　すかる」さんより頂きました。（（平成２２年７月８日付け））

　　（証明）　「１が２個、２が２個」の各数字の移動パターンは次の１０通りしかない。

　　　　上記のそれぞれのパターンについて初手の可能性は全て上記パターンに含まれる。

　　　　　実際に、　　Ａ　→　Ｂ、Ｆ、Ｇ　　　　Ｂ　→　Ａ、Ｄ　　　Ｃ　→　Ｄ、Ｅ、Ｈ

　　　　　　　　　　　　Ｄ　→　Ｂ、Ｃ、Ｊ　　　　Ｅ　→　Ｃ、Ｆ　　　Ｆ　→　Ａ、Ｅ、Ｉ

　　　　　　　　　　　　Ｇ　→　Ａ、Ｊ　　　　Ｈ　→　Ｃ、Ｉ　　　Ｉ　→　Ｆ、Ｈ　　　Ｊ　→　Ｄ、Ｇ

　　　　上記の１０パターンは、「1212」を含む形ではないので、ｎ＝２　では不可能である。

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　（証明終）

　そこで、

（２）　ｎ を３以上の自然数とする。

　　１が ｎ 個、２が ｎ 個にしたとき、ｎ＋１手でできることを示せ。

　あるいは、

（２’）　ｎ を３以上の自然数とする。

　　１が ｎ 個、２が ｎ 個にしたとき、何手でできるか。できるだけ短い手順を考えて

　　ください。

　この問いかけに対し、らすかるさんが、プログラムで調べられたところ、

　　ｎ＝３〜８について、ｎ＋１手でできる

とのこと。（平成２２年７月５日付け）

　ＦＮさんが、ｎ＝３、４、５、６のときの手順を考えられた。（平成２２年７月５日付け）

いずれも左側の 00 は使わないので省略。

ｎ＝３
　　　　　11122200→
　　　　　10022211→
　　　　　12122001→
　　　　　12100221→
　　　　　12121200

ｎ＝４
　　　　　1111222200→
　　　　　0011222211→
　　　　　1210022211→
　　　　　1212122001→
　　　　　1212100221→
　　　　　1212121200

ｎ＝５
　　　　　111112222200→
　　　　　100112222211→
　　　　　122112002211→
　　　　　122112112200→
　　　　　122112100212→
　　　　　120012121212→
　　　　　121212121200

ｎ＝６
　　　　　11111122222200→
　　　　　00111122222211→
　　　　　12111002222211→
　　　　　12111212222001→
　　　　　12111212002221→
　　　　　12001212112221→
　　　　　12121212100221→
　　　　　12121212121200

　さらに、らすかるさんが、ｎ＝７、８ の最短手順解（の一つ）を考えられた。
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　（平成２２年７月６日付け）
ｎ＝７
　　　　　1111111222222200→
　　　　　1001111222222211→
　　　　　1221111002222211→
　　　　　1221111212222001→
　　　　　1221111212002221→
　　　　　1221100212112221→
　　　　　1200121212112221→
　　　　　1212121212100221→
　　　　　1212121212121200

ｎ＝８
　　　　　111111112222222200→
　　　　　001111112222222211→
　　　　　121111100222222211→
　　　　　121111121222222001→
　　　　　121111121200222221→
　　　　　121001121211222221→
　　　　　121221121211200221→
　　　　　121200121211221221→
　　　　　121212121210021221→
　　　　　121212121212121200

（コメント）　ＦＮさん、らすかるさん、ありがとうございます。
　　　　　　左側の 00 は使わないわけですが、問題としての美しさを考えて左右対称形にし
　　　　　たように思います。

　さらに、らすかるさんが、ｎ＝１６〜１９ の最短手順解（の一つ）を考えられた。
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　（平成２２年７月７日付け）
ｎ＝１６
　　　　　1111111111111111222222222222222200→
　　　　　0011111111111111222222222222222211→
　　　　　1211111111111110022222222222222211→
　　　　　1211111111111112122222222222222001→
　　　　　1211111111111112120022222222222221→
　　　　　1210011111111112121122222222222221→
　　　　　1212211111111112121122002222222221→
　　　　　1212211001111112121122112222222221→
　　　　　1212211221111112121122112200222221→
　　　　　1212211221100112121122112211222221→
　　　　　1212211221122112121122112211200221→
　　　　　1212001221122112121122112211221221→
　　　　　1212121221122112121002112211221221→
　　　　　1212121200122112121212112211221221→
　　　　　1212121212122112121212100211221221→
　　　　　1212121212120012121212121211221221→
　　　　　1212121212121212121212121210021221→
　　　　　1212121212121212121212121212121200

ｎ＝１７
　　　　　111111111111111112222222222222222200→
　　　　　100111111111111112222222222222222211→
　　　　　121111111111111112222222222222222001→
　　　　　121111111111111112002222222222222221→
　　　　　121001111111111112112222222222222221→
　　　　　121221111111111112112200222222222221→
　　　　　121221100111111112112211222222222221→
　　　　　121221122111111112112211220022222221→
　　　　　121221122110011112112211221122222221→
　　　　　121221122112211112112211221122002221→
　　　　　121221122112210012112211221122112221→
　　　　　121221122112211212100211221122112221→
　　　　　121200122112211212121211221122112221→
　　　　　121212122112211212121210021122112221→
　　　　　121212120012211212121212121122112221→
　　　　　121212121212211212121212121002112221→
　　　　　121212121212001212121212121212112221→
　　　　　121212121212121212121212121212100221→
　　　　　121212121212121212121212121212121200

ｎ＝１８
　　　　　11111111111111111122222222222222222200→
　　　　　00111111111111111122222222222222222211→
　　　　　12111111111111111002222222222222222211→
　　　　　12111111111111111212222222222222222001→
　　　　　12111111111111111212002222222222222221→
　　　　　12100111111111111212112222222222222221→
　　　　　12122111111111111212112200222222222221→
　　　　　12122110011111111212112211222222222221→
　　　　　12122112211111111212112211220022222221→
　　　　　12122112211001111212112211221122222221→
　　　　　12122112211221111212112211221122002221→
　　　　　12122112211221001212112211221122112221→
　　　　　12122112211221121212100211221122112221→
　　　　　12120012211221121212121211221122112221→
　　　　　12121212211221121212121210021122112221→
　　　　　12121212001221121212121212121122112221→
　　　　　12121212121221121212121212121002112221→
　　　　　12121212121200121212121212121212112221→
　　　　　12121212121212121212121212121212100221→
　　　　　12121212121212121212121212121212121200

ｎ＝１９
　　　　　1111111111111111111222222222222222222200→
　　　　　1001111111111111111222222222222222222211→
　　　　　1211111111111111111222222222222222222001→
　　　　　1211111111111111111200222222222222222221→
　　　　　1210011111111111111211222222222222222221→
　　　　　1212211111111111111211220022222222222221→
　　　　　1212211001111111111211221122222222222221→
　　　　　1212211221111111111211221122002222222221→
　　　　　1212211221100111111211221122112222222221→
　　　　　1212211221122111111211221122112200222221→
　　　　　1212211221122110011211221122112211222221→
　　　　　1212211221122112211211221122112211200221→
　　　　　1212001221122112211211221122112211221221→
　　　　　1212121221122112211210021122112211221221→
　　　　　1212121200122112211212121122112211221221→
　　　　　1212121212122112211212121002112211221221→
　　　　　1212121212120012211212121212112211221221→
　　　　　1212121212121212211212121212100211221221→
　　　　　1212121212121212001212121212121211221221→
　　　　　1212121212121212121212121212121210021221→
　　　　　1212121212121212121212121212121212121200

　この「ｎ＋１」手の手順について、らすかるさんが一般化されました。
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　（平成２２年７月７日付け）

　手順の書き方

　　　　「左からｍ桁目とｍ＋１桁目を空き位置に移動する」ことを、単に、ｍ　と書く。

　　　ただし、左端は０桁目とする。

　例えば、ｎ＝３　の解は、

　　　　　11122200→
　　　　　10022211→
　　　　　12122001→
　　　　　12100221→
　　　　　12121200

なので、「 １ ５ ３ ６ 」という手順となる。

(ｎ＝４ｋの場合)　→　手順の解説
　　　　0 n-1 2n-1
　　　　n+2 3 n+6 7 n+10 11 … 2n-6 n-5　※この行　2項×(k-1)組=2k-2項だけ
　　　　2n-3
　　　　4 n+3 8 n+7 12 n+11 … n-4 2n-5　※この行　2項×(k-1)組=2k-2項だけ
　　　　2n

(ｎ＝４ｋ＋１の場合)
　　　　1 2n-1 n+1
　　　　3 n+5 7 n+9 11 n+13 … n-6 2n-4　※この行　2項×(k-1)組=2k-2項だけ
　　　　n-3 n+2
　　　　4 n+6 8 n+10 12 n+14 … n-5 2n-3　※この行　2項×(k-1)組=2k-2項だけ
　　　　2n

(ｎ＝４ｋ＋２の場合)
　　　　0 n-1 2n-1 n+2
　　　　3 n+6 7 n+10 11 n+14 … n-7 2n-4　※この行　2項×(k-1)組=2k-2項だけ
　　　　n-4 n+3
　　　　4 n+7 8 n+11 12 n+15 … n-6 2n-3　※この行　2項×(k-1)組=2k-2項だけ
　　　　2n

(ｎ＝４ｋ＋３の場合)
　　　　1 2n-1
　　　　n+1 3 n+5 7 n+9 11 … 2n-6 n-4　※この行　2項×k組=2k項だけ
　　　　2n-3
　　　　4 n+2 8 n+6 12 n+10 … n-3 2n-5　※この行　2項×k組=2k項だけ
　　　　2n

※「この行〜項」という行は、ｎ が３〜６の場合、行削除となる。

　これで、「ｎ＋１手で可能」ということが分かった。また、変更されなければならない不連続
箇所がｎ箇所あるため、「少なくともｎ手は必要」であることも容易に分かる。あとは「ｎ手で
は出来ない」ことを証明すれば終わりですが、簡単ではなさそうですね。

（コメント）　らすかるさん、ありがとうございます。一般的な手順の存在に感動しました！

　以下で、ｎ＝３〜９　について、手順を翻訳しました。

　上記の手順に従って、ｎ＝９　のときを書き下してみた。

　　　　　11111111122222222200→
　　　　　10011111122222222211→
　　　　　12111111122222222001→
　　　　　12111111120022222221→
　　　　　12100111121122222221→
　　　　　12122111121122002221→
　　　　　12122100121122112221→
　　　　　12122112121002112221→
　　　　　12120012121212112221→
　　　　　12121212121212100221→
　　　　　12121212121212121200

（コメント）　う〜む、なるほど！１２〜１３手でしかできなかったので、．．．感動！


　ＦＮさんが、らすかるさんの手順（ｎ＝４ｋ）について解説を与えられた。
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　（平成２２年７月９日付け）

　まず、最初の３手「 0 n-1 2n-1 」で次の形になる。

　　　　121 11 11 11 ･･･11 212 22 22 ･･･22 22 2001

　（見やすくするために適当にスペースを入れてある。）

　ここで、「11」及び「22」は、2k-2=2(k-1)組ずつある。

　次に、奇数番目の「22」と「00」の交換を行い、その後、奇数番目の「11」と「00」の交換をす
べて行うと次の形になる。

　　　　121 2211 2211 ･･･ 2211 0011 212 1122 1122 ･･･ 1122 2221

　「22」と「00」、「11」と「00」の順番、そして奇数番目の「22」や「11」であることさえ守れば順序
は問わない。

　ここで、「2211」、「1122」は、k-1組ある。ただし、「2211」のうち、１つは「0011」。

　「0011」の「00」を、後ろから５番目の位置にある「22」と交換して、

　　　　121 2211 2211 ･･･ 2211 2211 212 1122 1122 ･･･ 1120 0221

　これを書き直して、

　　　　12 12 2112 2112 ･･･ 2112 121 1221 1221 ･･･ 1221 12002 21

　ここで、「2112」は、k-1組、「1221」は、k-2組ある。

　「2112」は、「21」が「12」に、「1221」は、「12」が「21」にならなければいけない。

　まず、「2112」の「21」を「00」と交換、「1221」の「12」を「00」と交換する。この操作を続ける。

　その結果

　　　　12 12 1212 1212 ･･･ 1212 0012 121 2121 2121 ･･･ 2121 12212 21

　あとは後ろから7番目の位置にある「12」を「00」、最後の「21」を「00」と交換して完成する。

　手数は、最初に３手。「22」と「00」、「11」と「00」の交換で、2(k-1)手。次に、１手。

　「2112」の「21」と「00」の交換、「1221」の「12」と「00」の交換で、k-1+k-2=2k-3手。

　最後に2手。あわせて、3+2k-2+1+2k-3+2=4k+1=n＋1手。

（コメント）　「2211」、「1122」の形を作り、「21」と「12」を一気に交換しないと最短手順は難し
　　　　　　いだろうな〜と思っていましたが、ＦＮさんの解説を見て納得しました！ＦＮさんに感
　　　　　　謝します。


　ＦＮさんより、次の問題についてコメントをいただきました。（平成２２年７月２５日付け）

　11・・・122・・・200　を　002121・・・21 を含む形(0は右端または左端)にせよ

　前の問題より、この方が簡単だと思う。ｎ が４以上のとき、ｎ 手でできる。（→：参考）

そこで、（１）　ｎ が ４、５、６、７ のときの ｎ 手の手順を作ってください。

　　　　　（２）　ｎ が４以上のとき、ｎ 手でできることを示してください。

　この問題は、「おしどりの遊び」あるいは「おしどりパズル」として有名な問題でした。
ただし、逆の形で出題されるのが普通のようです。

　すなわち、002121････21　を　11････122････200　にする問題として。

　これが ｎ 手でできると書いてあるサイトはいろいろあります。しかし、ｎ 手でできることの
証明が書いてあるのは私が気付いた所では下記のみです。

　　　　　　第６章 パズル的な数列の問題（岐阜県教育委員会）

　ｎ 手が最短であることの証明もそんなに難しくないでしょう.。


　この問題について、ＨＮ「攻略法」さんから解答をいただいた。（平成２２年７月２５日付け）

ＢＡ型・・・らすかるさんの場合と違って、左端が「１桁目」であることに注意。

ｎ＝４　の場合、手順　(2,5,8,1)　※１相対
ｎ＝５　の場合、手順　(2,8,5,10,1)
ｎ＝６　の場合、手順　(2,8,4,9,12,1)
ｎ＝７　の場合、手順　(2,11,5,10,7,14,1)　または　(2,11,5,14,7,10,1)

ｎ＝ｋ＋４　（ｋ≧４）の場合、３つの部分に分けて
　　　０手　1111┃11…22…22┃22__　2桁目
　　　１手　1__1┃11…22…22┃2211　2*k+5桁目
　　　２手　1221┃11…22…__┃2211　中央部分は、再帰的 k=((((p+4)+4)+4) … )+4
　　　　　　　　└ k個ずつ ┘
　　　ｋ手　1221┃__2121…21┃2211　2*k+8桁目
　　　３手　1221┃212121…21┃2__1　1桁目
　　　４手　__21┃212121…21┃2121
　　となり、ｋ＋４回、すなわち、ｎ 回で移動できる。

実際に、ｎ＝９　の場合を計算すると、　９＝ｋ＋４　より、ｋ＝５　となり、

＼1234┃567890123456┃7890
0 1111┃111112222222┃22__ 2桁目
1 1__1┃111112222222┃2211 15桁目
2 1221┃1111122222__┃2211 2+4=6桁目 　※ｎ＝５　の手順　(2,8,5,10,1)　より
3 1221┃1__112222211┃2211 8+4=12桁目
4 1221┃1221122__211┃2211 5+4=9桁目
5 1221┃1221__212211┃2211 10+4=14桁目
6 1221┃122121212__1┃2211 1+4=5桁目
7 1221┃__2121212121┃2211 18桁目
8 1221┃212121212121┃2__1 1桁目
9 __21┃212121212121┃2121

また、ｎ＝１３　の場合を計算すると、　１３＝ｋ＋４　より、ｋ＝９　となり、

＼1234┃56789012345678901234┃5678
0 1111┃11111111122222222222┃22__ 2桁目
1 1__1┃11111111122222222222┃2211 23桁目
2 1221┃111111111222222222__┃2211

　ここで、ｎ＝９　の手順　(2,15, 6,12,9,14,5, 18,1)　より
手順(2+4,15+4, 6+4,12+4,9+4,14+4,5+4, 18+4,1+4)の９手で中央部分は

　 1221┃__212121212121212121┃2211

となる。

11 1221┃__212121212121212121┃2211 26桁目
12 1221┃21212121212121212121┃2__1 1桁目
13 __21┃21212121212121212121┃2121

同様に

AB型

ｎ＝３、４、５、６　は、１つの例を提示する。それぞれ、１、４、１６、２１通りの中から、
ｎ＝３　の場合、手順　(2,6,4,7)　※１相対
ｎ＝４　の場合、手順　(1,4,8,6,9)
ｎ＝５　の場合、手順　(2,7,11,3,8,11)
ｎ＝６　の場合、手順　(1,6,12,9,3,10,13)
ｎ≧７　について、すなわち、ｎ＝ｋ＋３　（ｋ≧４）とする。
３つの部分に分けて
０手　111┃11…11122…222┃2__　2桁目
１手　1__┃11…11122…222┃211　2*k+6桁目
２手　121┃11…11122…222┃__1　2*k+4桁目
３手　121┃11…11122…2__┃221　中央部分は、BA型に帰着
　　　　　　└ k個ずつ ┘
ｋ手　121┃__21212121…21┃221　2*k+7桁目
４手　121┃21212121…2121┃2__
となり、ｋ＋４回、すなわち、ｎ＋１回で移動できる。

ｎ＝１６　の場合を計算すると、　１６＝ｋ＋３　より、ｋ＝１３　となり、

＼123 ┃4567890123456789012345678901┃234
0 111 ┃1111111111111222222222222222┃2__ 2桁目
1 1__ ┃1111111111111222222222222222┃211 32桁目
2 121 ┃1111111111111222222222222222┃__1 30桁目
3 121 ┃11111111111112222222222222__┃221 2+3=5桁目 　※BA型　ｎ＝１３　の手順より
4 121 ┃1__1111111111222222222222211┃221 23+3=26桁目
5 121 ┃1221111111111222222222__2211┃221 6+3=9桁目
6 121 ┃12211__111111222222222112211┃221 19+3=22桁目
7 121 ┃122112211111122222__22112211┃221 10+3=13桁目
8 121 ┃122112211__11222221122112211┃221 16+3=19桁目
9 121 ┃122112211221122__21122112211┃221 13+3=16桁目
10 121┃122112211221__21221122112211┃221 18+3=21桁目
11 121┃12211221122121212__122112211┃221 9+3=12桁目
12 121┃12211221__212121212122112211┃221 22+3=25桁目
13 121┃122112212121212121212__12211┃221 5+3=8桁目
14 121┃1221__2121212121212121212211┃221 26+3=29桁目
15 121┃1221212121212121212121212__1┃221 1+3=4桁目
16 121┃__21212121212121212121212121┃221 33桁目
17 121┃2121212121212121212121212121┃2__

（コメント）　攻略法さん、ありがとうございます。ＦＮさんと同様に私も感動しました。


　さらに、ＨＮ「攻略法」さんから新しい問題提起です。（平成２２年９月８日付け）

「おしどりの遊び」(N*N,3)型-雌雄のおしどりがＮ羽ずつ、移動は３羽

開始の並びは、右端に空きがある12121212___とする。

終了の並びは、

　___11112222　,　11112222___　,　___22221111　,　22221111___

のいずれかとする。たとえば、N=4の場合

（解）Nが奇数の場合、N 回

N=3
0: 12121┃2___
1: 1___1┃2212
2: 12211┃___2
3: ___11┃1222
　└ 5 ┘└ 4 ┘　※左側と右側の２つの部分に分けられる

参考
　0: ___121212
　1: 12112___2
　2: 1___22112
　3: 111222___


以降は、N-2に帰着させて、残り２手でできることを示す。

N=5
0: 12┃12121┃21┃2___　N=3に帰着　xx┃12121┃xx┃2___ の部分
1: 12┃1___1┃21┃2212　+1　　　　　　└ 5 ┘　　└ 4 ┘
2: 12┃12211┃21┃___2　+2
3: 12┃___11┃21┃1222　+3
4: 12　21111　--　-222
5: --　-1111　12　2222
　　└ 7 ┘ ┃└ 6 ┘　※同上

N=7
0: 12┃1212121┃21┃212___　N=5に帰着　xx┃1212121┃xx┃212___ の部分
1: 12┃121___1┃21┃212212　+1　　　　　　 └ 7 ┘　　　└ 6 ┘
2: 12┃1212211┃21┃21___2　+2
3: 12┃12___11┃21┃211222　+3
4: 12┃1221111┃21┃___222　+4
5: 12┃___1111┃21┃122222　+5
6: 12　2111111　--　-22222
7: --　-111111　12　222222
　　└ 9 ┘　 ┃　└ 8 ┘　※同上

一応解法を得たが、簡単、明解な手順が見えないか！？

（別解）

●Nが奇数の場合、N 回

たとえば、N=7の場合

開始の並び
　123456789ABCDEFGH（位置）
　12121212121212___
を
　123456789
　*ABCDEFGH
と２段で表現する。（「左側と右側の２つの部分に分けられる」の表現）

実際の並びは
　121212121
　*21212___
となる。

上記の操作を、これで表記すると

0: 121212121　上段の左斜めから
　 *21212___

1: 12121___1　下段から
　 *21212212

2: 121212211　上段の左斜めから
　 *2121___2

3: 1212___11　下段の左斜めから　※前４つを無視すれば、N=3が完成！
　 *21211222

4: 121221111　上段の左斜めから
　 *21___222

5: 12___1111　下段の左斜めから　※前２つを無視すれば、N=5が完成！
　 *21122222

6: 122111111　上段の左斜めから
　 *___22222

7: ___111111
　 *12222222

(操作1)上段の左斜めから
(操作2)下段から
(操作3)上段の左斜めから
(操作4)下段の左斜めから
(操作3)上段の左斜めから
(操作4)下段の左斜めから
(操作3)上段の左斜めから
(操作4)下段の左斜めから
　・・・・・・
となる。

同様に、9,11,13,…と拡張できる。


●Nが偶数の場合、N+1 回

たとえば、N=6の場合、開始の並び

実際の並びは
0: 12121212*
　 **1212___
となる。

上記の操作を、これで表記すると

0: 12121212*　上段の左斜めから
　 **1212___

1: 12121___*　下段の左斜めから
　 **1212212

2: 12121122*　上段の左斜めから
　 **12___12

3: 121___22*　下段の左斜めから
　 **1221112

4: 12112222*　上段の左斜めから
　 **___1112

5: 1___2222*　終端から
　 **2111112

6: 11122222*　始端から
　 **2111___

7: ___22222*
　 **2111111

N-1手まで
　(操作1)上段の左斜めから
　(操作2)下段の左斜めから
　(操作1)上段の左斜めから
　(操作2)下段の左斜めから
　・・・・・・
　(操作1)上段の左斜めから

N手　終端から
N+1手　始端から

同様に、8,10,12,…と拡張できる。（前記のN=4は、この手順で求めた）

（コメント）　当ＨＰの掲示板「出会いの泉」に投稿された原稿のアップです。攻略法さんに感
　　　　　　謝します。


　このパズルに類した問題を、当ＨＰがいつもお世話になっているＨＮ「らい」さんより頂きま
した。（平成２４年１月１６日付け）

　黒ｎ個、白ｎ個の計２ｎ個の碁石が下のように並べられている。(ｎ≧３)

　　●●…●○○…○

このとき、次のルールに従って、下のような黒白交互の並びになるように碁石を動かす。

　　●○●○…●○

（ルール）

・隣り合う二つの碁石を選び、順番を変えずに隣り合ったまま横の空いている部分に動かす。
・移動した碁石のあったところは詰めずに空白のままにしておく。
・空白を挟む二つの碁石を選ぶことはできない。
・完成図の碁石の間に空白があってはならない。

例えば、ｎ＝３のとき、次のように動かせばよい。

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

問題　ｎ＝４、５のときは、どのように動かせばよいか。できれば、ｎ≧６についても解き方を
　　　示してください。


　ＦＮさんからのコメントです。（平成２４年１月１７日付け）

　上記に答えがあります。最初の方は正順(11･･･122･･･2を1212･･･12にする)で、途中から
逆順(11･･･122･･･2を2121･･･21にする)です。らいさんが書かれているのは逆順です。


　当ＨＰ読者のＨＮ「河南勝」さんが、上記のらいさんの問題について考察されました。
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　（平成２４年３月３１日付け）

　この問題は、「呉清源ゲーム」とか「碁石並べ替え遊び」と呼ばれているもので、昔から知
られているものですね。しかし、最初の３行、つまりゲームの目的を「白黒交互に並ぶように
する」とすれば、ルールの第１行目の部分を

　　　「隣り合う二つの碁石を移動する。

　　　　ただし、２個の石は平行移動だけが許される。回転させてはけない。」

と変えれば何個でも、つまり、ｎ=1 でも、ｎ=2 でもできます。

　ｎ=1のときは、一旦動かして元のところに戻せばいいので、ちっとも面白くありませんが、
できると言えばできます。

　学生にさせると、決まって回転させようとします。また、空白を詰めるように動かしてしまい
ます。全体として順番を変えるのが、このゲームの目的ですから。

　「二個を回転しない」としたほうが分かりやすい。

　私は、今から50年も前、学生時代にこの問題を知って、どう考えたら解けるかと毎日考え
て、何個でもできることを自分で見つけました。数学では、ｎ≧3の順列・組み合わせの問題
なのでしょうが、遊びとしてはあんまり制限を多くしないでやると、ｎ=2 でも発想の転換で黒
白交互に並べられるので、面白いと思います。ｎ=8の時が一番易しく規則的にできますね。

　1、2年前、関西棋院の雑誌にこの問題が懸賞問題として載っていたそうです。私の弟は記
事を見てすぐ正解を編集部に返事を出して、まんまと賞を貰いました。弟は以前から解をコ
ンピューターのファイルにして持っていましたので、すぐ解答できたのです。私は、以前、ｎ=3
は特殊だと思っていたのですが、ｎ=7は、ｎ=3 とおなじ系列なんですね。最近、インターネット
が普及したせいで、自分で考えず答えを教えてくれと言うのが多いようです。難問を解く楽し
みを放棄しているようで残念な気がします。

　これと同じ問題がYahooの智恵袋に投稿されていて、その回答・ベストアンサーが隙間をど
んどん詰めていって、しかも、回数など全く無視するものになっているのですが、ルールを知
らない人が質問してルールを知らない人が答えているから、こんなルールがあると知ってい
る人間から見るとなんだかおかしいのですが、インターネットで得られる解答は時にはおかし
なものなのでしょうね。

　ゲームの目的が「ｎ回で白黒又は黒白が交互に並ぶように碁石を動かす」としないと、順番
にこだわる数学者から文句が出そうです。また、ｎ個は、ｎ回でできるとしたほうがゲームとし
ては単純で遣り甲斐があります。

　ｎ≧4では、最初に動かすのは端から2番目と3番目と言うのが正解です。2回目は、n≧8の
場合は移動した石から2個置いた内側の同じ色の2個を動かすというルールで内側へ進み、
内側から外へは違う色の2個組を隙間に入れていくという手順でできます。

　n=8、12、16、・・・　は、最も機械的に出来ます。n=5、6、7 のシリーズは一番内側がそれぞ
れ違うので、一工夫いります。


（コメント）　河南勝さん、いろいろな情報をいただいて感謝します。


　らいさんからのコメントです。（平成２４年４月２日付け）

　知っているかもしれませんが、呉清源先生は「昭和の棋聖」と言われるほどの偉大なプロ
棋士です。様々な情報提供ありがとうございます。勉強になりました。確かに、この問題は
ルールをきちんとしたうえで、石の数と手数の美しい関係を垣間見られるわけで、そう考え
ると、そのような現実は悲しく感じますね・・・。


　河南勝さんからのコメントです。（平成２４年４月４日付け）

　呉清源は、私の大学時代にはまだ５〜７段の時代ですから、その頃はこのゲームに「呉清
源ゲーム」などという名前はついていなかったはずですが、いつ頃からこんな名前がついた
のでしょうかね。本当か嘘かは知りませんが、昭和の棋聖呉清源もこんなゲームを楽しんで
(苦しんで)いたのかと思うと愉快になってきます。一応私もへぼ碁を打ちますので．．．。

　私も以前は、３個以上でしかできないゲームだと思っていたのですが、「ｎ 個の白石と ｎ 個
の黒石の並びを、互いに接する２個の石を平行移動して、ｎ回の操作で、間に空白がないよ
うに石の色が交互になるように並べ替える」としたら２個でもできると最近気付いて嬉しくなっ
ています。何個でもできると知って、長い間このゲームから遠ざかっていたのですが、本当は
どんなルールなのかなと、ごく最近インターネットで調べて、一応のルールや名前なども知り
ました。数学者は白黒交互か黒白交互か気になさるようです。碁盤の上での碁石の並べ替
え遊びですから、どちらでもいいのですが、確かに、このルールだと、ｎ=2 以外は逆順にな
ってしまいますね。ｎ回という制限をはずすと正順も可能になります。

　最終的な石の並びに、「間にスペースが入ってはいけない」という制限を入れないと簡単に
できてしまいます。動かす２個の石は白黒を黒白と順番を変えてはいけない(あるいは回転を
してはいけない)とか、スペースをつめてはいけないというように、ルールをもっとはっきり明示
的に書く方がいいかもしれません。

　ところで、n=2 のときの答えは分かりましたか？



　　　　以下、工事中