円板の移動　 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　


　　　　左図のように、地面に柱が２本立っていて、その
　　　うちの左側の柱には、１から５までの番号のつけら
　　　れた円板が、上から番号順に積まれている。

　　　　いま、１回の操作で、上から、１枚または２枚の円
　　　板を、他の柱へ移動させる。ただし、２枚のときは、
　　　上下の順番は、そのままとする。

　　　　何回か操作をして、右側の柱に、円板が、上から
　　　順番に１から５まで並ぶようにしたい。
　　　　一体、何回の操作でできるであろうか？


（参考文献：ピーター・フランクル　著　中学生でも分かる　大学生にも解けない
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　数学問題集＜２＞　（日本評論社））

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

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

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

















（答）　１５回

　（２枚ずつ２回、１枚を１回移動させて、一方の柱の円板を全て他方の柱に移す。この操作
　　を、１セットとする。左側の柱より始めて、５セット目で、題意を満たす。）


　当ＨＰがいつもお世話になっているＨＮ「ＦＮ」さんが、上記の問題の一般化を考えられた。
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　（平成２２年８月５日付け）

　上記の問題で、１から５までになっているのを、ｎ を自然数として、１から ｎ までとする。

ｎ＝１、２　のときは、明らかに１手でできるから、ｎ≧３　とする。また、縦だと書きにくいので
横に書くことにする。

ｎ＝５の場合、初期状態は(12345,　)、完成形は(　,12345)である。

（追記）　令和５年５月１５日付け

　　　(12345,　)→(345,12)→(5,3412)→( ,53412)→(53,412)→(4153,2)→(24153, )→(153,24)
　　　→(3,1524)→( ,31524)→(31,524)→(5231,4)→(45231, )→(231,45)→(1,2345)→( ,12345)

　の１５手


ｎ＝５の場合の解答は１５手で長いから、ｎ＝３のときの手順を書いてみよう。

　　(123,　)→(3,12)→(　,312)→(31,2)→(231,　)→(1,23)→(　,123)
　　　※６手が最短であることの証明はできないが、多分最短だろう。

　さらに、括弧を書くのは面倒なので省略し、コンマの代わりに「0」にすると、上記の手順は

　　1230→3012→0312→3102→2310→1023→0123

と書ける。そこで、問題です。

（１）　まず、ｎ＝４　のときの手順を考えてください。

（解）　　12340→23401→40231→24031→02431→20431→43201→

　　　　32041→41320→13204→20134→12034→01234　　以上　１２手

（２）　次に、ｎ＝６、７、８あたりを考えてください。

（３）　そして、一般の ｎ で考えてください。

　最短であることの証明は難しいので考えないことにします。ｎ が奇数の場合は、５の場合
と同様にできそうです。偶数の場合はさてどうなるのでしょうか。

　この問題に対して、ＨＮ「攻略法」さんが解法の手順を考えられた。（平成２２年８月６日付け）

　●　ｎ が奇数の場合・・・次のまとまった手順で、左→右と右→左に移動させる。

　・12、34、45、…のように２枚ずつ移動する（ (ｎ-1)/2 回）

　・残り１枚を移動する（１回）

　この (ｎ+1)/2 手を「１巡」とする操作を、ｎ 回繰り返す。

　従って、総手数は ｎ(ｎ+1)/2 手。

例　ｎ＝７　のとき

　12345670→34567012→56703412→70563412→07563412→75063412→63750412→

41637502→24163750→16375024→37501624→50371624→05371624→53071624→

71530624→62715304→46271530→27153046→15302746→30152746→03152746→

31052746→52310746→74523106→67452310→45231067→23104567→10234567→

01234567　　以上　２８手

　この流れは、２枚を１枚と考えると、(正順,　)→ … →(逆順,　)→(　,正順)として解を得てい
る。ｎ が偶数の場合で、このような状態が存在するだろうか？

　攻略法さんが、ｎ が偶数の場合の手順を一般化された。（平成２２年８月６日付け）

