数字の並べ替え 　　　　　　　　　　　　　　　　　　

　下図のような空所がある。

この空所に、数字の１から５までが順に並んでいる。

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

（ルール）　１．　１→２→３→４→５→１→２→・・・　と数字の順番に、数字を、数字の入って
　　　　　　　　　いない空所のどちらかに移動する。

　　　　　　　２．　１回の操作で動かせる数字は、ひとつだけとする。

このとき、次のように数字を並べ替えるには、最低何回の操作が必要であろうか？

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

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

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


















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

　当ＨＰがいつもお世話になっているＨＮ「ＦＮ」さんが、このパズルを次のように拡張された。
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　（平成２２年６月２６日付け）
　下図のような空所がある。

この空所に、数字の１から６までが順に並んでいる。

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

（ルール）　１．　１→２→３→４→５→６→１→２→・・・　と数字の順番に、数字を、数字の入
　　　　　　　　　っていない空所のどちらかに移動する。

　　　　　　　２．　１回の操作で動かせる数字は、ひとつだけとする。

このとき、次のように数字を並べ替えるには、最低何回の操作が必要であろうか？

　この問題について、当ＨＰがいつもお世話になっているＨＮ「らすかる」さんが、数字が幾つ
あっても解があることを次のように示された。（平成２２年６月２６日付け）

　以下で、空所を数字の「０」で表すことにする。

　（１）数字の個数が偶数個の場合

　　　たとえば、　「００１２３４５６」について、「１」と「２」を入れ替える操作

　　　　１２３４５６００　←　１〜６まで２マスずらす

　　　　３４５６００１２　←　１と２は６マス、３〜６まで２マスずらす

　　　　５６００１２３４　←　１と２は２マス、３と４は６マス、５と６は２マスずらす

　　　　００２１３４５６　←　１を１マス、２を３マス、３と４は２マス、５と６は６マスずらす

　（２）数字の個数が奇数個の場合

　　　たとえば、　「００１２３４５」について、「１」と「２」を入れ替える操作

　　　　１２３４５００　←　１〜５まで２マスずらす

　　　　３４５００１２　←　１と２は５マス、３〜５まで２マスずらす

　　　　４５００１２３　←　１と２は１マス、３は５マス、４と５は１マスずらす

　　　　００２１３４５　←　１を１マス、２を３マス、３は２マス、４と５は５マスずらす

　上記のようにすれば、任意の２マスを入れ替えることが出来るので、必ず解にたどり着く
ことができる。

（コメント）　なるほど、合点！

　さらに、らすかるさんは、ｎ≦１１ の最短手数も調べられた。

　らすかるさんによれば、この数列は数列サイトにはなく、増加数列かどうかも分からない
とのこと。

　上記の範囲では、　(最短手数)＝ｎ（ｎ＋１）/２−Ａ

　　　　ただし、ｎ が奇素数のとき、 Ａ＝（ｎ−１）/２

　　　　　　　　　ｎ が指数 ｋ の累乗数のとき、 Ａ＝４（ｋ−１）　あるいは　Ａ＝２^ｋ

　　　　　　　　　その他の場合、 Ａ＝０

が成り立っているが、この先も成り立つかどうかはまったく不明とのことである。

（コメント）　ｎ＝６　のときの最短手数が「２１手」とのことなので、挑戦してみました！　　　　　　

　このような機会を与えていただいた、らすかるさんに感謝します。


　当ＨＰがいつもお世話になっているＨＮ「ＧＡＩ」さんが、ｎ＝５、６、７ の場合について、手順
を示された。（平成２２年６月２７日付け）

（コメント）　ＧＡＩ さん、ありがとうございます。ｎ＝６ の場合について、私のものと微妙に違
　　　　　　うので、解も一通りには決まらないことが分かりました！（当たり前かな．．．？）

　この問題に関連して、ＦＮさんが新しい記法を考えられた。（平成２２年６月２８日付け）

　１から順に、２、３、・・・、ｎ を移動する ｎ 手をまとめて、１巡と呼ぶことにし、局面ＡからＢ

に１巡で移ることを、「 Ａ⇒Ｂ 」で、１手で移るのを、「 Ａ→Ｂ 」で書くことにする。

　ｎ＝２、３、４、５、６、７　の手順の１つを、この記法で書いてみると次のようになる。

ｎ＝２　0012　⇒　0120　→　0021

ｎ＝３　00123　⇒　12300　→→　00321

ｎ＝４　001234　⇒　124300　→→　004321

ｎ＝５　0012345　⇒　1243500　⇒　2354010　→→→　0054321

ｎ＝６　00123456　⇒　12435060　⇒　23540106　⇒　30654210　→→→　00654321

ｎ＝７　001234567　⇒　123456070　⇒　234507106　⇒　347650210　→→→→　007654321


　らすかるさんより、ｎ＝８ のときの手順を頂いた。（平成２２年６月２８日付け）

