◆東京都 藤本 さんからの解答
【問題１】
Ｒ→Ｋ→Ｈ→Ａ→Ｌ→Ｕ→
Ｒ→Ｏ→Ｈ→Ｋ→Ｒ→Ｏ→
Ｄ→Ｇ→Ｎ→Ｙ→Ｒ
【問題２】
イ→Ｔ→Ｉ→Ａ→Ｎ→Ｙ→
Ｕ→Ｑ→Ｉ→Ｔ→イ→Ｑ→
Ｆ→Ｊ→Ｗ→コ→イ
【おまけ】
ｎ が ３以上の場合可能
証明は 帰納法で簡単にできます。
証明の手順は 以下のようなものになります。
たとえば 問題２の ６×６の場合には、最初に
イ→Ｑ→Ｕ→ウ
と動かして スペースを （５，５）に移せば、問題１と同じ手順で
黒のナイトを （５，５）に持ってこれます。
そのとき スペースは、（４，３） または （３，４）にあります。
スペースが （４，３）のときは
ウ→Ｐ→Ｘ→イ→Ｑ→Ｕ→
ウ→Ｒ→Ｖ→ケ→Ｘ→イ→
Ｑ→Ｕ→ク→Ｗ→コ→イ
と動かせば 黒のナイトを（６，６）に移せます。
スペースが （３，４）のときも 同様の手順で
黒のナイトを（６，６）へ移動が可能です。
と、これらのことを ｎ と ｎ＋１ のチェス版について示せばよいわけです。
◆愛知県 Y.M.Ojisan さんからの解答
【問題１】
１７回
Ｎ→Ｅ→Ｈ→Ａ→Ｌ→Ｗ→
Ｎ→Ｅ→Ｈ→Ｑ→Ｎ→Ｅ→
Ｈ→Ｋ→Ｒ→Ｙ→Ｎ
【問題２】
１７回
イ→Ｑ→Ｉ→Ａ→Ｎ→Ｊ→
Ｆ→Ｑ→Ｉ→Ｔ→イ→Ｑ→
Ｕ→Ｊ→Ｗ→コ→イ
【おまけ】
Ｎが３以上で全て可能。
∵ 空白の動きもまた騎士と同じであり、騎士と逆に移動すると考えればよい。
Ｎ＝３，４，５の場合、下図のようにループになった「騎士回廊」がある。
従って、この回廊を空白が一巡するたびに騎士は逆方向に１個づつ必ずずれるので、いずれ黒騎士も反対側に到達する。
なお、空白だけを移動することが目的の場合、Ｎ＝５の色付矢印で示される「近道」をすることで，手数の削減が可能。
Ｎ＞５の場合、Ｎ＝４ないしＮ＝３，５の回廊の半周経路を繋ぎ合わせることにより、「空白」を任意の対角線上に移動が可能である。
（◎＝(10) (1)＝(7) (2)＝(8) (3)＝(9) (4)＝(10) (5)＝(11) 。。。。）即ち，問題のＮを３づつ減らすことが可能である。
よって ３以上のＮに対して移動可能である。
【Ｐ．Ｓ．】
実際にはＮ＝３の手数は近道が無いのでかなり多く、
Ｎ＝６で止め、Ｎ＝６の最小の手順を用いた方が早いようです。
下図参照。
◆宮城県 アンパンマン さんからの解答
【問題１】
１７回
Ｒ→Ｉ→Ｌ→Ａ→Ｈ→Ｏ→
Ｒ→Ｉ→Ｌ→Ｕ→Ｒ→Ｉ→
Ｔ→Ｗ→Ｎ→Ｙ→Ｒ
Ｎ→Ｑ→Ｈ→Ａ→Ｌ→Ｕ→
Ｒ→Ｏ→Ｈ→Ｋ→Ｒ→Ｏ→
Ｈ→Ｅ→Ｎ→Ｙ→Ｒ
【問題２】
１７回
Ｗ→Ｊ→Ｎ→Ａ→Ｉ→Ｍ→
Ｕ→Ｊ→Ｎ→ア→Ｗ→Ｊ→
Ｕ→カ→イ→コ→Ｗ
【おまけ】
３＊３ の場合、25回で移動可能。
４＊４ の場合、5回で移動可能。
ｎ＝３i+j (i>1,1≦j≦3) の場合
最初、隅の位置を(2、3)か(3、2)まで移動します。
(３k＋j,３k＋j)から(３(k-1)＋j,３(k-1)＋j)に移動するには2回以内で可能です。
j=1の場合(4、4)からあと1回で(2、3)か(3、2)に移動できます。
j=2の場合(5、5)からあと3回で(2、3)か(3、2)に移動できます。
j=3の場合(6、6)からあと3回で(2、3)か(3、2)に移動できます。
次はナイトを移動します。
(３(k-1)＋１,３(k-1)＋１)から(３k＋１,３k＋１)に移動するには(隅の位置も考えて)6回以内で可能です。
つまりナイトを(３(i-1)＋１,３(i-1)＋１)に移動するには
4＋6(i-2)回以内で移動可能。
(最初の隅の(ナイトまでの)移動はふくまれていません。)
ｊ＝1の場合
(3i+1,3i+1)までは(2i-1)+4+6(i-2)+6=8i-3回以内で移動可能です。
ｊ＝2の場合
ナイトを(3i+2,3i+2)までは14回以内で移動可能なので、
(2i+1)+4+6(i-2)+14=8i+７回以内で移動可能です。
ｊ＝3の場合
(3i+3,3i+3)までは14回以内で移動可能なので、
(2i+1)+4+6(i-2)+14=8i+７回以内で移動可能です。
◆東京都 BossF さんからの解答
【問題１】
Ｎ→Ｃ→Ｌ→Ａ→Ｈ→Ｑ→
Ｎ→Ｃ→Ｌ→Ｗ→Ｎ→Ｃ→
Ｌ→Ｕ→Ｒ→Ｙ→Ｎ
【問題２】
Ｗ→Ｊ→Ｎ→Ａ→Ｉ→Ｅ→
Ｐ→ア→Ｎ→Ｊ→Ｗ→ア→
Ｓ→Ｏ→イ→コ→Ｗ
【おまけ】
n≧3でできる
[証明]
例のように左上から右、そして下に1,2,3･･････と番号を振り
各マスを(横.縦)であらわすことにする。
一般に、(1.1)と(n.n)を通る桂馬跳びでつないだループができれば、巡回置換によって題意は達せられることに注意する。
まず、n=1のときは、問題は意味を持たない。
n=2のときは明らかに解なし。
n=3のとき
(1.1)→(3.2)→(1.3)→(2.1)→(3.3)→(1.2)→(3.1)→(2.3)→(1.1)
というループが存在するから可能。
ところで、n≧4のとき
(n.n)→(n-2.n-1)→(n.n-2)→(n-2.n-3)→(n-1.n-1)
というループにより、(n.n)と(n-1.n-1)を通るループが存在し
それらを順次つなげることにより(3.3)まで鎖が出来、これを開けばループとなるから可能である
◆長野県 Mr.D さんからの解答
【問題１】
Ｒ→Ｕ→Ｌ→Ａ→Ｈ→Ｅ→
Ｎ→Ｙ→Ｒ→Ｕ→Ｌ→Ａ→
Ｈ→Ｅ→Ｎ→Ｙ→Ｒ→Ｕ→
Ｌ→Ａ→Ｈ→Ｅ→Ｎ→Ｙ→Ｒ
【問題２】
イ→カ→Ｕ→Ｙ→Ｎ→Ａ→
Ｉ→Ｅ→Ｐ→Ｌ→Ｗ→コ→
イ→カ→Ｕ→Ｙ→Ｎ→Ａ→
Ｉ→Ｅ→Ｐ→Ｌ→Ｗ→コ→
イ→カ→Ｕ→Ｙ→Ｎ→Ａ→
Ｉ→Ｅ→Ｐ→Ｌ→Ｗ→コ→
イ→カ→Ｕ→Ｙ→Ｎ→Ａ→
Ｉ→Ｅ→Ｐ→Ｌ→Ｗ→コ→
イ→カ→Ｕ→Ｙ→Ｎ→Ａ→
Ｉ→Ｅ→Ｐ→Ｌ→Ｗ→コ→イ
【おまけ】
可能です。（ｎ≧３）
（1,1）と（n,n)を通る輪を作ることができれば、ところてんのように移動することができます。
【作り方】
作り方はたくさんあると思いますので、その中の一つをあげます。
１．
壁に沿って、行けるところまで行きます。
(n,n)→(n-2,n-1)→(n-4,n)→(n-6,n-1)→(n-8,n)…
すると、ｎによって、
(1,n)か(1,n-1)か(2,n)か(2,n-1)のどこかにたどり着きます。
n=4mのときは、(2,n-1)に、
n=4m+1のときは、(1,n)に
n=4m+2のときは、(2,n)に、
n-4m+3のときは、(1,n-1)にたどり着きます。
２．
(1,n-1)か(2,n)にたどり着いた場合は、(3,n-2)に移動します。
そうすると、(1,n)と(n,1)を結ぶ対角線の上に来ました。
３．
そうしたら、これまで移動した線とこれから移動する線が、この対角線について対称になるように
(1,1) まで移動することができます。
４．
今度は、(1,1)と(n,n)を結ぶ対角線について対称になるように
(n,n)まで移動することができます。
これで輪ができました。
こうして作ると同じ場所を２度以上通ることはないので、ところてん方式ができると思います。
最小手順となるとこの手は使えませんが。
◆東京都 未菜実 さんからの解答
【問題１】
遷移図を書いて最短解を捜してみました。
Ｒ→Ｏ→Ｈ→Ａ→Ｌ→Ｓ→
Ｖ→Ｋ→Ｈ→Ｏ→Ｒ→Ｋ→
Ｈ→Ｅ→Ｎ→Ｙ→Ｒ
の17手が最短では？
【問題２】
さすがに図は大変であきらめました。^^;
部分的に最短距離を捜して（図参照）
イ→Ｑ→Ｉ→Ａ→Ｎ→Ｊ→
Ｕ→Ｑ→Ｉ→Ｔ→イ→Ｑ→
Ｕ→Ｊ→Ｗ→コ→イ
の 17 手が最短と思います。
【おまけ】
図の様に上下左右に1つずつ移動できるので必ず一まとまりの遷移図が存在します。
よって必ず解は存在します。
◆ 問題へもどる
◆ 今週の問題へ
数学の部屋へもどる