・カード遊び                           GAI 氏

 1から10までの数字が1つずつ書かれた10枚のカードがある。カードは一列に並べられて
おり、一番左のカードに書かれている数字を見て、その数の枚数だけカードを左から取り、
並びを逆順にする作業を繰り返す。

 この作業を左端が1になるまで続ける。(1が左端に現れると作業は停止する。)

 この時、最長手数になる最初の配列は何で、その手数はいくつになるでしょうか?


 スモークマンさんからのコメントです。(平成30年6月23日付け)

 「2,10,8,6,4,1,3,5,7,9」で、13回かな?


 らすかるさんからのコメントです。(平成30年6月23日付け)

 プログラムを作って調べたところ、最長は38手でしたが、この解は手作業で導き出せるの
でしょうか?

 あと、38手になる解は一つしかありませんでした。


 GAI さんからのコメントです。(平成30年6月24日付け)

 (n=5の場合の手作業)

  まず1〜5を整然と並べて、左からの位置と数字が一致するものを(1を除く)探し、該当す
るものの左方を優先してそれから左の数字を入れ替えて行く。

0:12345  (整然と並べたとき位置と数字が一致するのが2,3,4,5だが左優先から2の位置で作業)
1:21345 (3,4,5が一致し3で作業)
2:31245  (4,5が一致4で作業)
3:42135 (2,5が一致2で作業)
4:24135  (5で一致)
5:53142 (4で一致)
6:41352 (3で一致)
7:31452 (該当するもの無し=完全順列の時終了)

 逆に、31452からスタートすれば例のルールで7回で1が先頭に出てきて終了となる。

 (n=6の場合の手作業)

0:123456
1:213456
2:312456
3:421356
4:241356
5:531426
6:413526
7:314526
8:625413
9:265413
10:456213 (完全順列)

 以上から、6個なら最長10回の手数で達成できることになる。

 基本的には10に拡張すれば何とか手作業で行けそうかと・・・。あれ〜やってみたらなりま
せんでした!・・・今考察中。


 らすかるさんからのコメントです。(平成30年6月24日付け)

 「A000375」にありましたが、これを見ると手作業では無理っぽいですね。もしn=10の解を
手作業で機械的に求められるのであれば、コンピュータでn=17までしかわからないというこ
とにはならないと思います。


 GAI さんからのコメントです。(平成30年6月24日付け)

 確かに、一律の法則で手作業による方法を編み出すことは困難ですね。

 n=10の場合をやってみたら、

0 :1,2,3,4,5,6,7,8,9,10
1 :2,1,3,4,5,6,7,8,9,10
2 :3,1,2,4,5,6,7,8,9,10
3 :4,2,1,3,5,6,7,8,9,10
4 :2,4,1,3,5,6,7,8,9,10
5 :5,3,1,4,2,6,7,8,9,10
6 :4,1,3,5,2,6,7,8,9,10 (3,6,7,8,9,10 が該当するが6で作業する)
7 :6,2,5,3,1,4,7,8,9,10
8 :2,6,5,3,1,4,7,8,9,10
9 :7,4,1,3,5,6,2,8,9,10 (5,6,8,9,10 が該当するが6で作業)
10:6,5,3,1,4,7,2,8,9,10 (3,8,9,10 が該当するが8で作業)
11:8,2,7,4,1,3,5,6,9,10
12:2,8,7,4,1,3,5,6,9,10 (4,9,10 が該当するが9で作業)
13:9,6,5,3,1,4,7,8,2,10
14:7,4,1,3,5,6,9,8,2,10
15:5,3,1,4,7,6,9,8,2,10
16:4,1,3,5,7,6,9,8,2,10
17:3,1,4,5,7,6,9,8,2,10
18:6,7,5,4,1,3,9,8,2,10 (4,8,10 が該当するが8で作業)
19:8,9,3,1,4,5,7,6,2,10
20:3,9,8,1,4,5,7,6,2,10 (7,10 が該当10で作業)
21:10,2,6,7,5,4,1,8,9,3
22:2,10,6,7,5,4,1,8,9,3
23:5,7,6,10,2,4,1,8,9,3
24:8,1,4,2,10,6,7,5,9,3
25:6,10,2,4,1,8,7,5,9,3
26:4,2,10,6,1,8,7,5,9,3 (2,7,9 が該当で7で作業)
27:7,8,1,6,10,2,4,5,9,3
28:9,5,4,2,10,6,1,8,7,3
29:6,10,2,4,5,9,1,8,7,3
30:4,2,10,6,5,9,1,8,7,3
31:2,4,10,6,5,9,1,8,7,3
32:5,6,10,4,2,9,1,8,7,3
33:4,10,6,5,2,9,1,8,7,3
34:8,1,9,2,5,6,10,4,7,3
35:5,2,9,1,8,6,10,4,7,3
36:2,5,9,1,8,6,10,4,7,3
37:6,8,1,9,5,2,10,4,7,3
38:5,9,1,8,6,2,10,4,7,3  (完全順列:終了)

 最長手数にするには、この例外部分をどう判断できるかに関わるが、これを前もって見極
めることは至難の技であろう。


 らすかるさんからのコメントです。(平成30年6月24日付け)

 この方法では、「最終形が昇順に並ぶものの最大値」しか求まりませんので、最終形が任
意順である場合の最大値にはならない可能性があります。

 「最終形が昇順に並ぶものの最大値」は、「A000376」にあり、n=11までは同じ値ですが、
n=12では異なります。

 実際、n=12で最大の65手になる解:「2 6 1 10 11 8 12 3 4 7 9 5」に対して操作を行うと、最
終形は、「1 6 5 2 3 4 7 8 9 10 11 12」となり、昇順になりません。



                         投稿一覧に戻る