0012345678　⇒　1235460780　⇒　2376501804　⇒　3487652010　→→→→　0087654321

（コメント）　ＦＮさんの記法で見通しよくなりました_ネ！

　ＧＡＩ さんが、「根性？」で、ｎ＝９ のときの手順を導かれた。（平成２２年６月２９日付け）

ｎ＝９　00123456789　⇒　12354607890　⇒　23765018904

　　　　　　⇒　34876520019　⇒　45987632100　→→→→→　00987654321

　さらに、らすかるさんが、ｎ＝１０、１１、１２ の手順を導かれた。（平成２２年６月２９日付け）

ｎ＝１０
　　　　　00123456789A　⇒
　　　　　1235406789A0　⇒
　　　　　237651089A04　⇒
　　　　　3487621900A5　⇒
　　　　　45987630210A　⇒
　　　　　50A987643210　→→→→→
　　　　　00A987654321

ｎ＝１１
　　　　　00123456789AB　⇒
　　　　　123546B789A00　⇒
　　　　　234657090AB81　⇒
　　　　　3457602A1B098　⇒
　　　　　45698730201AB　⇒
　　　　　56BA987143200　→→→→→→
　　　　　00BA987654321

ｎ＝１２
　　　　　00123456789ABC　⇒
　　　　　1234657C89AB00　⇒
　　　　　234576A090BC18　⇒
　　　　　34568702A1C09B　⇒
　　　　　45A798630201BC　⇒
　　　　　56CBA987143200　→→→→→→
　　　　　00CBA987654321

　らすかるさんによれば、ｎ＝１２の場合に６６手が最短であることが証明できたとのこと。
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　（平成２２年６月３０日付け）

（証明）　もし、ｎ＝１２が、６５手で出来たとすると、

　　　　　00123456789ABC⇒
　　　　　QRXXXXSTUVWXYZ⇒
　　　　　QRXXXXSTUVWXYZ⇒
　　　　　QRXXXXSTUVWXYZ⇒
　　　　　QRXXXXSTUVWXYZ⇒
　　　　　MNCBA9876PXXL0＋５手

　の形になる。（Ｌ、Ｍ、Ｎ、Ｐ〜Ｚは以降の説明のための記号である）

　　Ｍ、Ｎは５以下なので、Ｍ、Ｎ、Ｑ、Ｒの範囲内に少なくとも一つの０がなければならない。

　また、Ｐ≠０　のとき、Ｓ〜Ｚの各列には少なくとも一つの０が必要である。

　　Ｐ≠０　のとき

　　　２行目〜５行目に存在する０の個数は８個なので、Ｓ〜Ｚの各列にちょうど一つずつの

　　０が必要。Ｑ、Ｒは０に出来ないので、ＭかＮのいずれかが０である。

　　　すると、Ｌは１と決まるので、Ｙの中にもう一つ０が必要となるが、それは不可能。

　　Ｐ＝０　のとき

　　　Ｍ、Ｎは０に出来ないので、ＱかＲのうち少なくとも一つに０が入る。

　　また、Ｓ〜Ｕ、Ｗ〜Ｚにそれぞれ０が少なくとも一つ必要であるが、Ｌは１なので、Ｙには

　　０が少なくとも２つ必要となる。このとき、２行目〜５行目に０が９個必要となり、不可能。

　　　６１手〜６４手は、６行目のＰＸＸＬの部分が固定されるだけなので出来ない。

　　　６０手は、Ｓ〜Ｚの範囲に０が１０個必要となって不可能。

　　　５９手は、

　　　　　00123456789ABC⇒
　　　　　XXXXXXSTUVWXYZ⇒
　　　　　XXXXXXSTUVWXYZ⇒
　　　　　XXXXXXSTUVWXYZ⇒
　　　　　XXCXXXSTUVWXYZ＋11手

　　のようになるが、５行目は右から順に、０、１以下、２以下、…、Ａ以下でなければならな

　　いことを考慮すると、Ｓ〜Ｚの範囲に０が少なくとも１０個必要となり、不可能。

　　　同様に、５８手以下も不可能となり、結局６６手が最短となる。　（証終）


　これまでの最短手数をまとめると、

となる。

　ＦＮさんやらすかるさんの探究の結果、上記の範囲では、

　ｎ が奇数のとき、　(最短手数)＝（ｎ²＋１）/２

　　　　（実際に、　ｎ＝３　→　(最短手数)＝５　、ｎ＝５　→　(最短手数)＝１３　、
　　　　　　　　　　　ｎ＝７　→　(最短手数)＝２５　、ｎ＝９　→　(最短手数)＝４１　、
　　　　　　　　　　　ｎ＝１１　→　(最短手数)＝６１　、　・・・・・・・・　　）

