◆千葉県 しまだきよこ さんからの解答
【問題１】
[5→1→6→4→9] 5回
4匹ずつの場合… ---------------------------- A B A B A B A B 〇〇 ---------------------------- A B A B 〇〇A B B A 〇〇A B B A A B B A A A A B B 〇〇B B A A A A 〇〇B B B B A A A A A B B B B 〇〇 ----------------------------【問題２】
[7→3→1→10→4→1] 6回
5匹ずつの場合… ---------------------------- A B A B A B A B A B 〇〇 ---------------------------- A B A B A B 〇〇A B B A A B 〇〇A B B A A B B A 〇〇B A A B B A A B B A B B B A A B B A A 〇〇A B B B 〇〇B B A A A A A 〇〇B B B B B A A A A A ----------------------------【問題３】
[9→5→1→10→4→6→13] 7回
6匹ずつの場合… ---------------------------- A B A B A B A B A B A B 〇〇 ---------------------------- A B A B A B A B 〇〇A B B A A B A B 〇〇A B B A A B B A 〇〇A B B A A B B A A B B A A A A B B A A B B 〇〇B B A A A A 〇〇A A B B B B B B A A A A A A 〇〇B B B B B B A A A A A A A B B B B B B 〇〇 ----------------------------【おまけ】
動物がＮ匹ずつの場合、入れ替えにかかる最短手数は、(n+1)回です。
Ｎが２の場合は、できませんでした。
入れ替えの手順は、
まず(A B A B)を(A B B A)に置換え、
次に(B B)と(A A)を左右に振り分けていくのが、一番手っ取り早いと思います。
◆新潟県 エチロ町ヨコリン さんからの解答
【おまけ】
答えはｎ＋１回（ｎ≧３ ｎ：自然数）
ｎ＝１の時 ０回
ｎ＝２の時は できない
ｎ＝４以上のときは
ｎ＝偶数の時：
| ｎ ２ | 回で１２２１１・・・１１２２１の形にできる。 |
２２．１１のかたまりで動かすと
| ｎ ２ | 回で１１１１・・空白・・２２２２１ |
ｎ＝奇数の時：
| ｎ＋１ ２ | 回で１２２１１２２・・・１１２２１の形にできる。 |
２２．１１の塊で動かすと
| ｎ−１ ２ | 回で１１１１空白１１２２２・・・２２２ |
◆宮城県 アンパンマン さんからの解答
【問題１】
5回
5→1→6→4→9
【問題２】
6回
7→1→8→10→3→11あるいは
7→10→3→9→2→11あるいは
7→3→8→10→1→11
【問題３】
7回
9→5→1→10→4→6→13
【おまけ】
n=1, 0手数
n=2,入れ替える方法はありません。
n=3,最短手数＝5
（青木注：４手で可能のようです。手順はY.M.Ojisan さんの解答を参照）
ｎ＞３の場合、
ABABAB....ABから
F:AA...ABB...B あるいは
R:BB...BAA...Aにするためには違う側のA、Bを自分の側に持っていかなくてはならない。
| つまり少なくとも2[ | ｎ ２ | ]手数が必要です。 |
実際はn+1手数が必要です。（ｎ＞３）
n偶数、n=2mの場合：
最短手数は
2n-3,2n-7,...,1,
2n-2,4,2n-6,8,2n-10,12,...,n,
2n+1
| 合計m+[ | m 2 | ]+[ | m+1 2 | ]+1=n+1手数 |
ちなみにRにするにはn+2手数が必要です。
n=4m+1の場合：
FとRにするための最短手数は同じn+1です。
最短手数は
2n-3,2n-7,...,7,3,
2n-2,2n,1,
2n-6,6,2n-10,10,...,n+3,n-3,
2n+1
合計2m+3+(m-1)+(m-1)+1=n+1手数
(FOOになります）
あるいは
2n-3,2n-7,...,7,3,
1,
2n,4,2n-4,...,n+5,n-1,
1
合計2m+1+m+m+1=n+1手数
(OORになります）
n=4m+3の場合：
最短手数は
2n-3,2n-7,...,7,3,
1,
2n,4,2n-4,10,...,n+7,n-3,n+3,
2n+1
合計(2m+1)+1+(m+1)+m+1=n+1手数
(ROOになります）
ちなみに、Fにするにはn+2手数が必要です。
2n-3,2n-7,...,7,3,
2n-2,2n,1,
2n-6,6,2n-10,10,...,n+1,n-1,
2n+1
合計(2m+1)+3+m+m+1=n+2手数
(FOOになります）
◆愛知県 Y.M.Ojisan さんからの解答
【問題１】 ５手
【問題２】 ６手
【問題３】 ７手
【おまけの予想】
Ｎ＋１手 （ただしＮ＞２）
Ｎ＋１手は後述の手順により可能。
Ｎ−１手以下は不可能。
「仲間同士隣合い」の数を考えることで証明は容易。
Ｎ手はほぼ不可能のようですが、証明できていません。
【Ｎ＝３のとき】 ４手
【Ｎ＝７のとき】 ８手
【一般のＮ（＞３）の手順】
（１）枠の右から６番目、
すなわち Ｐ1＝２Ｎ−３ 番から始めて
Ｐ1−４ 、 Ｐ1−８ 。。。。。と４飛びの位置を移動し、最後に１番を移動する。
なお、Ｎが奇数のときは1番はＰ1−４ｐの系列ではない。
すると、必ず、［（Ｎ＋１）／２］手で、解答図内赤枠のように、両端が単独かつ右端がライオンで、間は２匹ずつ交互に整列する状態になる。
細かく見ると、Ｎの偶奇性で動物左端（空白のとなり）がライオンかねずみか決まる。
解答図参照。
（２− 奇数Ｎ）
枠の右から３番目、
すなわち Ｐ2＝２Ｎ 番から始めて、空白を外側から中心へ仲間が増えるように移動させる。
すなわち Ｐ2，４，Ｐ2−４，８，。。。。。。というように移動させる。
すると、合計Ｎ手めで、 解答図｛問題２、 Ｎ＝７のとき｝に示されるように、リーチ手になり、
最後に（Ｎ＋１）／2の偶奇性により、右端２Ｎ＋１番 または 左端１番を移動して完成。
すなわちＮ＋１手で完成。
（２− 偶数Ｎ）
枠の右から５番目、
すなわち Ｐ2＝２Ｎ−２ 番から始めて、空白を外側から中心へ仲間が増えるように移動させる。
すなわち Ｐ2，４，Ｐ2−４，８，。。。。というように移動させる。
すると、合計Ｎ手めで、 解答図｛問題１、 問題３｝に示されるように、
｛ライオンＮ−１匹＋空白２＋ねずみＮ匹＋ライオン１匹｝のリーチ手になり、
最後に右端の２Ｎ＋１番を移動して完成。
すなわちＮ＋１手で完成。
まとめると、Ｎの４の剰余により若干異なる４タイプがあるが、概念的には同じ手順
｛右から４飛びで左へ、１番、右から始めてＶ字状に中心へ、最後に完成の１手｝により
Ｎ＋１手で完成させることができる。
◆ 問題へもどる
◆ 今週の問題へ
数学の部屋へもどる