【問題1】 最小回数は、以下の19回 1⇔ 7, 2⇔24, 3⇔10, 4⇔19, 5⇔10, 6⇔12, 7⇔20, 9⇔22,10⇔23,11⇔24, 12⇔15,13⇔25,14⇔18,15⇔25,16⇔24, 17⇔21,18⇔23,19⇔22,20⇔24 【問題2】 (最小回数であることの説明)  a.問題の表記と用語の定義 問題の配置をパネル上の位置(上段)とその位置にある数字(下段)の組合せとして書き直すと    以下のようになる。     位置 → 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25     数字 → 7 24 10 19 3 12 20 8 22 23 2 15 25 18 13 11 21 5 9 16 17 4 14 1 6 これを、しりとりの手順(下段の数字−>上段の位置の数字)に従って列を並べ替える。   1 7 20 16 11 2 24 * 3 10 23 14 18 5 * 4 19 9 22 * 6 12 15 13 25 * 8 * 17 21    7 20 16 11 2 24 1 * 10 23 14 18 5 3 * 19 9 22 4 * 12 15 13 25 6 * 8 * 21 17     (*はしりとりの完結する位置をわかりやすくするために挿入)          使用する用語を以下の様に定義する。     循環列   : 上記のしりとりが完結する列のセット             例えば 1 7 20 16 11 2 24          7 20 16 11 2 24 1     循環列の長さ:循環列を構成する列の数。上記の例の場合は、7になる。     単位循環列 :長さが1の循環列     問題の正規表現:問題を循環列に並べ替えた表記     問題の位数 :問題に含まれる循環列の数。            与えられた問題の場合は、6。            最終形では、すべて単位循環列となるので25(=列の数)となる。  b.交換操作と循環列との関係    パネル上の2つの数字を交換する操作を循環列に着目して見ると、      2つの循環列に跨る交換(例えば1と10の交換)と      1つの循環列の中に閉じた交換(例えば7と20の交換)    にわけることができる。    1と10の交換のように2つの循環列に跨る交換をする場合は、以下のようになり、    1 7 20 16 11 2 24 3 10 23 14 18 5 *    7 20 16 11 2 24 10 1 23 14 18 5 3 *         ^^^^^^ これを整理すると、1つの循環列になっていることがわかる。    1 7 20 16 11 2 24 10 23 14 18 5 3 *    7 20 16 11 2 24 10 23 14 18 5 3 1 *    すなわち、2つの循環列に跨る交換は、2つの循環列を1つの循環列に連結する作用があり、    問題の位数は1つ減少する。    次に7と20の交換のように1つの循環列の中に閉じた交換の場合は、以下のようになり、    1 7 20 16 11 2 24 *    20 7 16 11 2 24 1 *   ^^^^^^ これを整理すると、2つの循環列に分割されていることがわかる。    7 * 1 20 16 11 2 24 *    7 * 20 16 11 2 24 1 * 20と11の交換の場合も、同様に、2つの循環列に分割される。    1 7 20 16 11 2 24 * --> 1 7 11 2 24 * 20 26 *    7 11 16 20 2 24 1 * 7 11 2 24 1 * 26 20 * ^^ ^^    以上から、1つの循環列の中に閉じた交換は、1つの循環列を2つの循環列に分割する作用があり、    問題の位数は1つ増加する。  c.最小回数となる手順の条件    以上の考察より、     @与えられた問題の位数(=6)< 最終形の位数(=25)であるから、『位数が増加す      る手順を常に選択する方法』が最小回数となる手順である     A1回の交換操作では、位数は1つしか増加しないので、本問題の場合、25−6=19回の      交換が最小回数となる    @,Aをまとめると、『常に1つの循環列の中に閉じた交換を続ける』ことが最小回数の19回とな    る手順である。そして、その最も簡単な手順が、問題1の解答で示した『1から順番に所定の位置    にない数字を交換により所定の位置に戻していく』という方法である。 【問題3】 (答え)   最小回数となる手順の数は、425,935,250,535,674,880,000 通り (求め方) a.準備   長さがN1,N2,...,Nmのm個の循環列で構成される問題を最小回数で解く手順の数をR(N1,N2,...,Nm) とする。R(N1,N2,...,Nm)は、以下の関係が成り立つ。   1) R(1) = 0   2) R(2) = 1   3) R(N) = N*{ R(1,N-1)+R(2,N-2)+ ... +R(s,N-s)*δ/2 }             ただし、δ = 0   Nが奇数のとき                   = 1   Nは偶数のとき   4) R(N1,N2,...,N[k-1],1,N[k+1],...,Nm)=R(N1,N2,...,N[k-1],N[k+1],...,Nm)       (長さ1の循環列は、無操作なので除外してよい)   5) Nk > 1 のとき (k=1,2,...,m)                  (N1 + N2 + ... + Nm - m)!      R(N1,N2,...,Nm)=−−−−−−−−−−−−−−−−−−−−−*R(1)*R(2)* ... *R(Nm)                (N1-1)!*(N2-1)!* ... *(Nm-1)!      1),2),4)は自明。3),5)については、補足1,2で説明する。 b.最小回数で解く手順の数   与えられた問題は、R(1,2,4,5,6,7)に該当する。   まず、R(3)〜R(7)を1)〜5)を使って、順次求めていく。     R(3) = 3*{R(1,2)} = 3*R(2) = 3       次に、R(4)を求めるために必要なR(2,2)を求めると              (2+2−2)!             2!     R(2,2)=−−−−−−−−−−−*R(2)*R(2)=−−−−−−*1*1 = 2                (2−1)!*(2−1)!          1!*1!     R(4) = 4*{R(1,3)+R(2,2)/2}= 4*{R(3)+R(2,2)/2}= 4*{3+2/2}          = 16      同様にして、R(5)=125、R(6)=1296、R(7)=16807を得る。     最後に、     R(1,2,4,5,6,7)=R(2,4,5,6,7)            (2+4+5+6+7−5)!        =−−−−−−−−−−−−−−−−−−−−−−−−−*R(2)*R(4)*R(5)*R(6)*R(7)         (2-1)!*(4-1)!(5-1)!*(6-1)!*(7-1)!               19!        = −−−−−−−−−−−−−*16*125*1296*16807           3!*4!*5!*6!        = 425,935,250,535,674,880,000    この膨大な数がもとめる答えである。 ----------------------------------------------------------------------------------------------------  補足1  3)の説明     長さnの循環列の構成要素を(A1,A2,,,,An)とし、これを長さsと(n−s)の2つの循環列に分ける     場合を考える。(ただし、s<=n-s)     s<n−sの場合、長さsの循環列の選び方は、以下のn通り。      (A1,A2, ... ,As)  (A2,A3,...,A[s+1])  ...  (An,A1,...,A[s-1])     また、長さsと(n−s)の2つの循環列の問題を解く手順の数はR(s,n−s)通りであるから     全体では、n*R(s,n−s)通りとなる。     s=n−sの場合(nは偶数,s=n/2)、長さsの循環列の選び方は、以下のn/2通り。 注:(A1,A2, ... ,As) と(A[n/2+1],...,An) は同じ分割となっているため、半分になる      (A1,A2, ... ,As) (A2,A3,...,A[s+1]) ... (A[n/2],...,A[n-1])     また、長さn/2の2つの循環列の問題を解く手順の数はR(n/2,n/2)通りであるから     全体では、n/2*R(n/2,n/2)通りとなる。 sは、1〜n/2の範囲で任意の整数値をとることができるので、      R(n)=n*R(1,n−1)+n*R(2,n−2)+...+n/2*R(n/2,n/2)*δ          =n*{ R(1,n−1)+R(2,n−2)+...+R(n/2,n/2)*δ/2 }            但し、δ=0  nが奇数のとき                1  nが偶数のとき  補足2  5)の説明    2つの循環列a、bの長さをn、mとし、a、bを単独で解くて手順をそれぞれ        A1,A2,...,A[n-1]  B1,B2,...,B[m-1] とする。    この手順の中からAi,Bjのいずれかを順番に取り出して並べると、a,bを合わせて解く手順となる。    例えば、A1,A2,...,A[n-1],B1,B2,...,B[m-1]やA1,B1,A2,B2,...A[-1]B[m-1]など    Ai,Bjの並べ方は、a、bの中からaをn−1個、bをm−1個取り出す順列の数となるので      (n+m−2)!/((n−1)!*(m−1)!)通り    となる。また、a,bを単独で解く手順の数は、それぞれR(n),R(m)通りであるから、全体では、              (n+m−2)!      R(n,m)=−−−−−−−−−−−−−*R(n)*R(m)             (n−1)!*(m−1)!    となる。    一般の場合、m個の循環列の長さをN1,N2,...,Nmとすると                  (N1 + N2 + ... + Nm - m)!      R(N1,N2,...,Nm)=−−−−−−−−−−−−−−−−−−−−−*R(1)*R(2)* ... *R(Nm)                (N1-1)!*(N2-1)!* ... *(Nm-1)!       となる。  補足3  R(n)の一般式の予測    R(3)〜R(7)の値は、3**1,4**2,6**4,7**5となっているので、一般式として        R(n) = n **(n−2)    が予測される。 しかし、証明を試みたが力及ばず、断念した。    回答者の中にこの証明があることを楽しみにしています。 -----------------------------------------------------------------------------------------------------