　　　※　ＦＮさんによれば、「１〜ｎ を動かす操作を（ｎ−１）/２回行って、後ろの（ｎ−１）/２
　　　　個を正しい位置に入れ、前の（ｎ＋１）/２個を最後に入れて完成」ということで、
　　　　　　　　　（ｎ−１）/２×ｎ＋（ｎ＋１）/２＝（ｎ²＋１）/２
　　　　が導かれるとのこと。（平成２２年６月２７日付け）

　ｎ＝４ｋ （ｋ＝１、２、３、・・・）のとき、　(最短手数)＝ｎ（ｎ−１）/２

　　　　（実際に、　ｎ＝４　→　(最短手数)＝６　、ｎ＝８　→　(最短手数)＝２８　、
　　　　　　　　　　　ｎ＝１２　→　(最短手数)＝６６　、　・・・・・・・・　　）

　ｎ＝４ｋ＋２ （ｋ＝０、１、２、・・・）のとき、　(最短手数)＝ｎ（ｎ＋１）/２

　　　　（実際に、　ｎ＝２　→　(最短手数)＝３　、ｎ＝６　→　(最短手数)＝２１　、
　　　　　　　　　　　ｎ＝１０　→　(最短手数)＝５５　、　・・・・・・・・　　）

が成り立っている。（ｎ≧１３ についても成り立つかどうかは不明！）

　らすかるさんによれば、一般に、

　ｎ が奇数のとき、　（ｎ²＋１）/２　手未満では不可能

　ｎ＝４ｋ （ｋ＝１、２、３、・・・）のとき、　ｎ（ｎ−１）/２　手未満では不可能

　ｎ＝４ｋ＋２ （ｋ＝０、１、２、・・・）のとき、　ｎ（ｎ＋１）/２　手未満では不可能

ということが証明されたとのことである。（平成２２年６月３０日付け）

（証明）　ｎ＝４ｋ　の場合（行数は、２ｋ、列数は、４ｋ＋２）

　２行目〜２ｋ行目（つまり、２行目以降全部）の範囲において、１列目〜２列目（下図Ｒの

範囲）で少なくとも１個、ｋ＋４列目〜３ｋ＋３列目（下図Ｓの範囲）は各列少なくとも１個ず

つ、３ｋ＋４列目〜４ｋ＋２列目（下図Ｔの範囲）は各列少なくとも２個ずつなので、合計す

ると、最小　１＋２ｋ＋２（ｋ−１）＝４ｋ−１個となるが、２行目〜２ｋ行目の０の個数は、

４ｋ−２個なので矛盾。

（ｋ＝４　の場合の参考図）
　　　　　00123456789ABCDEFG⇒
　　　　　RRXXXXXSSSSSSSSTTT⇒
　　　　　RRXXXXXSSSSSSSSTTT⇒
　　　　　RRXXXXXSSSSSSSSTTT⇒
　　　　　RRXXXXXSSSSSSSSTTT⇒
　　　　　RRXXXXXSSSSSSSSTTT⇒
　　　　　RRXXXXXSSSSSSSSTTT⇒
　　　　　RRGFEDCBA98SSSSTTT＋０〜７手

　ｎ＝４ｋ＋１　の場合（行数は、２ｋ＋１、列数は、４ｋ＋３）

　２行目〜２ｋ＋１行目（つまり、２行目以降全部）の範囲において、

　（１）　２ｋ巡＋ｋ〜２ｋ手で出来ないことの証明

　　　１列目〜２列目（下図Ｒの範囲）で少なくとも１個、ｋ＋４列目〜３ｋ＋３列目（下図Ｓの

　　範囲）は各列少なくとも１個ずつ、３ｋ＋４列目〜４ｋ＋３列目（下図Ｔの範囲）は各列少

　　なくとも２個ずつなので、合計すると、最小　１＋２ｋ＋２ｋ＝４ｋ＋１個となるが、２行目〜

　　２ｋ＋１行目の０の個数は４ｋ個なので矛盾。

（ｋ＝４　の場合の参考図）
　　　　　00123456789ABCDEFGH⇒
　　　　　RRXXXXXSSSSSSSSTTTT⇒
　　　　　RRXXXXXSSSSSSSSTTTT⇒
　　　　　RRXXXXXSSSSSSSSTTTT⇒
　　　　　RRXXXXXSSSSSSSSTTTT⇒
　　　　　RRXXXXXSSSSSSSSTTTT⇒
　　　　　RRXXXXXSSSSSSSSTTTT⇒
　　　　　RRXXXXXSSSSSSSSTTTT⇒
　　　　　RRHGFEDCBA9SSSSTTTT＋４〜８手

　（２）　２ｋ巡＋０〜ｋ−１手で出来ないことの証明

　　　１列目〜２列目（下図Ｒの範囲）で“各列”少なくとも１個、ｋ＋４列目〜３ｋ＋４列目（下

　　図Ｓの範囲）は各列少なくとも１個ずつ、３ｋ＋５列目〜４ｋ＋３列目（下図Ｔの範囲）は各

