当ＨＰがいつもお世話になっているＨＮ「ＧＡＩ」さんからの出題です。（平成２１年１１月３日）
Ａから６までの数字のトランプ６枚を十分にシャッフルする。この初期配列から、次の操作
を繰り返す。
トップにあるカードの数字を見て、その枚数だけカードを取り上げ、順番をまったく
逆にして元に戻す。
このとき、初めて「 Ａ 」がトップから出現する「手間が最もかかる」初期配列は何かを探し
て下さい。また、それは何手かかるでしょうか。
ただし、トップのカードを見ることを１手と数えることにする。
（構造が掴めたら、Ａ〜Ｋの１３枚のカードでも挑戦して下さい。）
（答） いくつか実験をして、上記の操作の構造を眺めることにしよう。
（１） 初期配列が「 Ａ 」 １枚のときは自明で、必要手数は、１手である。
（２） カードが、Ａと２の２枚のとき、初期配列は、（上→下）として、（Ａ２）、（２Ａ）の２通り。
初期配列が（Ａ２）のときは、必要手数は、１手である。
初期配列が（２Ａ）のとき、 （２Ａ） → （Ａ２） となり、必要手数は、２手である。
したがって、カードが、Ａと２の２枚のとき、初めて「 Ａ 」がトップから出現する「手間が最
もかかる」初期配列は、 （２Ａ） で、２手を要する。
（３） カードが、Ａから３までの３枚のとき、初期配列は、
（Ａ２３）、（Ａ３２）、（２Ａ３）、（２３Ａ）、（３Ａ２）、（３２Ａ） の６通り。
初期配列が（Ａ２３）のときは、必要手数は、１手である。
初期配列が（Ａ３２）のときは、必要手数は、１手である。
初期配列が（２Ａ３）のとき、 （２Ａ３） → （Ａ２３） となり、必要手数は、２手である。
初期配列が（２３Ａ）のとき、 （２３Ａ） → （３２Ａ） → （Ａ２３） となり、必要手数は、
３手である。
初期配列が（３Ａ２）のとき、 （３Ａ２） → （２Ａ３） → （Ａ２３） となり、必要手数は、
３手である。
初期配列が（３２Ａ）のとき、 （３２Ａ） → （Ａ２３） となり、必要手数は、２手である。
したがって、カードが、Ａと２と３の３枚のとき、初めて「 Ａ 」がトップから出現する「手間
が最もかかる」初期配列は、 （２３Ａ） または （３Ａ２） で、３手を要する。
上記の計算をボンヤリ眺めていると、初めて「 Ａ 」がトップから出現する「手間が最もか
かる」初期配列になるためには、「 Ａ 」がトップから ｋ 番目にあるとき、トップのカードは
決して数字の「ｋ」であってはいけないということが分かる。
この観点で、上記（３）の場合を見直すと、
「 Ａ 」がトップから２番目にあるとき、 （３Ａ２）
「 Ａ 」がトップから３番目にあるとき、 （２３Ａ）
であることが直ちに求められる。
（４） カードが、Ａから４までの４枚のとき、上記の観点で計算してみよう。
「 Ａ 」がトップから２番目にあるとき、
（３Ａ２４） → （２Ａ３４） → （Ａ２３４） の３手
（３Ａ４２） → （４Ａ３２） → （２３Ａ４） → （３２Ａ４） → （Ａ２３４） の５手
（４Ａ２３） → （３２Ａ４） → （Ａ２３４） の３手
（４Ａ３２） → （２３Ａ４） → （３２Ａ４） → （Ａ２３４） の４手
「 Ａ 」がトップから３番目にあるとき、
（２３Ａ４） → （３２Ａ４） → （Ａ２３４） の３手
（２４Ａ３） → （４２Ａ３） → （３Ａ２４） → （２Ａ３４） → （Ａ２３４） の５手
（４２Ａ３） → （３Ａ２４） → （２Ａ３４） → （Ａ２３４） の４手
（４３Ａ２） → （２Ａ３４） → （Ａ２３４） の３手
「 Ａ 」がトップから４番目にあるとき、
（２３４Ａ） → （３２４Ａ） → （４２３Ａ） → （Ａ３２４） の４手
（２４３Ａ） → （４２３Ａ） → （Ａ３２４） の３手
（３２４Ａ） → （４２３Ａ） → （Ａ３２４） の３手
（３４２Ａ） → （２４３Ａ） → （４２３Ａ） → （Ａ３２４） の４手
したがって、カードが、Ａから４までの４枚のとき、初めて「 Ａ 」がトップから出現する「手
間が最もかかる」初期配列は、 （３Ａ４２） または （２４Ａ３） で、５手を要する。
上記の場合をもっと整理してみよう。
「 Ａ 」がトップから２番目にあるとき、最長配列の候補は、
（３Ａ○□） または （４Ａ○□）
（３Ａ○□） のとき、最長配列になるためには、 ○に入る数字は、２以外
よって、 （３Ａ４２） と確定する。実際に、
（３Ａ４２） → （４Ａ３２） → （２３Ａ４） → （３２Ａ４） → （Ａ２３４） の５手
（４Ａ○□） のとき、最長配列になるためには、 □に入る数字は、３以外
よって、 （４Ａ３２） と確定する。実際に、
（４Ａ３２） → （２３Ａ４） → （３２Ａ４） → （Ａ２３４） の４手
「 Ａ 」がトップから３番目にあるとき、最長配列の候補は、
（２○Ａ□） または （４○Ａ□）
（２○Ａ□） のとき、最長配列になるためには、 ○に入る数字は、３以外
よって、 （２４Ａ３） と確定する。実際に、
（２４Ａ３） → （４２Ａ３） → （３Ａ２４） → （２Ａ３４） → （Ａ２３４） の５手
（４○Ａ□） のとき、最長配列になるためには、 □に入る数字は、２以外
よって、 （４２Ａ３） と確定する。実際に、
（４２Ａ３） → （３Ａ２４） → （２Ａ３４） → （Ａ２３４） の４手
「 Ａ 」がトップから４番目にあるとき、最長配列の候補は、
（２○□Ａ） または （３○□Ａ）
（２○□Ａ） のとき、最長配列になるためには、 ○に入る数字は、４以外
よって、 （２３４Ａ） と確定する。実際に、
（２３４Ａ） → （３２４Ａ） → （４２３Ａ） → （Ａ３２４） の４手
（３○□Ａ） のとき、最長配列になるためには、 □に入る数字は、４以外
よって、 （３４２Ａ） と確定する。実際に、
（３４２Ａ） → （２４３Ａ） → （４２３Ａ） → （Ａ３２４） の４手
したがって、カードが、Ａから４までの４枚のとき、初めて「 Ａ 」がトップから出現する「手
間が最もかかる」初期配列は、 （３Ａ４２） または （２４Ａ３） で、５手を要する。
ここで見方を変えよう。
上記で手順が長い配列の最終形は何れも （Ａ２３４） であることに気がつく。
配列で、「上から ｋ 番目には数字の ｋ 」という場合がたくさんある方が最長手順を生む
原動力になっているような．．．そんな雰囲気。
この最長手順を生むであろう配列から逆算して初期配列を求めることにしよう。
（Ａ２３４） ← （２Ａ３４） ← （３Ａ２４） ← （４２Ａ３） ← （２４Ａ３）
※ （３Ａ２４） の代わりに （４３Ａ２） とすると、「上から ｋ 番目には数字のｋ」
という場合が消失するので、そこで操作はストップしてしまう。
（Ａ２３４） ← （３２Ａ４） ← （２３Ａ４） ← （４Ａ３２） ← （３Ａ４２）
※ （２３Ａ４） の代わりに （４Ａ２３） とすると、「上から ｋ 番目には数字の ｋ 」
という場合が消失するので、そこで操作はストップしてしまう。
（Ａ２３４） ← （４３２Ａ）
※ この場合は、「上から ｋ 番目には数字の ｋ 」という場合が消失するので、
そこで操作はストップしてしまう。
以上から、カードがＡから４までの４枚のとき、初めて「 Ａ 」がトップから出現する「手間が
最もかかる」初期配列は、 （３Ａ４２） または （２４Ａ３） で、５手を要する。
（５） カードが、Ａから５までの５枚のとき、初めて「 Ａ 」がトップから出現する「手間が最も
かかる」初期配列を上記の方法で求めてみよう。
（Ａ２３４５） ← （２Ａ３４５） ← （３Ａ２４５） ← （４２Ａ３５）
← （２４Ａ３５） ← （５３Ａ４２） ← （４Ａ３５２） ← （３Ａ４５２）
（Ａ２３４５） ← （３２Ａ４５） ← （２３Ａ４５） ← （４Ａ３２５）
← （３Ａ４２５） ← （５２４Ａ３） ← （２５４Ａ３）
（Ａ２３４５） ← （４３２Ａ５） ← （５Ａ２３４）
（Ａ２３４５） ← （５４３２Ａ） ← （３４５２Ａ）
以上から、カードがＡから５までの５枚のとき、初めて「 Ａ 」がトップから出現する「手間が
最もかかる」初期配列は、 （３Ａ４５２） で、８手を要する。
（６） カードが、Ａから６までの６枚のとき、初めて「 Ａ 」がトップから出現する「手間が最も
かかる」初期配列を求めてみよう。
（Ａ２３４５６） ← （２Ａ３４５６） ← （３Ａ２４５６） ← （４２Ａ３５６）
← （２４Ａ３５６） ← （５３Ａ４２６） ← （４Ａ３５２６） ← （３Ａ４５２６）
← （６２５４Ａ３） ← （２６５４Ａ３） ← （４５６２Ａ３）
（Ａ２３４５６） ← （３２Ａ４５６） ← （２３Ａ４５６） ← （４Ａ３２５６）
← （３Ａ４２５６） ← （５２４Ａ３６） ← （２５４Ａ３６） ← （６３Ａ４５２）
← （４Ａ３６５２） ← （３Ａ４６５２） ← （５６４Ａ３２）
（Ａ２３４５６） ← （４３２Ａ５６） ← （５Ａ２３４６） ← （６４３２Ａ５） ← （３４６２Ａ５）
（Ａ２３４５６） ← （５４３２Ａ６） ← （６Ａ２３４５）
（Ａ２３４５６） ← （６５４３２Ａ）
以上から、カードがＡから６までの６枚のとき、初めて「 Ａ 」がトップから出現する「手間が
最もかかる」初期配列は、 （４５６２Ａ３） または （５６４Ａ３２） で、１１手を要する。
（７） カードが、Ａから７までの７枚のとき、初めて「 Ａ 」がトップから出現する「手間が最も
かかる」初期配列を求めてみよう。
（Ａ２３４５６７） ← （２Ａ３４５６７） ← （３Ａ２４５６７） ← （４２Ａ３５６７）
← （２４Ａ３５６７） ← （５３Ａ４２６７） ← （４Ａ３５２６７） ← （３Ａ４５２６７）
← （６２５４Ａ３７） ← （２６５４Ａ３７） ← （７３Ａ４５６２） ← （４Ａ３７５６２）
← （３Ａ４７５６２） ← （５７４Ａ３６２） ← （６３Ａ４７５２） ← （４Ａ３６７５２）
← （３Ａ４６７５２）
（Ａ２３４５６７） ← （３２Ａ４５６７） ← （２３Ａ４５６７） ← （４Ａ３２５６７）
← （３Ａ４２５６７） ← （５２４Ａ３６７） ← （２５４Ａ３６７） ← （６３Ａ４５２７）
← （４Ａ３６５２７） ← （５６３Ａ４２７） ← （３６５Ａ４２７） ← （７２４Ａ５６３）
← （２７４Ａ５６３） ← （５Ａ４７２６３） ← （６２７４Ａ５３） ← （２６７４Ａ５３）
← （４７６２Ａ５３）
（Ａ２３４５６７） ← （４３２Ａ５６７） ← （５Ａ２３４６７） ← （６４３２Ａ５７）
← （３４６２Ａ５７） ← （７５Ａ２６４３）
（Ａ２３４５６７） ← （５４３２Ａ６７） ← （３４５２Ａ６７） ← （６Ａ２５４３７）
← （７３４５２Ａ６）
（Ａ２３４５６７） ← （６５４３２Ａ７） ← （７Ａ２３４５６）
（Ａ２３４５６７） ← （７６５４３２Ａ） ← （４５６７３２Ａ）
以上から、カードがＡから７までの７枚のとき、初めて「 Ａ 」がトップから出現する「手間が
最もかかる」初期配列は、 （３Ａ４６７５２） または （４７６２Ａ５３） で、１７手を要する。
（コメント） 厳密には樹形図を用いて、いろいろ変化した手も吟味する必要がありそう．．．。
手計算では限界がありますね！Ａ〜Ｋの１３枚のカードに至っては、気が遠くなり
そうですね。
出題者のＧＡＩさんから、アドバイスをいただいた。（平成２１年１１月１１日付け）
カードがＡから６までの６枚のとき、初めて「 Ａ 」がトップから出現する「手間が最もかかる」
初期配列として、 （４５６２Ａ３） または （５６４Ａ３２） の２つをあげているが、その他に、
（３６５Ａ４２） （４Ａ５２６３） （４Ａ６５２３）
も解になる。このうち（４Ａ６５２３）の最終形は完全順列（Ａ２３４５６）にはならず、（Ａ４３２５６）
である。この６枚の場合が他の場合と少し状況が違うようだ。思ったよりも奥が深い数理を潜
ませている感がある。
実際に、確認してみよう。
（３６５Ａ４２） → （５６３Ａ４２） → （４Ａ３６５２） → （６３Ａ４５２）
→ （２５４Ａ３６） → （５２４Ａ３６） → （３Ａ４２５６） → （４Ａ３２５６）
→ （２３Ａ４５６） → （３２Ａ４５６） → （Ａ２３４５６）
（４Ａ５２６３） → （２５Ａ４６３） → （５２Ａ４６３） → （６４Ａ２５３）
→ （３５２Ａ４６） → （２５３Ａ４６） → （５２３Ａ４６） → （４Ａ３２５６）
→ （２３Ａ４５６） → （３２Ａ４５６） → （Ａ２３４５６）
（４Ａ６５２３） → （５６Ａ４２３） → （２４Ａ６５３） → （４２Ａ６５３）
→ （６Ａ２４５３） → （３５４２Ａ６） → （４５３２Ａ６） → （２３５４Ａ６）
→ （３２５４Ａ６） → （５２３４Ａ６） → （Ａ４３２５６）
（コメント） 上記でも述べましたが、最初の２つは、樹形図を用いて考えると拾い上げられる
可能性はありますが、３番目は全く予想外の解ですね！やはり全数検査が必要な
のでしょうか？何か未知の構造がまだ秘められているような．．．雰囲気。
平成２１年１１月１４日付けで、ＧＡＩ さんより、「最長手順の解析経過報告」を頂いた。
手調査による手段では限界を感じるので、コンピュータによる全パターンの解析結果の報
告とのことである。ただし、カードの「１０」は「Ｘ」と表記し、１４枚目は「Ｌ」とする。
※トップのカードを見ることを１手と数えることにさせていただきました。