『今週の問題』第218回　解答

◆北海道　和貴 さんからの解答

【問題１−１】

1→移動先，2,3→移動先，4→移動先，4,2→最　初，3,1→最　初，
3→移動先，1,4→移動先，2→移動先，2,1→最　初，4,3→最　初，

1→移動先，2,3→移動先，4→移動先，4,2→最　初，3,1→最　初，
3→移動先，1,4→移動先，1→最　初，4→最　初，3→最　初，
3,4→移動先，1,2→移動先，

1→移動先，2,3→移動先，4,5→移動先，6→移動先，6,4→最　初，
5,2→最　初，3,1→最　初，3→移動先，1,5→移動先，2,6→移動先，
4→移動先，4,2→最　初，6,1→最　初，5,3→最　初，5→移動先，
3,6→移動先，1,4→移動先，2→移動先，2,1→最　初，4,3→最　初，
6,5→最　初，

【問題２−２】

1→移動先，2,3→移動先，4,5→移動先，6→移動先，6,4→最　初，
5,2→最　初，3,1→最　初，3→移動先，1,5→移動先，2,6→移動先，
4→移動先，4,2→最　初，6,1→最　初，5,3→最　初，5→移動先，
3,6→移動先，1,4→移動先，1→最　初，4→最　初，3→最　初，
6→最　初，5→最　初，5,6→移動先，3,4→移動先，1,2→移動先，

【おまけ２】

ｎ(ｎ＋３) ２

−２

最初の場所に2だけが残るまで上記の作業を繰り返す。
これは移動先での2の位置が上から2番目になる時の試行で成り立つ。

すべてが移動先に移動したときの2の位置は、
(ｎ - ２* 移動した回数) であらわすことができる。

よって移動させる回数は ｎ−２ * ｘ＝２

ｘ＝

ｎ ２

−１　より

ｎ ２

−１　回である。

上記の試行で移動先へ行き、最初の場所に完全に戻る回数は、

ｎ ２

＋１＋

ｎ ２

なので、ここまでのすべての移動の回数は

ｘ*(ｎ＋１) …(1) となる。

次に、2だけが残るように奇数番目を上から順に移動先へ移動させる。

この試行は

ｎ ２

回 …(2) である。

移動先のものを逆順にして最初の場所に戻す。
この試行は ｎ−１回 …(3) である。

最初の場所の偶数番号をクリックして、移動先へ移動させる。

この試行は

ｎ ２

回…(4) である。

すべての試行は(1)+(2)+(3)+(4)より、整理して

ｎ(ｎ＋３) ２

−２…(答)

◆愛知県　Y.M.Ojisan　さんからの解答

【問題１】

【問題１−１】　１０手

1,2→移動先，3,4→移動先，3→最　初，4,1→最　初，2→最　初，
2,4→移動先，1,3→移動先，1→最　初，3,2→最　初，4→最　初，


【問題１−２】　１２手

1,2→移動先，3,4→移動先，3→最　初，4,1→最　初，2→最　初，
2,4→移動先，1,3→移動先，1→最　初，3,2→最　初，3→移動先，
2→移動先，1→移動先，

【おまけ２】 　予想です

【証明】
　下図（ｎ＝8の場合）のようにカードのある部分だけ上部を付き合わせると、8個のセルにカードがならび、
ｎ＋１個の位置の何れかの位置に境界が一つあるという図になる。
この場合、１個だけ移動するのは、境界が１個ずれるだけと同じである。
また、２個の移動は、境界が２個ずれることと、通過した２セルのカード交換が行われることと同じである。

　以上の表示方法で初期状態とゴール状態を表すと下図である。
いずれのゴールもカード配置にのみ注目すると逆順である。境界位置が異なっているだけである。　
一方、上図に示すように１個移動ではカードの並びは変化せず、２個の場合は互換一回に対応している。

【十分条件】
【おまけ１】　下図のように左に２個２個。。。右に１個2個2個。。１個移動を　左右にｎ回スイープすればカード順は逆転し、かつ矢印は左端に来る。
このときの手順数はである。

　　
【おまけ２】　下図のようにおまけ１の最後の１手前まで実行し、そのまま１個1個1個で左に進む。
このときの手順数はである。（青破線はそのままを表す）
これは単順に、おまけ１の手順の最後を除く手順の後、１個移動のみで右へ戻る方法よりは２回少ない。
　　

【必要条件】
Ｎ枚のカードを逆順に並び替えるには　互換は全部で回必要である。
これを「必要互換数」とよぶ。
即ち、どんなに少なくても回の手数は必須である。
ただし、２個移動ばかりでは矢印の位置が２ずつ左右するだけなので、ｎ＝８の場合なら４回より後は戻るしかなく、かつ単純に戻るとそれは前回と同じ互換なので無駄である。

従って、状況を変えるには　ここに「１個移動」を挟む必要がある。
さらに次の折り返しを考えると最後にも「１個移動」を挟む必要がある。

「よって一般には往復でｎ−１回連続が最高である。
これを「往復最高連続互換回数」とよぶ。

必要互換数／往復最高連続互換回数＝ｎの半分であるので　少なくともｎ回の「１個移動」が余分に必要である。
ｎは奇数であるので、区分境界（↓）はほぼ左の端に行っている。
完全に左端にゴールするには、後１回「１個移動」が必要である。
　よって、【おまけ１、２】の手数は回より小さくない。

【おまけ２】の場合は、PCで虱潰しに探索したところ　ｎ＝4，６，８，１０の場合は十分条件で示した手数が最小であることが確認された。
多分、それ以上のときも十分条件で示した手数が最小と思われるが証明できなかった。

上記探索プログラムのソース(VC++)を添付する。　　
出発と到着が反転対称の関係にあることを利用し、出発と到着両側から横型探索している。
また、順列の背番号付けで逆順列　を隣接する背番号にし、探索計算を効率化している。

　◆ 問題へもどる

　◆ 今週の問題へ

数学の部屋へもどる