　　列少なくとも２個ずつなので、合計すると、最小　２＋（２ｋ＋１）＋２（ｋ−１）＝４ｋ＋１個

　　となるが、２行目〜２ｋ＋１行目の０の個数は４ｋ個なので矛盾。

（ｋ＝４　の場合の参考図）
　　　　　00123456789ABCDEFGH⇒
　　　　　RRXXXXXSSSSSSSSSTTT⇒
　　　　　RRXXXXXSSSSSSSSSTTT⇒
　　　　　RRXXXXXSSSSSSSSSTTT⇒
　　　　　RRXXXXXSSSSSSSSSTTT⇒
　　　　　RRXXXXXSSSSSSSSSTTT⇒
　　　　　RRXXXXXSSSSSSSSSTTT⇒
　　　　　RRXXXXXSSSSSSSSSTTT⇒
　　　　　RRHGFEDCBA987654TTT＋０〜３手

　ｎ＝４ｋ＋２　の場合（行数は、２ｋ＋２、列数は、４ｋ＋４）

　　２行目〜２ｋ＋２行目（つまり２行目以降全部）の範囲において、１列目〜２列目（下図Ｒ

　の範囲）で“各列”少なくとも１個ずつ、ｋ＋４列目〜３ｋ＋４列目（下図Ｓの範囲）は各列少

　なくとも1個ずつ、３ｋ＋５列目〜４ｋ＋４列目（下図Ｔの範囲）は各列少なくとも２個ずつな

　ので、合計すると、最小　２＋（２ｋ＋１）＋２ｋ＝４ｋ＋３個となるが、２行目〜２ｋ＋２行目

　の０の個数は４ｋ＋２個なので矛盾。

（ｋ＝４　の場合の参考図）
　　　　　00123456789ABCDEFGHI⇒
　　　　　RRXXXXXSSSSSSSSSTTTT⇒
　　　　　RRXXXXXSSSSSSSSSTTTT⇒
　　　　　RRXXXXXSSSSSSSSSTTTT⇒
　　　　　RRXXXXXSSSSSSSSSTTTT⇒
　　　　　RRXXXXXSSSSSSSSSTTTT⇒
　　　　　RRXXXXXSSSSSSSSSTTTT⇒
　　　　　RRXXXXXSSSSSSSSSTTTT⇒
　　　　　RRXXXXXSSSSSSSSSTTTT⇒
　　　　　RRIHGFEDCBA9SSSSTTTT＋０〜８手

　ｎ＝４ｋ＋３　の場合（行数は、２ｋ＋２、列数は、４ｋ＋５）

　　２行目〜２ｋ＋２行目（つまり２行目以降全部）の範囲において、１列目〜２列目（下図Ｒ

　の範囲）で少なくとも１個、ｋ＋４列目〜３ｋ＋５列目（下図Ｓの範囲）は各列少なくとも１個

　ずつ、３ｋ＋６列目〜４ｋ＋５列目（下図Ｔの範囲）は各列少なくとも２個ずつなので、合計

　すると、最小　１＋（２ｋ＋２）＋２ｋ＝４ｋ＋３個となるが、２行目〜２ｋ＋２行目の０の個数

　は４ｋ＋２個なので矛盾。

（ｋ＝４　の場合の参考図）
　　　　　00123456789ABCDEFGHIJ⇒
　　　　　RRXXXXXSSSSSSSSSSTTTT⇒
　　　　　RRXXXXXSSSSSSSSSSTTTT⇒
　　　　　RRXXXXXSSSSSSSSSSTTTT⇒
　　　　　RRXXXXXSSSSSSSSSSTTTT⇒
　　　　　RRXXXXXSSSSSSSSSSTTTT⇒
　　　　　RRXXXXXSSSSSSSSSSTTTT⇒
　　　　　RRXXXXXSSSSSSSSSSTTTT⇒
　　　　　RRXXXXXSSSSSSSSSSTTTT⇒
　　　　　RRJIHGFEDCBASSSSSTTTT＋０〜９手
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　（証終）

　ＦＮさんが、らすかるさんの証明を参考にして、ｎ＝１３のときの証明を、ｎ＝２ｋ＋１への一
般化を意識しながら試みられた。（平成２２年６月３０日付け）

　ｎ＝１３のとき、６巡＋６手以下では不可能であることの証明

６巡＋１〜６手で可能であるとする。

　　　　　00123456789ABCD⇒
　　　　　RRXXXXSSSSSSSSS⇒
　　　　　RRXXXXSSSSSSSSS⇒
　　　　　RRXXXXSSSSSSSSS⇒
　　　　　RRXXXXSSSSSSSSS⇒
　　　　　RRXXXXSSSSSSSSS⇒
　　　　　MMDCBA987JJJKL0＋１〜６手

　まず、６巡が終わった後、６手以内で完成するために、7以上は正しい位置に入っていなけ