　●　ｎ が偶数の場合・・・次のまとまった手順で、右または左に移動させる。

　・１番上の１枚を移動する（１回）

　・23、45、67、…のように２枚ずつ移動する。（ ｎ/2 回）

　　ただし、この操作の INT(ｎ/4) 回目の後に１枚戻す。（１回）

　この (ｎ+4)/2 手を「１巡」とする操作を、ｎ-1 回繰り返す。

　従って、総手数は (ｎ-1)(ｎ+4)/2 手。

　ＦＮさんからこの問題についての考え方をご教示頂きました。（平成２２年８月６日付け）

基本的な考え方は、次の通りです。

まず、ｎ が奇数の場合、例えば、ｎ＝５　の場合

　３手で、123450 を 053412 にします。これを、「0」を除いた部分だけ見れば、即ち、右側か
左側かは無視して、12345 がどの順に並んでいるかだけに注目すれば、12345 を 53412 に
してます。これを置換と見れば長さ５の巡回置換(15234)です。これの位数は５だから５回で
元に戻ります。そして、５回ということは右側にきてるので、３×５＝１５手で完成です。

次に、ｎ が偶数の場合、例えば、ｎ＝４　の場合は同様にすると、巡回置換(1423)が得られ
るが、これの位数は４だから、４回で元に戻る。４回では左側なので駄目。そこで、1つだけ
動かないようにして、長さ３の巡回置換を作ることを考えます。

　　　12340→23401→40231→24031→02431

これだと、3 が動いてなくて長さ３の巡回置換(124)になっています。だから、３回で元に戻
ります。３回だから右側なのでできています。
手数は、12340→・・・→02431４ が４手より、　４×３＝１２手です。

ｎ=6　のときの手順

　　　1234560→3456012→5603412→3560412→6035412→0635412

これだと、4 が動いていなくて長さ５の巡回置換(16235)になっています。
手数は、1234560→・・・→0635412 が５手より、　５×５＝２５手です。

ｎ=8　のときの手順

　123456780→345678012→567803412→356780412
　　　　　　　　　　　　　　　　　　　　　　　　　　　→678035412→806735412→086735412
これだと、5 が動いていなくて、長さ７の巡回置換(1826437)になっています。
手数は、123456780→・・・→086735412６ が６手より、　６×７＝４２手です。

ｎ＝２ｋ　のときは、ｋ＋２＝（ｎ＋４）/２手で長さ ｎ−１ の巡回置換が作れそうに思います。
だから、(ｎ＋４)(ｎ−１)/２手で、できそうな気がします。

　当ＨＰがいつもお世話になっているＨＮ「ＧＡＩ」さんも手順を考えられた。
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　（平成２２年８月６日付け）

n=6の場合　２５手

　1234560→3456012→5603412→3560412→6035412→0635412→6305412→5463012→

4630512→5146302→2514630→1463025→6301425→1630425→3016425→0316425→

3106425→6431025→4310625→6243105→5624310→2431056→3102456→2310456→

1023456→0123456


n=8の場合　４２手

　123456780→345678012→567803412→356780412→678035412→806735412→

086735412→860735412→738605412→386075412→753860412→417538602→241753860→

175386024→538601724→153860724→386015724→603815724→063815724→630815724→

816305724→163085724→851630724→728516304→472851630→285163047→516302847→

251630847→163025847→301625847→031625847→310625847→623105847→231065847→

652310847→846523107→784652310→465231078→523104678→452310678→231045678→

102345678→ 012345678


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

　ｎ＝４ｋ　の場合の攻略法さんの手順が確認できました。

　巡回置換 (1,4k-1,3,4k-3,･･･,2k-3,2k+3,2k-1,2k,2k+2,･･･,4,4k-2,2,4k) で、動かないのは
2k+1でした。奇数番目だけ偶数番目だけを別々に書けばそれぞれ

