◆広島県 清川 育男 さんからの解答
【問題１】
２→９→18→16→８→17→11→７→15→20→
13→５→３→12→19→14→10→４→６→１
【おまけ１】
すべて可能。
出発点別の解の個数は 34 34
10 10
34 10 4 4 10 34
34 10 4 4 10 34
10 10
34 34全結果はこちらです。
【おまけ２】
34通り
結果はこちらです。
◆愛知県 Y.M.Ojisan さんからの解答
【問題１】
２→７→11→17→15→20→13→５→３→12→
19→14→10→４→６→１→８→16→18→９
【おまけ１】
不可能位置はない。
∵ 問題１の解答において、９から２に移動可能である。
即ちループになっているのでどからでも始められる。
なお、おまけ２の全探索の結果、ループ解は,パターンとてしては問題１解の１とおりであることが判った。
【おまけ２】
３４通り。 （しらみつぶしＰＣ解）
因みに ４からは１０通り、
８からは全部ループで４通りである。
探索結果
2→ 9→18→ 7→11→17→15→20→13→ 5→ 3→12→19→14→10→ 4→ 6→ 1→ 8→16→Open 2→ 9→18→16→ 8→17→11→ 7→15→20→ 13→ 5→ 3→12→19→14→10→ 4→ 6→ 1→Open 2→ 9→18→16→ 8→ 1→ 6→17→11→ 7→ 15→20→13→ 5→ 3→12→19→14→10→ 4→Open 2→ 9→18→16→ 8→ 1→ 6→17→11→ 7→ 15→20→13→ 4→10→14→19→12→ 3→ 5→Open 2→ 9→18→16→ 8→ 1→ 6→17→11→ 7→ 15→ 4→10→14→19→12→ 3→ 5→13→20→Open 2→ 9→18→16→ 8→ 1→ 6→ 4→10→14→ 19→12→ 3→ 5→13→20→15→17→11→ 7→Close 2→ 9→18→16→ 8→ 1→ 6→ 4→10→14→ 19→12→ 3→ 5→13→20→15→ 7→11→17→Open 2→ 9→13→20→15→17→11→ 7→18→16→ 8→ 1→ 6→ 4→10→14→19→12→ 3→ 5→Open 2→ 9→13→ 5→ 3→12→19→14→10→ 4→ 6→ 1→ 8→16→18→ 7→11→17→15→20→Open 2→ 9→ 3→12→19→14→10→ 4→ 6→ 1→ 8→16→18→ 7→11→17→15→20→13→ 5→Open 2→ 9→ 3→ 5→13→20→15→17→11→ 7→ 18→12→19→14→10→ 4→ 6→ 1→ 8→16→Open 2→ 9→ 3→ 5→13→20→15→17→11→ 7→ 18→16→ 8→12→19→14→10→ 4→ 6→ 1→Open 2→ 9→ 3→ 5→13→20→15→17→11→ 7→ 18→16→ 8→ 1→ 6→ 4→10→14→19→12→Open 2→ 9→ 3→ 5→13→20→15→ 7→11→17→ 6→ 1→ 8→16→18→12→19→14→10→ 4→Open 2→ 9→ 3→ 5→13→20→15→ 7→11→17→ 6→ 4→10→14→19→12→18→16→ 8→ 1→Open 2→ 9→ 3→ 5→13→20→15→ 7→11→17→ 8→16→18→12→19→14→10→ 4→ 6→ 1→Open 2→ 9→ 3→ 5→13→20→15→ 7→11→17→ 8→ 1→ 6→ 4→10→14→19→12→18→16→Open 2→ 9→ 3→ 5→13→20→15→ 4→10→14→ 19→12→18→ 7→11→17→ 6→ 1→ 8→16→Open 2→ 9→ 3→ 5→13→20→15→ 4→10→14→ 19→12→18→16→ 8→ 1→ 6→17→11→ 7→Close 2→ 9→ 3→ 5→13→20→15→ 4→10→14→ 19→12→ 8→16→18→ 7→11→17→ 6→ 1→Open 2→ 9→ 3→ 5→13→20→15→ 4→10→14→ 19→12→ 8→ 1→ 6→17→11→ 7→18→16→Open 2→ 9→ 3→ 5→13→ 4→10→14→19→12→ 18→16→ 8→ 1→ 6→17→11→ 7→15→20→Open 2→ 7→11→17→ 6→ 1→ 8→16→18→12→ 19→14→10→ 4→15→20→13→ 5→ 3→ 9→Close 2→ 7→11→17→ 6→ 1→ 8→16→18→12→ 19→14→10→ 4→15→20→13→ 9→ 3→ 5→Open 2→ 7→11→17→ 6→ 1→ 8→16→18→ 9→ 13→20→15→ 4→10→14→19→12→ 3→ 5→Open 2→ 7→11→17→ 6→ 1→ 8→16→18→ 9→ 13→ 5→ 3→12→19→14→10→ 4→15→20→Open 2→ 7→11→17→ 6→ 1→ 8→16→18→ 9→ 3→12→19→14→10→ 4→15→20→13→ 5→Open 2→ 7→11→17→ 6→ 1→ 8→16→18→ 9→ 3→ 5→13→20→15→ 4→10→14→19→12→Open 2→ 7→11→17→ 6→ 1→ 8→12→19→14→ 10→ 4→15→20→13→ 5→ 3→ 9→18→16→Open 2→ 7→11→17→15→20→13→ 5→ 3→ 9→ 18→12→19→14→10→ 4→ 6→ 1→ 8→16→Open 2→ 7→11→17→15→20→13→ 5→ 3→ 9→ 18→16→ 8→12→19→14→10→ 4→ 6→ 1→Open 2→ 7→11→17→15→20→13→ 5→ 3→ 9→ 18→16→ 8→ 1→ 6→ 4→10→14→19→12→Open 2→ 7→11→17→15→20→13→ 5→ 3→12→ 19→14→10→ 4→ 6→ 1→ 8→16→18→ 9→Close 2→ 7→11→17→15→20→13→ 9→18→16→ 8→ 1→ 6→ 4→10→14→19→12→ 3→ 5→Open 4→10→14→19→12→18→16→ 8→ 1→ 6→ 17→11→ 7→15→20→13→ 5→ 3→ 9→ 2→Open 4→10→14→19→12→18→16→ 8→ 1→ 6→ 17→11→ 7→ 2→ 9→ 3→ 5→13→20→15→Close 4→10→14→19→12→18→16→ 8→ 1→ 6→ 17→15→20→13→ 5→ 3→ 9→ 2→ 7→11→Open 4→10→14→19→12→ 3→ 5→13→20→15→ 17→11→ 7→ 2→ 9→18→16→ 8→ 1→ 6→Close 4→10→14→19→12→ 3→ 5→13→20→15→ 17→ 6→ 1→ 8→16→18→ 9→ 2→ 7→11→Open 4→10→14→19→12→ 3→ 5→13→20→15→ 7→11→17→ 6→ 1→ 8→16→18→ 9→ 2→Open 4→10→14→19→12→ 3→ 5→13→20→15→ 7→ 2→ 9→18→16→ 8→ 1→ 6→17→11→Open 4→10→14→ 6→ 1→ 8→16→18→ 9→ 2→ 7→11→17→15→20→13→ 5→ 3→12→19→Open 4→15→20→13→ 5→ 3→ 9→ 2→ 7→11→ 17→ 6→ 1→ 8→16→18→12→19→14→10→Close 4→ 6→ 1→ 8→16→18→ 9→ 2→ 7→11→ 17→15→20→13→ 5→ 3→12→19→14→10→Close 8→16→18→12→19→14→10→ 4→15→20→ 13→ 5→ 3→ 9→ 2→ 7→11→17→ 6→ 1→Close 8→16→18→ 9→ 2→ 7→11→17→15→20→ 13→ 5→ 3→12→19→14→10→ 4→ 6→ 1→Close 8→ 1→ 6→17→11→ 7→ 2→ 9→ 3→ 5→ 13→20→15→ 4→10→14→19→12→18→16→Close 8→ 1→ 6→ 4→10→14→19→12→ 3→ 5→ 13→20→15→17→11→ 7→ 2→ 9→18→16→Close
◆宮城県 アンパンマン さんからの解答
【問題１】
２→９→18→16→８→17→11→７→15→20→
13→５→３→12→19→14→10→４→６→１
【おまけ１】
どの出発点も可能です。
理由は
1-8-16-18-9-2-7-11-17-15-20-13-5-3-12-19-14-10-4-6-1
のループは重複なしですべてのマス目を通ったため、
このループの中、出発点にしたいマス目とのつながり線一本を消せば、
残りの線を辿って行くと最後のマス目(つながり線のもう片方のマス目)に辿り着きます。
また OX
XO
OXOXOX
XOXOXO
OX
XO
という風に書き、奇偶を考慮して
Xの集合＝{1,4,5,7,9,12,14,16,17,20}で始まる場合
Oの集合＝{2,3,6,8,10,11,13,15,18,19}で終わらないといけません。
また逆にOで始まるとXで終わるということも言えます。
【おまけ２】
a_{ij}= 1 もしiからjに移動できる,
a_{ij}= 0 もしiからjに移動できない
と定義すると
A={aa_{ij}}は移動する行列を表し、
A=|0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0| |0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0| |0 0 0 0 1 0 0 0 1 0 0 1 0 1 0 0 0 0 0 0| |0 0 0 0 0 1 0 0 0 1 0 0 1 0 1 0 0 0 0 0| |0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0| |1 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0| |0 1 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 0| |1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 0| |0 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0| |0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0| |0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0| |0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 0| |0 0 0 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1| |0 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0| |0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 1| |0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0| |0 0 0 0 0 1 0 1 0 0 1 0 0 0 1 0 0 0 0 0| |0 0 0 0 0 0 1 0 1 0 0 1 0 0 0 1 0 0 0 0| |0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0| |0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0|です。 求めたい通り数(N_1)は
N_1=Σ_{全て異なるr_i≠１}a_{1,r_2}a_{r_2,r_3}...a_{r_19,r_20}
なのでかなりの計算量です。
(マス目をグラフの点にして、n点がある場合、(n-1)!個の値の総和が必要です)。
B={1,2,...,20}＝マス目の集合とします。
Q_B={Q_{(i,j),B}}、
Q_{(i,j),B}はB上で出発点はiで終点はjである重複無しで全ての点を通る経路数とすると、
Q_{(i,j),B}＝Σ_{k≠i} a_{i,k} Q_{(k,j),B(i)}の漸化式で表され、
ここでB(i)=B-{i}です。
C＝A-DiagonalMatrix(A), C(i)=Cのi番目の行とし、
(この問題ではDiagonalMatrix(A)＝０ため、C＝A)
Aはn*nサイズの行列とすると
Q_{B}= | C(1)Q_{B(1)} |
| C(2)Q_{B(2)} |
| : |
| C(n)Q_{B(n)} | が成り立ちますが、この式で計算するのもかなり計算量が必要ですので、別の方法で計算してみます。
まず,P_r (i,j)=B上で出発点はiで終点はjで重複なしでrの長さの経路数
(Number of Path)で、P_r={P_r(i,j)}と定義します。
また
L_r(i,j)=0 もしi≠j
L_r(i,j)=出発点と終点はiで重複なしでrの長さのループ数(Number of Loop)で、
L_r={L_r(i,j)}と定義します。
定理：P_1=A-L_1で表され、さらにP_kはP_1,P_2,....,P_{k-1}で表すことができます。(証明省略)
例として P_1=A-L_1,
P_2=P_12-L_2
P_3=P_2P_1-L_3-P_1*L_2+P_1
P_4=P_3P_1-L_4-P_1L_3+3P_1*P_2-P_2L_2+P_2
P_5=P_4P_1-L_5-P_1L_4+3P_1*P_3+3P_1*P_2(2)+3P_1(P_1*P_2)-3L_3+P_3-P_3*L_2-P_2L_3-4P_1P_2 P_6=P_5P_1-L_6-P_1L_5+3P_1*P_4+6P_1*P_2*P_3-8P_1*(P_1(P_1*P_2))-8P_1*((P_1*P_2)P_1)-P_2L_4+P_2(3)-4P_2(2)+3P_2+3P_1(P_1*P_3)+3P_1(P_1*P_2(2))-3L_4+21P_1*P_2-P_4L_2-P_3L_3+3P_2(P_1*P_2)-3P_1(P_1*P_2)+3L_3-6I*(P_1(P_2(2)))-4P_1L_3+P_4*の演算子は、A={a_{ij}},B_{b_{ij}}の場合、C＝A*B＝{a_{ij}b_{ij}}と定義します。
D(X)は正方行列から正方行列への関数でD(X)＝I*Xです。
また
L_k=D(P_{k-1}P_1)=D(P_1P_{k-1})=I*(P_{k-1}P_1)=I*(P_1P_{k-1})で求まります。
ちなみに上記のP_kの式は、 (k-1)の長さの経路(P_{k-1})プラス1の長さの経路(P_{1})から考えて得られた式です。
同じように、P_kの式を(k-2)と２の長さの経路から構成されると考えるとまた別の式が得られます。
この問題、n=20であるため、P_{19}までの式がわかると求めたい経路数が求まります。
P_{19}の式まで求めるのに困難でもありますが、他の類似問題にも使える
(Derive Once Calculate Anywhere)ので求める価値があると思います。
またP_1,...,P_{19}の式で計算することによって、全てのiからjまでのすべての長さの重複なしの経路数、またはiを通る重複無しのループ数もわかります。
さらに、ケースを分けることによって、P_{11}までわかれば、この問題を解くことができます。
類似問題として「右折禁止の平安京」問題や「今週の問題シリーズ」にでてきた経路数に関する問題などが挙げられます。
「右折禁止の平安京」問題の場合は格子点と格子点を結ぶ道路をグラフの点として考え, 次の道路に進めるかどうかを１と０で表して考えると、
m(m-1)+n(n-1)点の有向グラフ(Directed Graph)の重複無しの経路数の問題に変わります。
ただし、このグラフは有向グラフであるため、P_i の式を使うのではなく、有向グラフのためのQ_iの式を考えなければなりません。
Q_{m(m-1)+n(n-1)-1}までの式が解れば、経路数が計算できます。
(実際、この問題の性質により、P_{m(m-1)+n(n-1)-1}までの式が必要ないはずです。)
◆東京都 You.O さんからの解答
まず【おまけ２】から。
２０コのマス目のうち隣接するマス目の数が２，３，４であるマス目の集合をそれぞれＡ，Ｂ，Ｃとする。
すなわち、
Ａ＝｛１，２，５，10，11，16，19，20｝，
Ｂ＝｛３，４，６，９，12，15，17，18｝，
Ｃ＝｛７，８，13，14｝である。
また、Ｕ＝Ａ∪Ｂ∪Ｃ＝｛１，２，３，・・・，20｝としておく。
次に、マス目@からマス目ｊへナイトが１回の動きで移動できるとき、@とｊは「結ばれている」と定義し、
これを“@＿ｊ”で表わすことにしておく。
当然のことながら、この定義には交換法則が成り立つ。
このとき、
(1)Ａの任意の要素ａに対して、ａ＿ｑ，ａ＿ｒを満たすＢ，Ｃの要素ｑ，ｒがそれぞれただ１つずつ存在し、ａ＿ｐを満たすＡの要素ｐは存在しない。
(2)Ｂの任意の要素ｂに対して、ｂ＿ｐ，ｂ＿ｒを満たすＡ，Ｃの要素ｐ，ｒがそれぞれただ１つずつ存在し、ｂ＿ｑを満たすＢの要素ｑ（ｑ≠ｂ）は２つ存在する。
(3)Ｃの任意の要素ｃに対して、ｃ＿ｐ，ｃ＿ｑを満たすＡ，Ｂの要素ｐ，ｑがそれぞれ２つずつ存在し、ｃ＿ｒを満たすＣの要素ｒは存在しない。
ナイトが移動するマス目の番号を順に並べた数列を考えると、この問題の解は次のような形で表される。
{Xi；０≦@≦19｝＝X0，X1，X2，・・・，X19
ただし
・X0＝２（∈Ａ）
・任意の@（０≦@≦19）に対してXi∈Ｕ
・任意の@（０≦@≦18）に対してXi＿X(i+1)
・任意の@，ｊ（０≦@＜ｊ≦19）に対してXi≠Xj
このとき
(1)より、Xi∈Ａ，X(i+1)∈Ａを満たす@（０≦@≦18）は存在しない。 ・・・(4)
(3)より、Xi∈Ｃ，X(i+1)∈Ｃを満たす@（０≦@≦18）は存在しない。 ・・・(5)
(1)より、Xi∈Ｂ，X(i+1)∈Ａ，X(i+2)∈Ｂを満たす@（０≦@≦17）は存在しない。・・・(6)
(1)より、Xi∈Ｃ，X(i+1)∈Ａ，X(i+2)∈Ｃを満たす@（０≦@≦17）は存在しない。・・・(7)
(2)より、Xi∈Ａ，X(i+1)∈Ｂ，X(i+2)∈Ａを満たす@（０≦@≦17）は存在しない。・・・(8)
(2)より、Xi∈Ｃ，X(i+1)∈Ｂ，X(i+2)∈Ｃを満たす@（０≦@≦17）は存在しない。・・・(9)
（T）X19∈ＢまたはX19∈Ｃのとき
上の数列｛Xi｝でＡの要素を出てくる順にa1，a2，a3，・・・，a8、Ｂの要素を出てくる順にb1，b2，b3，・・・，b8、Ｃの要素を出てくる順にc1，c2，c3，c4とする。
a1，a2，a3，・・・，a8，b1，b2，b3，・・・，b8，c1，c2，c3，c4の並び方は次のように（a8以降の並び方によって）場合分けされる。
ア）X18∈Ａ，X19∈Ｃの場合
a1,b1,b2,a2,c1,a3,b3,b4,a4,c2,a5,b5,b6,a6,c3,a7,b7,b8,a8,c4
イ）X17∈Ａ，X18∈Ｂ，X19∈Ｂの場合
a1,c1,a2,b1,b2,a3,c2,a4,b3,b4,a5,c3,a6,b5,b6,a7,c4,a8,b7,b8
ここで、０≦@≦16に対する（Xi（∈Ａ），X(i+1)（∈Ｂ），X(i+2)（∈Ｂ），X(i+3)（∈Ａ））の組と０≦@≦17に対する（Xi（∈Ａ），X(i+1)（∈Ｃ），X(i+2)（∈Ａ））の組を考えると、
（Xi（∈Ａ），X(i+1)（∈Ｂ），X(i+2)（∈Ｂ），X(i+3)（∈Ａ）） ＝（１，６，４，10），（１，６，17，11），（２，９，３，５），（２，９，18，16）， （５，３，９，２），（５，３，12，19），（10，４，６，１），（10，４，15，20）， （11，17，６，１），（11，17，15，20），（16，18，９，２），（16，18，12，19）， （19，12，３，５），（19，12，18，16），（20，15，４，10），（20，15，17，11） （Xi（∈Ａ），X(i+1)（∈Ｃ），X(i+2)（∈Ａ）） ＝（１，８，16），（２，７，11），（５，13，20），（10，14，19）， （11，７，２），（16，８，１），（19，14，10），（20，13，５）これを用いて（a1，a2，a3，・・・，a8）の組を決定すると、
ア）の場合 （a1，a2，a3，・・・，a8）＝（２，５，20，10，19，16，１，11），（２，16，１，10，19，５，20，11） イ）の場合 （a1，a2，a3，・・・，a8）＝（２，11，１，16，19，10，20，５），（２，11，20，５，19，10，１，16）これら４つのいずれの場合にも、b1，b2，b3，・・・，b8およびc1，c2，c3，c4はそれぞれ一意的に定まり、a1，a2，a3，・・・，a8と合わせた２０コの数はすべて異なる。
ア）・・・２通り
イ）・・・２通り
ウ）X18∈Ａ，X19∈Ｂの場合
（U）の考え方を適用する。
X1∈｛７，９｝，X19∈（Ｂ∩Ｅ）＝｛４，９，12，17｝であり、
『ｘ＿ｙ（ｘ∈Ｕ，ｙ∈Ｕ）を満たす３２の組のうち用いられない１３組をすべて書き出すと、
その中にX0（＝２）が１コ，X19（∈Ｂ）が３コ、X19以外のＢの要素およびＣの要素が各２コずつ現れる』はずである。
（１）X1＝７の場合
（あ）X19＝４のとき
ｘ＿ｙ（ｘ∈Ｕ，ｙ∈Ｕ）を満たす３２の組のうち、（@）の（ｘ，ｙ）＝（２，９），（B）の（ｘ，ｙ）＝（４，６），（４，15）および（C）の８組すべてが用いられない。
用いられない組はあと２つであるが、残りの組の中から２組をどのように選んでも、上の『 』内の条件を満たさない。
（い）X19＝９のとき
（あ）と同様、『 』の条件を満たす１３組の選び方は存在しない。
（う）X19＝12のとき
（@）の（ｘ，ｙ）＝（２，９），（B）の（ｘ，ｙ）＝（３，12），（12，18）および（C）の８組すべてが用いられない。
『 』の条件を満たす残り２組の選び方は、
（B）の（ｘ，ｙ）＝（４，６），（15，17）または（ｘ，ｙ）＝（４，15），（６，17）の２通り。
このそれぞれについて１通りずつのナイトの進め方が存在する。
（え）X19＝17のとき
（あ）と同様、『 』の条件を満たす１３組の選び方は存在しない。
（２）X1＝９の場合
同じように考えて、X19＝４のとき２通り、X19＝12のとき１通り，X19＝17のとき１通り、計４通りのナイトの進め方が存在する。
ア）の２通り、イ）の２通り、ウ）の６通りを合わせて、（T）の場合のナイトの進め方は１０通り。
（U）X19∈Ａのとき
Ｄ＝｛２，３，６，８，10，11，13，15，18，19｝
Ｅ＝｛１，４，５，７，９，12，14，16，17，20｝
とすると、ナイトの移動の性質から、任意のｍ（０≦ｍ≦９）に対して、
X(2m)∈Ｄ，X(2m+1)∈Ｅとなる。ゆえに、
X(19)∈（Ａ∩Ｅ）＝｛１，５，16，20｝
ところで(1)〜(3)より、
(10)Ａの任意の要素ａに対して、ａ＿ｘを満たすＵの要素ｘが２つ存在する。
(11)Ｂの任意の要素ｂに対して、ｂ＿ｘを満たすＵの要素ｘが４つ存在する。
(12)Ｃの任意の要素ｃに対して、ｃ＿ｘを満たすＵの要素ｘが４つ存在する。
一方、数列｛Xi｝は次のような性質を持っている。
・X1はX0＿ｘを満たすＵの要素ｘのうちの１つである。
・任意の@（１≦@≦18）に対して、X(i-1)とX(i+1)はXi＿ｘを満たす相異なるＵの２つの要素である。
・X18はX19＿ｘを満たすＵの要素ｘのうちの１つである。
また、ｘ＿ｙを満たすＵの（相異なる）要素（ｘ，ｙ）は下の３２組であり、そのうち１９組が数列｛Xi｝を構成するのに用いられるから、残りの１３組は用いられないこととなる。
（@）ｘ∈Ａ，ｙ∈Ｂの場合 （ｘ，ｙ）＝（１，６），（２，９），（５，３），（10，４）， （11，17），（16，18），（19，12），（20，15） （A）ｘ∈Ａ，ｙ∈Ｃの場合 （ｘ，ｙ）＝（１，８），（２，７），（５，13），（10，14）， （11，７），（16，８），（19，14），（20，13） （B）ｘ∈Ｂ，ｙ∈Ｂの場合 （ｘ，ｙ）＝（３，９），（３，12），（４，６），（４，15）， （６，17），（９，18），（12，18），（15，17） （C）ｘ∈Ｂ，ｙ∈Ｃの場合 （ｘ，ｙ）＝（３，14），（４，13），（６，14），（７，15）， （７，18），（８，12），（８，17），（９，13）(10)〜(12)および上で述べた数列｛Xi｝の性質と
ア）X1∈Ｃ，X18∈Ｃのとき
このとき、上の（A）の８組すべてが数列｛Xi｝の構成に用いられることと(13)から、（C）の８組はすべて用いられない。
また、X0＝２であるから、（@）の（ｘ，ｙ）＝（２，９）は用いられない。
例として、X19＝１の場合を考えると、（@）の（ｘ，ｙ）＝（１，６）は用いられず、残り３組の用いられない組み合わせはすべて（B）に属することになるが、(13)の条件を満たすように、（B）の中から用いられない３組を選ぶことはできない。
X19＝５の場合には、（B）の８組の組み合わせと(13)を考慮すると用いられない組み合わせは次のようになる。
（@）の（ｘ，ｙ）＝（２，９），（５，３），（C）の８組すべて，
（B）の［あ］（ｘ，ｙ）＝（４，６），（12，18），（15，17）または
［い］（ｘ，ｙ）＝（４，15），（12，18），（６，17）
［あ］の場合
｛Xi｝＝２，７，11，17，６，１，８，16，18，９，３，12，19，14，10，４，15，20，13，５
［い］の場合
数列｛Xi｝をつくることができない。
（X0から順に決定してゆくと、X7＝５＝X19となる）
同様にして、X19＝16の場合に１通りの動かし方があり、X19＝20の場合には動かし方がないことがわかる。
すなわち、条件を満たす場合が２通りある。
イ）X1∈Ｂ，X18∈Ｃのとき
このとき、上の（A）の（ｘ，ｙ）＝（２，７）は｛Xi｝の構成に用いられないが、それ以外の７組は用いられる。
ゆえに(13)から、（C）の８組のうちただ１組は用いられ、それ以外の７組はすべて用いられないことがわかる。
(13)を考慮すると、用いられない１３組の組み合わせの中に“７”がちょうど２回現れることから、（C）の中で用いられる組み合わせは
（ｘ，ｙ）＝（７，15）または（７，18）であることがわかる。
さらに（B）の８組の組み合わせから、X19＝１，20のとき、
この組み合わせは（ｘ，ｙ）＝（７，15）に決定し、
X19＝５，16のときは（ｘ，ｙ）＝（７，18）に決定することがわかる。
他の組み合わせも考慮して、X19＝１，５，20のとき各１通りずつ、X19＝16のとき３通りの計６通りの動かし方を発見することができる。
ウ）X1∈Ｃ，X18∈Ｂのとき
同様にして、X19＝１，16，20のとき各１通りずつ、X19＝５のとき３通りの計６通りの動かし方があることがわかる。
エ）X1∈Ｂ，X18∈Ｂのとき
同様にして、X19＝５，16，20のとき各２通りずつ、X19＝１のとき４通りの計１０通りの動かし方があることがわかる。
ア）〜エ）まで合わせて（U）は２４通りの動かし方がある。
（T）の１０通り、（U）の２４通りを合わせて、ナイトの進め方は全部で３４通り。
考え方がイマイチよく伝わらないと思いますので補足をしておきます。
任意の（ｘ，ｙ）の組（１≦ｘ＜ｙ≦20）について、２点ｘ，ｙの間をナイトが１回の動きで移動可能なときのみｘとｙを線で結んだ図を描くと下のようになります。
ナイトが１９回の移動でたどる経路は、この図中の番号のついた点を両端にもつ３２本の線のうち、１９本の線で表されます。
そこで、ナイトが通らない１３本の経路の選び方を考えるわけです。
Ａの要素となる各点（１，２，５，10，11，16，19，20）からはそれぞれ２本、ＢおよびＣの要素となる各点からはそれぞれ４本の経路が出ているわけですが、ナイトが同じ点を重複して通ることなく１９回移動したときの経路を図に表すと、スタート地点（２）とゴール地点からは各１本ずつの線が、それ以外の１８コの点からは各２本ずつの線が出ていなければなりません。
ただし、スタート・ゴール地点以外の１８コの点のうちいくつかが次の例のようにループを形成してしまうことがあるので要注意！
例．ナイトを通らない１３本の経路を次のように選ぶ。
２−９，３−５，３−14，４−13，４−15，６−14，６−17，
７−15，７−18，８−12，８−17，９−13，12−18
このとき、残りの１９本の経路のうちの１２本が、
１−６−４−10−14−19 ｜ ｜ ８−16−18−９−３−12というループを形成し、２からスタートするナイトの動きは、
２−７−11−17−15−20−13−５
で終わってしまう。
以上のことに注意すれば、考えられるナイトの移動経路は上の例のような場合を含めても６０種類程度にあらかじめしぼっておくことができ、ＰＣを使わずに解くことができます。
時間はやっぱりかかりますけどね。
【おまけ１】
上の【おまけ２】の解答で述べた（Ｉ）の場合の解は、
X19＿X0（＝２）を満たす。すなわち、ナイトは
X0，X1，X2，・・・，X19，X0，X1，X2，・・・
というように１から20までのすべてのマス目を１つずつ周期的に移動することができる。
いま、出発点の番号をｋ（１≦ｋ≦20）とすると、
｛X0，X1，X2，・・・，X19｝＝Ｕ＝｛１，２，３，・・・，20｝であるから、
任意のｋの値に対してXi＝ｋとなる@の値（０≦@≦19）が必ずただ１つ存在する。
その値をｎとすると、出発点がｋの場合には、
Xk，X(k+1)，・・・，X19，X0，X1，X2，・・・，X(k-1)
というようにナイトを移動すればよい。
したがって、すべてのマス目を一回ずつ通って進むことが不可能な出発点は存在しない。
例として、（T）の場合の解の１つ（これが【問題１】の解答ということにしておきます）
２，９，３，５，13，20，15，４，10，14，19，12，18，16，８，１，６，17，11，７
をもとにしたとき、16を出発点としたときのナイトの進め方は次のようになります。
16，８，１，６，17，11，７，２，９，３，５，13，20，15，４，10，14，19，12，18
全３４通りのナイトの進め方は以下の通りです。
２−９−３−５−13−20−15−４−10−14−19−12−18−16−８−１−６−17−11−７ ２−９−18−16−８−１−６−４−10−14−19−12−３−５−13−20−15−17−11−７ ２−７−11−17−６−１−８−16−18−12−19−14−10−４−15−20−13−５−３−９ ２−７−11−17−15−20−13−５−３−12−19−14−10−４−６−１−８−16−18−９ ２−７−11−17−６−１−８−16−18−９−３−５−13−20−15−４−10−14−19−12 ２−７−11−17−15−20−13−５−３−９−18−16−８−１−６−４−10−14−19−12 ２−９−３−５−13−20−15−７−11−17−６−１−８−16−18−12−19−14−10−４ ２−９−18−16−８−１−６−17−11−７−15−20−13−５−３−12−19−14−10−４ ２−９−３−５−13−20−15−17−11−７−18−16−８−１−６−４−10−14−19−12 ２−９−18−16−８−１−６−４−10−14−19−12−３−５−13−20−15−７−11−17 ２−７−11−17−６−１−８−16−18−９−３−12−19−14−10−４−15−20−13−５ ２−７−11−17−15−20−13−５−３−９−18−12−19−14−10−４−６−１−８−16 ２−９−３−５−13−20−15−７−11−17−６−４−10−14−19−12−18−16−８−１ ２−９−３−12−19−14−10−４−６−１−８−16−18−７−11−17−15−20−13−５ ２−９−３−５−13−20−15−４−10−14−19−12−18−７−11−17−６−１−８−16 ２−９−３−５−13−20−15−17−11−７−18−12−19−14−10−４−６−１−８−16 ２−９−18−７−11−17−15−20−13−５−３−12−19−14−10−４−６−１−８−16 ２−９−18−16−８−１−６−17−11−７−15−４−10−14−19−12−３−５−13−20 ２−７−11−17−15−20−13−５−３−９−18−16−８−12−19−14−10−４−６−１ ２−７−11−17−６−１−８−16−18−９−13−20−15−４−10−14−19−12−３−５ ２−７−11−17−６−１−８−16−18−12−19−14−10−４−15−20−13−９−３−５ ２−７−11−17−15−20−13−９−18−16−８−１−６−４−10−14−19−12−３−５ ２−７−11−17−６−１−８−12−19−14−10−４−15−20−13−５−３−９−18−16 ２−７−11−17−６−１−８−16−18−９−13−５−３−12−19−14−10−４−15−20 ２−９−３−５−13−20−15−４−10−14−19−12−８−16−18−７−11−17−６−１ ２−９−３−５−13−20−15−７−11−17−８−16−18−12−19−14−10−４−６−１ ２−９−３−５−13−20−15−17−11−７−18−16−８−12−19−14−10−４−６−１ ２−９−18−16−８−17−11−７−15−20−13−５−３−12−19−14−10−４−６−１ ２−９−13−20−15−17−11−７−18−16−８−１−６−４−10−14−19−12−３−５ ２−９−18−16−８−１−６−17−11−７−15−20−13−４−10−14−19−12−３−５ ２−９−３−５−13−20−15−４−10−14−19−12−８−１−６−17−11−７−18−16 ２−９−３−５−13−20−15−７−11−17−８−１−６−４−10−14−19−12−18−16 ２−９−３−５−13−４−10−14−19−12−18−16−８−１−６−17−11−７−15−20 ２−９−13−５−３−12−19−14−10−４−６−１−８−16−18−７−11−17−15−20
◆ 問題へもどる
◆ 今週の問題へ
数学の部屋へもどる