ればならないから、最終行の「DCBA987」は確定する。

　また、次の手で、「1」が正しい位置(最後)に入るために、最右端は「0」である。

　当然ながら、最終行の「DCBA987」以外は、「6」以下である。

各行に、「0」が２つあるが、それを除いて各数は１つ上の数より大きい。

(1から順に置いていくから、１は0の下しか置けないし、2は0か1の下しか置けない・・・)

　このことから、Ｓの列は各列に少なくとも1つ「0」がなければならない。

もしそうでないとすると、5の列で考えると5より大きい数を取っていって６番目が9。これは無

理で、他はよりきつい。Ｓは９列あるから、「0」が少なくとも９個あることになる。

　一方、各行で２個で、５行だから、「0」は全部で１０個である。

(ｎ＝１２のときと違って、１だけ差がある)　もちろん、２行目から６行目を考えている。

Ｍは6以下だから、少なくとも一方のＭは、5以下。従って、Ｍが２つとも0でないとすると上と

同様に考えて、Ｒの２列のうち少なくとも一方に0がなければならない。

　Ｌ＝１　のとき、Ｃより大きいのはＤよりないから、Ｃの下またはその下が「0」であるが、さら

にもう1個、この列に「0」がないと、Ｌ＝１にはなれない。

　従って、このとき、Ｌの列に「0」は少なくとも２個ある。

同様に考えて、Ｋ＝１、２　のとき、Ｋの列に「0」が少なくとも２個ある。

　３つの条件　「ＭＭはともに0でない」　「Ｌは１」　「Ｋは1または2」　を考える。

このうちの２つが成り立てば、「0」は１１個以上となって矛盾である。

従って、このうちのせいぜい1つしか成り立たない。即ちこれらの否定が２つ以上成り立つ。

Ｌの位置には最終的に、「2」が入ることになるから、Ｌはそれより小さい「0」か「1」しかない。

同様に、Ｋは、「0」か「1」か「2」しかない。

　ということで、上の３つの条件の否定は、「ＭＭの一方は0」　「Ｌは0」　「Ｋは0」となる。

このうちの2つ以上が成り立たねばならないが、それは不可能である。

なお、6巡＋0手や5巡＋数手で不可能なことも容易に示される。（証終）


　ＧＡＩ さんが、ｎ＝１０、１１、１２、１３　の場合の手順を見出された。
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　（平成２２年６月３０日、７月１日付け）

ｎ＝１０
　　　　　00123456789A　⇒
　　　　　1263450789A0　⇒
　　　　　237450189A06　⇒
　　　　　3487652A0019　⇒
　　　　　40987650213A　⇒
　　　　　51A987643200　→→→→→
　　　　　00A987654321

ｎ＝１１
　　　　　00123456789AB　⇒
　　　　　1273456089AB0　⇒
　　　　　238560719AB04　⇒
　　　　　34987602AB015　⇒
　　　　　45A987630012B　⇒
　　　　　56BA987413200　→→→→→→
　　　　　00BA987654321

ｎ＝１２
　　　　　00123456789ABC　⇒
　　　　　1234657C89AB00　⇒
　　　　　234576A090BC18　⇒
　　　　　34568702A1C09B　⇒
　　　　　45A798630201BC　⇒
　　　　　56CBA987143200　→→→→→→
　　　　　00CBA987654321

ｎ＝１３
　　　　　00123456789ABCD　⇒
　　　　　1283456709ABCD0　⇒
　　　　　2394568A1BCD007　⇒
　　　　　34A9670B2CD0158　⇒
　　　　　45BA98703D0126C　⇒
　　　　　56CBA987401230D　⇒
　　　　　67DCBA985243010　→→→→→→→
　　　　　00DCBA987654321

（コメント）　ｎ＝１３ のとき、８５手で、らすかるさんの結果により、これが最短手数となる。

　このことから、これまでの最短手数をまとめると、

となる。

　ＦＮさん、らすかるさん、ＧＡＩ さんのご尽力により、このパズルも非常な深化を遂げたが、
ここで、ＦＮさんが、

　冒頭の問題(ｎ＝５のとき)で、１３手が最小である

ことの証明を、当初の問題に即して与えられた。（平成２２年７月１日付け）

（証明）　まず、５は動かないといけないから、５手はかかる。そうすると、３は一度動いてか

　らもとに戻らないといけないから、最低８手は必要。

　　８手以上１２手以下の何手かでできると仮定する。

　最初と５手目、１０手目の直後を書く。ただし、８手や９手でできるときは10手目はないか

　ら最終手とする。１３手目以降がないから、１０手目(or最終手)の段階で、「　５　４　３　」

　は正しい位置にきている。

　５は最後に動かすから、Ｃは空である。Ａに、１、２、３はこれない。Ａに４や５がくると、そ

の下に３はこれない。従って、Ａも空である。

　Bは、５か空しかないが、空はありえないから、Ｂは５である。