　1,3,5,7,･･･,2k-3,2k-1,2k+2,2k+4,･･･4k-2,4k　で、2k-1から2k+2だけが +3 です。

　4k-1,4k-3,4k-5,･･･,2k+3,2k,2k-2,2k-4,･･･4,2　で、2k+3から2kだけが -3 です。

長さ ｎ-1 の巡回置換だと確認されたから、(ｎ+4)(ｎ-1)/2手でできます。

N=4k+2も多分同様にできるのでしょう。これは省略。

　次に、最短手数かどうかですが、理論的に考えるのは困難なので全数チェックに挑戦しま
した。

　n=3　のときは、0123の順列は全部で24通りで、6手は最短でした。

　n=4　のときは、01234の順列は全部で120通り。さすがに手計算は無理なので、ExcelVBA
でプログラムを書いて調べました。

　n=4、5、6、7、8　については最短であることが確認できました。
（n=8 は2時間近くかかりました。)

　以上から、らすかるさんの結果（平成２２年８月８日付け）も含めて

　この表から、

　３≦ ｎ ≦１１　において、

　　ｎ が奇数のとき、　ｎ(ｎ＋１)/２手　、　ｎ が偶数のとき、　(ｎ＋４)(ｎ−１)/２手

　が最短手数である

ことが成り立つことになりますね。

　ところで、ｎ が偶数の場合に面白い現象がありました。n=8 の場合で書きます。

　012345678 の順列は、9!=362880通りあります。この362880通りのすべての状態に到達で
きるのですが、012345678 のみ42手かかり、それ以外の362879通りは、すべて41手以下で
到達できます。n=4、n=6 でも同じことが起こっています。

　ｎ が奇数のときは、このようなことは起こっていません。例えば、n=7のとき

　01234567 には、28手で到達できますが、28手以上かかる状態はたくさんあります。
65432107は32手かかります。

（コメント）　ＦＮさん、攻略法さん、らすかるさん、ＧＡＩ さん、ありがとうございます。こんなにも
　　　　　　豊富に数学的考察が加えられることに感動しました！


　攻略法さんから、状態の表現の仕方として次のような提案があった。
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　（平成２２年８月２２日付け）　

　したがって、先の表現 3456012 は、6543012 となる。

　ここで、数字の移動の効果を見てみる。

２つを右へ

　6543012 → 6503412 となるが、0と隣接する２つの数字に着目すれば、430 → 034 のよ
うに反転させる。
　言い換えれば、「4と0を交換する」ということになる。

１つを右へ

　6543012 → 6540312 となるが、0と隣接する１つの数字に着目すれば、30 → 03 のように
反転させる。
　言い換えれば、「3と0を交換する」ということになる。

２つを左へ

　6543012 → 6543210 となるが、0と隣接する２つの数字に着目すれば、012 → 210 のよう
に反転させる。
　言い換えれば、「2と0を交換する」ということになる。

１つを左へ

　6543012 → 6543102 となるが、0と隣接する１つの数字に着目すれば、01 → 10 のように
反転させる。
　言い換えれば、「1と0を交換する」ということになる。

また、開始の並びと終了の並びは、N＝６　の場合、6543210　、0123456　となる。

　以上により、これらは、「あみだくじ」（置換）で表現することができる。

ただ、通常と違って、

　・「隣接」と「１つ飛び」のいずれかで横線を引くことになる。

　・０を必ず移動させるように横線を引く。（任意の位置には引けない）

となる。

　このとき、円板の移動の問題は、『横線の数を最少にするあみだくじをつくる』という問
題に置き換えられる。

　あみだくじを作成する要領で解のパターンを手作業で見つけることができる。


　この攻略法さんの問題の言い換えに対して、ＦＮさんからのコメントです。
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　（平成２２年８月２１日付け）

　とてもいいアイデアという気がします。状態の表現の仕方として明らかにこの方が優れて
いますね。

　N＝６の場合であれば最初の形 6543210 を最終形 0123456 にする。許される操作は、
0と隣の交換または0と1つ離れた隣との交換のみ。