そうなると、Ｄは空しかないので、１０手以内でできることはありえない。

　すなわち、１１手か１２手の可能性が残る。

わかった所を書きこむと、

　上表で、Ｉ は空でなければならない。そうすると、Ｇ、Ｈの一方は１。従って、Ｅ、Ｆの一方は

空となるが、これはあり得ない。　（証終）

　さらに、ＦＮさんは、この問題について、新たな端緒を開かれた。（平成２２年７月１日付け）

　冒頭の問題の最短手数は１３手であるが、最短手数を与える手順は何通りあるか？

　ただし、最初に空所２ヶ所を逆に入れたものは同じとみなすことにする。初手は１を空所
に入れるしかないが、左に入れるとしておく。

　この問題に対して、らすかるさんが解を示された。（平成２２年７月２日付け）

となる。

　らすかるさんの示された結果により、ｎ＝５ の場合は手順が２通りあるが、その具体的な
手順を、ＦＮさんが求められた。（平成２２年７月２日付け）

（求め方）　まず、１１手目以降は指定席に置くだけの必然手なので、１０手目(２巡目)まで

　で考えれば十分。ｎ＝５　の場合、

　　　　　0012345　⇒
　　　　　RRXXSST　⇒
　　　　　RR54SST　→→→
　　　　　0054321

　必然的に、Ｔは２つとも０。Ｓの列に少なくとも１つ０があるが、そうすると、０の個数は４以

上となり、従って、Ｓの列には０がちょうど１つ、ＲやＸの列には、０はなしとなる。

　左の０の下のＲは１との約束なので、上のＲＲは「 １ ２ 」、下のＲＲは「 ２ ３ 」しかない。

２の下のＸは３しかない。これまでのところを書くと

　　　　　0012345　⇒
　　　　　12X3SS0　⇒
　　　　　2354SS0　→→→
　　　　　0054321

　１の下のＸは、４、５、０　しかないが、０はだめで、５もだめだから、４しかない。

残ったＳの所は、各行、各列に０が１個だから、「 ０　Ｓ 」か「 Ｓ　０ 」しかない。

残った所に残った数字を入れて、上に書いた２つになる。

（コメント）　ＦＮさんの説明で、考え方の基本が段々分かってきたような気がします．．．。


　ＦＮさんによれば、最短手数の手順の個数を考えようとしたのは最短手数の手順の存在
の証明をするためにどの程度ありそうかの感じをつかむためだったとのこと。

　らすかるさんの証明にあるように、ｎ を４で割った余りによって状況が微妙に変わります。
ｎ＝５は、ｎ＝４ｋ＋１のパターンなので、まずこのパターンから考えてみたいと思う。
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　（ＦＮさん　平成２２年７月２日付け）

　このときの最短手数は、２ｋ巡２ｋ＋１手である。いきなり一般の場合は難しいので、まず
ｋ＝２　即ち、ｎ＝９のときを考える。

　　　　　00123456789
　　　　　RRXXXSSSSTT
　　　　　RRXXXSSSSTT
　　　　　RRXXXSSSSTT
　　　　　RR9876SSSTT

　ｎ＝５のときと同様に、0は、ＳとＴで使い切る。従って、Ｓ列には、0がちょうど１個ずつで、
Ｒ列Ｘ列にはない。このことからＲＲは決まる。また、3の列も決まる。9の列の２つの0も決ま
る。このあたりは、ｎ＝４ｋ＋１で成り立つ。

　　　　　00123456789
　　　　　12XX4SSSST0
　　　　　23XX5SSSSTT
　　　　　34XX6SSSSTT
　　　　　459876SSST0

　もちろん、ｎ＝９のときに最短手数の手順があることはすでにわかっていて、らすかるさん
によると、４０８２通りもあるとのこと。

　従って、その手順を作るだけでは意味がなく、ｎ＝４ｋ＋１のときに一般化できるようなもの
を作らないといけない。

　上記のＦＮさんの考察を受けて、ＨＮ「攻略法」さんが、具体的な解の手順を示された。
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　（平成２２年７月２９日付け）

　Ｎによって、一般に、最少手数 Ｍ の計算

・Nが奇数なら、M=(N²+1)/２

・Nが偶数で、N=４ｋ型　なら、M=(N−１)N/２

　　　　　　　　　N=４ｋ＋２型　なら、M=N(N＋１)/２

手順は、INT(Ｍ/Ｎ)巡＋MOD(Ｍ，Ｎ)手と簡潔に記述できる。（以下この表記とする）

手順は、次の２つのパターンに大別できる。