　この「円板の移動」の問題に関連して、攻略法さんが新しい問題を作られた。
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　（平成２２年９月２日付け）

蛙の整列１

　Ｎ匹の蛙が並んでいる。逆順に並べ替える手順を示せ。

　例　N＝４　の場合　1234_ → 4321_

　＜移動条件＞

　・隣の葉が空いていれば、そこに移動できる。　例. 12_34 → 1_234

　・他の１匹の蛙を挟んでその隣の葉が空いていれば、その１匹の蛙を飛び越えて移
　　動できる。
　　（１度に２匹以上の他の蛙を飛び越えることはできない）　例. 123_4 → 1_324

　・１枚の葉には、同時に２匹以上乗れない。

（解）

　回数について、

　Ｎが奇数の場合、　N(N＋３)/２−４　（ただし、N≧３）
　※奇数の場合の一般解は不明

　Ｎが偶数の場合、　N(N＋１)/２


蛙の整列２

　Ｎ匹の蛙が並んでいる。逆順に並べ替える手順を示せ。

ただし、終了時の空き位置が先頭にくるものとする。

　例　N＝４　の場合　1234_ → _4321

　＜移動条件＞

　・隣の葉が空いていれば、そこに移動できる。　例. 12_34 → 1_234

　・他の１匹の蛙を挟んでその隣の葉が空いていれば、その１匹の蛙を飛び越えて移
　　動できる。
　　（１度に２匹以上の他の蛙を飛び越えることはできない）　例. 123_4 → 1_324

　・１枚の葉には、同時に２匹以上乗れない。

（解）

　回数について、

　Ｎが奇数の場合、　Ｎ(N＋１)/２

　Ｎが偶数の場合、　（Ｎ−１）(N＋４)/２


　攻略法さんが、蛙の整列１について、別な視点で考えられた。（平成２２年９月３日付け）

　平面グラフをつくって、１周する巡回路（ハミルトン閉路、ハミルトン路）を考える。

（解）　偶数の場合、N手(N/2)巡 + (N/2)手・・・・・（N＋１）N/２手

　また、終了時の空き位置を先頭にした場合（蛙の整列２）

（解）　奇数の場合、N手(N+1)/2巡・・・・・（N＋１）N/２手

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

　円板の移動と蛙の整列が実質的に同じであるというのは大変面白いです。ついでに列車
の入れ替えも実質的に同じです。

列車が１を先頭に右向きに54321と並んで いる。これを右図のような引き込み線を利用 して右側に12345の順に並べよ。 　但し、一度に動かせるのは１台か２台とする。

　54321＿から１手で移れるのは、5432＿1か543＿12である。円板の移動を攻略法さんが

提案された記法で書けば、上から12345と並んだ状態は、54321＿であり、これから１手で

移れるのは5432＿1か543＿12である。

　円板の移動でも列車の入れ替えでも、654＿123から移れるのは、

　　65＿4123　、6＿45123　、6541＿23　、65421＿3

のどれかである。これが蛙の整列で許される操作と同じであることは容易にわかる。

即ち、３つとも＿とその隣の交換または＿と１つ離れた隣との交換が許される操作である。

許される操作が同じだという意味で円板の移動と列車の入れ替えと蛙の整列は実質的に

同じ問題と言えるが、最終的に作るべき形が違えば当然別の問題になる。

　「お茶の時間」の「円板の移動」は、54321＿を＿12345にせよであった。

　「蛙の整列」では、普通は、54321＿を12345＿にせよである。だから当然同じ問題ではな

い。「円板の移動」で54321＿を12345＿にせよという問題設定はもちろん可能である。

　54321＿を＿12345にするのを(A)型、54321＿を12345＿にするのを(B)型と呼ぶことに

する。5の場合で書いたが5をNにした形で考えよう。

　(A)型については、次の手数でできることは確認できている。

　　Nが奇数のとき、N(N＋１)/２手　、Nが偶数のとき、(N−１)(N＋４)/２手