■奇数、偶数４ｋ型の場合　※下記のStep6まで
　N= 24 M= 276
　 　　　　　　　　　　　　xrs　　　　 t 　　w
　 ZZXXXXXXXXXXXXYYYYYYYYYYYY
　 0 0+123456789ABCDEFGHIJKLMNO {}　　※ + は０の意、. は未定
　 24 12E3456789ABCD+FGHIJKLMNO0 {}
　 48 23FE56789ABCD+1GHIJKLMNO0. {4}
　 72 34GFE789ABCD+52HIJKLMNO01. {6}
　 96 45HGFE9ABCD+763IJKLMNO012. {8}
　 120 56IHGFEBCD+9874JKLMNO0123. {A}
　 144 67JIHGFED+BA985KLMNO0.234. {1C}
　 168 78KJIHGFEDCBA960MNO+1.345. {2L}
　 192 89LKJIHGFEDCBA71NO+32.056. {4M}
　 216 9AMLKJIHGFEDCB82O+543.107. {6N}
　 240 ABNMLKJIHGFEDC93+7654.210. {8O}
　 264 BCONMLKJIHGFEDA4987650321+ {}
　+12手

■偶数４ｋ＋２型の場合
　N= 26 M= 351
　 　　　　　　　　　　　　　rs 　　　　　　　　 w
　 ZZXXXXXXXXXXXXXYYYYYYYYYYYYY
　 0 0+123456789ABCDEFGHIJKLMNOPQ {}
　 26 12E3456789ABCD+FGHIJKLMNOPQ0 {}
　 52 23FE56789ABCD+1GHIJKLMNOPQ0. {4}
　 78 34GFE789ABCD+52HIJKLMNOPQ01. {6}
　 104 45HGFE9ABCD+763IJKLMNOPQ012. {8}
　 130 56IHGFEBCD+9874JKLMNOPQ0123. {A}
　 156 67JIHGFED+BA985KLMNOPQ01234. {C}
　 182 78KJIHGFEDCBA960MNOPQ+12345. {L}
　 208 89LKJIHGFEDCBA7.NOPQ+103456. {2M}
　 234 9AMLKJIHGFEDCB8.OPQ+3210567. {4N}
　 260 ABNMLKJIHGFEDC9.PQ+54321078. {6O}
　 286 BCONMLKJIHGFEDA.Q+765432109. {8P}
　 312 CDPONMLKJIHGFEB.+9876543210. {AQ}
　 338 D0QPONMLKJIHGFECBA987654321+ {}
　+13手

★パターンの生成（概要）

　　数字列を、ZZXXXXYYYYに分ける。

　Z並びは２個、Y並びはMOD(Ｍ，Ｎ)個、X並びは(N-(Y並びの個数))個となる。

　また、巡回数を ｊ 、X並びの最小値を ｖ＝N−ｊ＋１　とする。

例　Ｎ＝９　の場合、Ｍは４１手、Ｘは４個、Ｙは５個、ｊ は４、ｖ は６となる。

(Step　１) 巡回列
　Z列を、00,12,23,34,45,56,…とする。ただし、４ｋ＋２型（N=6,10,14,18,22,…）の場合は、Z並
びの(j)(j+1)部分を(j)(0)に置き換える。

例　Ｎ＝９　の場合
　　ZZXXXXYYYYY
　0 00123456789
　9 12xxxxyyyyy
18 23xxxxyyyyy
27 34xxxxyyyyy
36 45xxxxyyyyy

例　Ｎ＝１０　の場合
　　ZZXXXXXYYYYY
　0 00123456789A
10 12xxxxxyyyyy
20 23xxxxxyyyyy
30 34xxxxxyyyyy
40 45xxxxxyyyyy
50 50xxxxxyyyyy

(Step ２) 降順列
　巡を重ねることで、Ｘ並びを降順に１つずつ揃えて整列させる。v が対角線に並ぶ。

例　Ｎ＝９　の場合
　　ZZXXXXYYYYY
　0 00123456789
　9 126xxxyyyyy
18 2376xxyyyyy
27 34876xyyyyy
36 459876yyyyy

(Step ３) ２つの０の位置を仮定する。
　X並びに、１巡(v−１)列から左下斜めに向かって、先のX並びの降順に重なるまで０を記
入する。
　Y並びに、１巡右端列から左下斜めに向かって、(最終行−１)行まで０を記入する。
　s並び（s列）を、v列に設ける。その終端（X並びの０が、先のX並びの降順に重なる行）を
０とする。
　Y並びに、最終行右端列から左上斜めに向かって、s並びの終端１つ前まで０を記入する。

例　Ｎ＝９　の場合
　　　　　　　rs
　　ZZXXXXYYYYY
　0 00123456789
　9 ZZXxxx0syy0
18 ZZXXx0ysy0y
27 ZZXXXxy+0yy　←終端
36 ZZXXXXyyyy+　※大文字は既に数字が確定されている

(Step ４) r並び（r列）
　r並びを、(v−１)列に設ける。0,1,2,3,4,…とする。（Z並びの数字と連続させる）
　ただし、４ｋ＋２型の場合、最終行でX並びと重なるので上書きしない。