そして最短ではないかと予想されている。らすかるさんによれば、N≦１１では正しい。

(B)型については、攻略法さんによると、

　　Nが偶数のとき、N(N＋１)/２手　、Nが奇数のとき、N(N＋３)/２−４手　(N≧３)
　　　（ただし、Nが奇数のときは一般解は不明とのこと。）

　Nが偶数のときは、比較的容易に確認できそうです。Nが奇数のときは私は全くわかりま
せん。面白いのは、(A)型ではNが奇数のときが比較的簡単でN(N+1)/2手、(B)型ではNが
偶数のときが比較的簡単でN(N+1)/2手であることです。

　最短であることが証明できるとすれば一番可能性があるのは(B)型でNが偶数のときでは
ないかと思います。

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

　上記で、「 54321＿を＿12345にするのを(A)型、54321＿を12345＿にするのを(B)型と
呼ぶことにする。」としましたが、もともとの「円板の移動」は、この形の(A)型なのでこのよう
にしましたが最初の形が逆順ぽいので攻略法さんが書かれている形のほうがいいかもしれ
ません。

　12345＿を＿54321にするのを(A)型、12345＿を54321＿にするのを(B)型とする。

もちろんどちらでも同じことですが。また、説明するにはアンダーバーの方がいいと思います
が定式化できてしまえば、0でいいかなと思います。すなわち、

　　　123450 を 054321 にするのを、(A)型　

　　　123450 を 543210 にするのを、(B)型

とする。

　許される操作は、0と隣の交換、0と1つ離れた隣との交換である。

(B)型のN＝６の場合の手順を書いておきます。

　　0:1234560
　　1:1234065
　　2:1204365
　　3:0214365
　　4:2014365
　　5:2410365
　　6:2416305
　　7:2416350

　これで、最後が 0 になり、前の6個の文字の置換は巡回置換(124653)である。これを３回
繰り返すと即ち３乗すると(16)(25)(34)になる。以上の操作により、「123456」は「654321」に
置換され、丁度、７×３＝２１手でできている。

　同様に、Nが偶数の場合は、N＋１回で最後が 0 で、前のN文字は巡回置換にできる。

これを、N/２回繰り返すと、位数は２であるがそれだけではなく、123･･･N を逆向けN･･･321
に並べ替えるものになっている。従って、N(N＋１)/２手でできる。


攻略法さんが新しい問題を考えられた。（平成２２年９月６日付け）

蛙の入れ替え　　２種類の蛙がＭ匹とＮ匹ずついる。(M+N+1)枚の葉の上に１匹ずつ、１つ
　　　　　　　　　　　空けて両側に分かれて対峙している。配置を入れ替える手順を示せ。

　例　 M=4、N=3の場合　　1111_222 → 222_1111

　移動条件
　　・隣の葉が空いていれば、そこに移動できる。　例　 11_22 → 1_122
　　・他の１匹の蛙を挟んでその隣の葉が空いていれば、その１匹の蛙を飛び越えて移動
　　できる。（１度に２匹以上の他の蛙を飛び越えることはできない）　例　 112_2 → 1_212
　　・１枚の葉には、同時に２匹以上乗れない。
　　・仲間の蛙を飛び越すことはできない。　例　 111_22 → 1_1122 は不可

ヒント　　…121212…のように交互に並ぶように移動させる。

答え
●移動回数

　飛び越さないで移動させるには、Ｍ匹の蛙に対してそれぞれＮ＋１回ずつ。
　同様に、Ｎ匹の蛙ではＭ＋１回。また、飛び越す回数はＭ＊Ｎ回である。
　したがって、M*N+M+N回（ = M*(N+1)+N*(M+1)-M*N ）となる。

●蛙の種類による移動の表現

●葉の位置による移動の表現

（コメント）　単純な円板の移動の問題から始まって、こんなに豊富な応用例があることに驚
　　　　　　いています。



　　以下、工事中！