例　Ｎ＝９　の場合
　　　　　　　rs
　　ZZXXXXYYYYY
　0 00123456789
　9 ZZXxxx0syy0
18 ZZXXx01sy0y
27 ZZXXXx2+0yy
36 ZZXXXX3yyy+　※大文字は既に数字が確定されている

(Step ５) 最終行（最終巡回行）
　４ｋ型の場合、X並び（r並びの１つ前）が埋まっていないので、（降順列で）充填する。

　まず、Y並びを降順列で埋める。ただし、４ｋ＋２型以外の場合は、未使用の０を右端から
INT(j/2)の位置に当てはめる　→ t並び（t列）
　　s並びは、取り除いた数字が入れる
　と補正する。

例　Ｎ＝９　の場合
　　　　　　　rs　　 t
　　ZZXXXXYYYYY
　0 00123456789
　9 ZZXxxx0syy0
18 ZZXXx0Rsy0y
27 ZZXXXxR+0yy
36 ZZXXXXR120+　※大文字は既に数字が確定されている

(Step ６) 昇順列、降順列で埋める
　０に向かって（矢印の向きに）昇順列、降順列で埋めていく。

　　　

　以上の操作で、s並びの下、t並び、w並び（右端列）を除いてすべて埋まる。

例　Ｎ＝９　の場合
　　　　　　　rs 　tw
　　ZZXXXXYYYYY
　0 00123456789 {}
　9 12634507890 {}
18 2376501890y {4}
27 348765200yy {19}
36 45987631200 {}

(Step ７) s並びの下、t並び、w並びを埋める。ほとんど自明である。　完成！！！


ちなみに、奇数（Ｎ＝４ｋ＋１）の場合

Ｎ＝１３
　0 0+123456789ABCD
13 12834567+9ABCD0
26 2398567+1ABCD04
39 34A987+52BCD016
52 45BA987630D+12C
65 56CBA98741+230D
78 67DCBA98524301+
+7手

Ｎ＝１７
　0 0+123456789ABCDEFGH
17 12A3456789+BCDEFGH0
34 23BA56789+1CDEFGH04
51 34CBA789+52DEFGH016
68 45DCBA9+763EFGH0128
85 56EDCBA98740GH+123F
102 67FEDCBA9851H+2304G
119 78GFEDCBA962+43510H
136 89HGFEDCBA73654021+
+9手

Ｎ＝２１
　0 0+123456789ABCDEFGHIJKL
21 12C3456789AB+DEFGHIJKL0
42 23DC56789AB+1EFGHIJKL04
63 34EDC789AB+52FGHIJKL016
84 45FEDC9AB+763GHIJKL0128
105 56GFEDCB+9874HIJKL0123A
126 67HGFEDCBA9850JKL+1234I
147 78IHGFEDCBA961KL+23045J
168 89JIHGFEDCBA72L+435106K
189 9AKJIHGFEDCB83+6547210L
210 ABLKJIHGFEDC9487650321+
+11手

Ｎ＝２５
　0 0+123456789ABCDEFGHIJKLMNOP
25 12E3456789ABCD+FGHIJKLMNOP0
50 23FE56789ABCD+1GHIJKLMNOP04
75 34GFE789ABCD+52HIJKLMNOP016
100 45HGFE9ABCD+763IJKLMNOP0128
125 56IHGFEBCD+9874JKLMNOP0123A
150 67JIHGFED+BA985KLMNOP01234C
175 78KJIHGFEDCBA960MNOP+12345L
200 89LKJIHGFEDCBA71NOP+230456M
225 9AMLKJIHGFEDCB82OP+4351067N
250 ABNMLKJIHGFEDC93P+65472108O
275 BCONMLKJIHGFEDA4+876593210P
300 CDPONMLKJIHGFEB5A987604321+
+13手

Ｎ＝２９
　0 0+123456789ABCDEFGHIJKLMNOPQRST
29 12G3456789ABCDEF+HIJKLMNOPQRST0
58 23HG56789ABCDEF+1IJKLMNOPQRST04
87 34IHG789ABCDEF+52JKLMNOPQRST016
116 45JIHG9ABCDEF+763KLMNOPQRST0128
145 56KJIHGBCDEF+9874LMNOPQRST0123A
174 67LKJIHGDEF+BA985MNOPQRST01234C
203 78MLKJIHGF+DCBA96NOPQRST012345E
232 89NMLKJIHGFEDCBA70PQRST+123456O
261 9AONMLKJIHGFEDCB81QRST+2304567P
290 ABPONMLKJIHGFEDC92RST+43510678Q
319 BCQPONMLKJIHGFEDA3ST+654721089R
348 CDRQPONMLKJIHGFEB4T+876593210AS
377 DESRQPONMLKJIHGFC5+A9876B43210T
406 EFTSRQPONMLKJIHGD6CBA987054321+
+15手

（コメント）　一つ一つ追って理解したいと思います。攻略法さんに感謝します。



　　　以下、工事中