世界一周旅行
同じ大きさの立方体を４個横に並べたものを考える。
このとき、２つの立方体が繋がっていれば各頂点は合わさっているのでそこに一つの頂点があるものと考えると
上部には１０個の、また下部にも１０個の頂点を持ち
上部の各頂点を左上部の奥から時計回りに頂点1,2,3,4,5,6,7,8,9,10
同じく頂点1の真下を頂点11として、時計回りに底部の頂点を12,13,14,15,16,17,18,19,20
の番号をつけておく。
このとき、
[A]出発点を指定して辺(合わさった所は一つの辺とする。)を辿って
すべての頂点を一度ずつ訪れられるコースが何通り可能かを調べて欲しい。
(1)出発点を頂点1と指定した場合。
(2)出発点を頂点2と指定した場合。
(3)出発点を頂点3と指定した場合。
次に
[B]全部の頂点を一度ずつ訪れて、出発点に最後戻ってこられるコースは何処を出発点にしておけば、
最も多く存在できるか？
またそれは何通りか？
GAI様、こんにちは。
一筆書きだと思いますが、Wikipedia一筆書きの「一筆書き可能かどうかの判定法」によると、
＊＊＊＊＊＊＊＊＊＊＊＊＊引用開始＊＊＊＊＊＊＊＊＊＊＊
ある連結グラフが一筆書き可能な場合の必要十分条件は、以下の条件のいずれか一方が成り立つことである（オイラー路参照）。
・ すべての頂点の次数（頂点につながっている辺の数）が偶数 →運筆が起点に戻る場合（閉路）
・ 次数が奇数である頂点の数が2で、残りの頂点の次数は全て偶数 →運筆が起点に戻らない場合（閉路でない路）
＊＊＊＊＊＊＊＊＊＊＊＊引用終了＊＊＊＊＊＊＊＊＊＊＊
とあります。これを満足してますか？
管理人さんの図で見ると、頂点１,11,20,10,5,6,15,16は辺が３本で奇数で8です。
また、頂点2,3,4,12,13,14,9,8,7,19,18,17で辺が4本で偶数で12です。
偶数の場合「入り→出」の繰り返しで、通過点ですが、奇数は「出→入り→出」か「入り→出→入り」しかありえないので、出発点か終点です。だから、奇数は2つしかありえないのです。
勘違いでしたらすみません。
{A]
(1)頂点1を出発点とする一つの経路
1->10->9->2->12->11->20->19->18->8->3->13->14->17->7->4->5->6->16->15
で各頂点を一度ずつ訪れている。
（別にすべての辺を通れとは要求されていない。）
[B]
で頂点1を出発点とした場合の一例
1->2->9->19->18->8->3->4->7->17->16->6->5->15->14->13->12->11->20->10->1
（勿論一筆で描けますが、通常の一筆書きの問題とは趣旨を異にします。）
[B]は、すべての辺を1回だけ通ってないので、一筆書きとは言えませんね。
＞勿論一筆で描けますが、通常の一筆書きの問題とは趣旨を異にします。
そうなるしかありませんね。私の勘違いでした、すみません。
[B]の方が比較的簡単そうなので、そちらだけやりました。
あっているかどうかは自信がありません。
n個の立方体を横に並べたものを考える。
左端の立方体の左側の4個の頂点を順番にA,B,C,Dとし、そのすぐ右側の4個の頂点をそれぞれa,b,c,dとする。
左からi番目の立方体の右側の4個の頂点(=i+1番目の立方体の左側の4個の頂点)をまとめてi段目と称する。
全部の頂点を通り出発点に最後に戻るコースの数は、すべての頂点を通るループの数の2倍(どちら周りかの区別)になるので、
どこを出発点にしてもコースの数は変わらない。その数を a[n] 通りとする。
以下ではAを出発点とするコースを考える。
1周してAに戻る一つ前の点はBかDかaのどれかであり、対称性からラスト前がBのコース数とラスト前がDのコース数は等しい。
このラスト前がBのコース数(=ラスト前がDのコース数)を b[n] 通りとする。
n=0の場合、すなわち単なる四角形ABCDを考えると、ラスト前がBのコースは
A→D→C→B→A
の1通りなので、 b[0]=1 であり、 a[0]=2 である。
n≧1の場合、0段目の4点を通る順番は以下の(1.1)から(3.4)までのいずれかになる。
(1.1) A→a→…→b→B→C→D→A
(1.2) A→B→b→…→c→C→D→A
(1.3) A→B→C→c→…→d→D→A
(1.4) A→B→C→D→d→…→a→A
(1.5) A→a→…→d→D→C→B→A
(1.6) A→D→d→…→c→C→B→A
(1.7) A→D→C→c→…→b→B→A
(1.8) A→D→C→B→b→…→a→A
(2.1) A→a→…→b→B→C→c→…→d→D→A
(2.2) A→B→b→…→c→C→D→d→…→a→A
(2.3) A→a→…→d→D→C→c→…→b→B→A
(2.4) A→D→d→…→c→C→B→b→…→a→A
(3.1) A→a→…→c→C→B→b→…→d→D→A
(3.2) A→B→b→…→d→D→C→c→…→a→A
(3.3) A→a→…→c→C→D→d→…→b→B→A
(3.4) A→D→d→…→b→B→C→c→…→a→A
〇(1.1)～(1.8)の場合
(1.1)を例に考えると、部分列a→…→bの箇所はn-1個の立方体でAを出発しラスト前がBになるコース数に等しいので b[n-1] 通りとなる。
(1.2)～(1.8)も同様に b[n-1] 通りである。
〇(2.1)～(2.4)の場合
(2.1)を例に考える。
部分列a→…→bの最高到達段をi段目、部分列c→…→dの最高到達段をj段目とする。
コースは全体としてすべての点を通るので、i,jの少なくとも一方はnとなる。
i=j=nの場合、二つの部分列はどちらも、右へ直進しn段目でひとつ隣へ移動し左へ直進して戻るコースしかないので、1通りである。
i<j=nの場合、部分列a→…→bは右へ直進しi段目でひとつ隣へ移動し左へ直進して戻ることになり、
部分列c→…→dはi+1段目まで右へ直進しi+1段目以降のすべての点を通った後i+1段目から1段目まで左へ直進することになる。
よってこの場合は、n-i-1個の立方体でAを出発しラスト前がBになるコース数に等しいので b[n-i-1] 通りとなる。
j<i=nの場合も同様に b[n-i-1] 通りとなる。
以上の3つの場合の数を合わせると(2.1)のコース数は、
1+2*Σ[i=1..n-1]b[n-i-1]
= 1+2*Σ[k=0..n-2]b[k]
通りとなる。
(2.2)～(2.4)も同様に 1+2*Σ[k=0..n-2]b[k] 通りである。
〇(3.1)～(3.4)の場合
結論として、この場合のコースは存在しない。その理由を以下に示す。
(3.1)を例に考える。
部分列a→…→cの最高到達段をi段目、部分列b→…→dの最高到達段をj段目とする。
コースは全体としてすべての点を通るので、i,jの少なくとも一方はnとなる。
i=j=nの場合、n段目までは直進で行き来するしかないが、n段目での二つの部分列のコースの両立ができないためこれはありえない。
i<j=nの場合、部分列a→…→cはi段目までのどこかの段でその段内の少なくとも3点を通ることになるが、
そうすると部分列b→…→dがその段を往復で通過するための少なくとも2点が確保できないためありえない。
j<i=nの場合も同様である。
以上より、(3.1)のコースは存在しないことがわかる。
(3.2)～(3.4)も同様である。
ここまでのことからn≧1のとき次の二つの式が得られる。
a[n] = 8*b[n-1] + 4*(1+2*Σ[k=0..n-2]b[k]) …式①
b[n] = 3*b[n-1] + 1*(1+2*Σ[k=0..n-2]b[k]) …式②
式②よりb[n]の漸化式
b[n] = 1 + 3*b[n-1] + 2*Σ[k=0..n-2]b[k] …式②'
が得られ、a[n]は式①から
a[n] = 4 + 8*Σ[k=0..n-1]b[k] …式①'
を使えば求まる。
GAIさんの問題[B]はn=4の場合なので、計算すると a[4]=612 通りとなる。
どうでしょうか、GAIさんが求めた数と同じになりましたでしょうか？
[A]
(1) 2918(通り)
(2) 2188(通り)
(3) 2116(通り)
であったのに対し
[B]
の元に戻れるコースに限定すると、どの頂点から出発しようが
元に戻れるコース数は一定で、りらひいさんが求められている612(通り)
ありました。
[A]の場合の様に出発点が異なれば当然異なる結果が起こるだろうと計算をすすめてみると、
勝手に決めつけていたことが見事に裏切られました。
しかし後から考えてみたら、閉じた経路はトポロジー的にどれも同じものであることになるように思えて納得しました。
頭の中だけでこの612を見つけられたことに驚きました。
どうやらあっていたようでよかったです。
n=4で成り立っているのならば漸化式は正しい可能性が高いですね。
とここまで書いた後、ふと思い立って調べてみたら、
OEISのA003699にハミルトン閉路の数(=コース数の半分)が載っていました。
ここの３項間漸化式を見るにもっとシンプルな考え方がありそうです。
最初から半分の数で検索しておけばよかったのか……。
私の投稿で一か所間違えていたので修正します。
〇(2.1)～(2.4)の場合 の中
誤：「j<i=nの場合も同様に b[n-i-1] 通りとなる。」
→
正：「j<i=nの場合も同様に考えて b[n-j-1] 通りとなる。」
りらひいさんのと考え方が共通する部分も多いですが、こんなのでどうでしょう。
n 個の立方体を左右一列に並べてある場合で考えます。
最も右側にある立方体の右側の面の頂点 4 つは、
・4 つを連続して通る（コ型）
・2 つをまず通り、後で残り 2 つを通る（二型）
のいずれかで通ることになります。
コ型のパターン数を コ[n], 二型のパターン数を 二[n] とします。
コ型について、右側の面の 4 頂点を削除して経路を短絡することを考えます。
GAI さんの図で例を挙げれば、……→4→5→6→16→15→14→…… を ……→4→14→…… に短絡するようなイメージです。
立方体 n+1 個の場合のコ型の経路全てを短絡すると、
立方体 n 個の場合のコ型の経路全種が 3 つずつおよび二型の経路全種が 2 つずつできるので、
コ[n+1] = 3*コ[n] + 2*二[n]
二型について、同様に考えます。
GAI さんの図で例を挙げれば、……→4→5→6→7→……→17→16→15→14→…… を ……→4→7→……→17→14→…… に短絡するようなイメージです。
立方体 n+1 個の場合の二型の経路全てを短絡すると、
立方体 n 個の場合のコ型の経路全種が 1 つずつおよび二型の経路全種が 1 つずつできるので、
二[n+1] = コ[n] + 二[n]
両漸化式から コ[n] を消去して
二[n+2] = 4*二[n+1] - 二[n]
また、コ[1] = 8, 二[1] = 4 なので、二[2] = 12, 二[3] = 44, 二[4] = 164, 二[5] = 612
よって、求める総数は コ[4] + 二[4] = 二[5] = 612 通りです。
ハミルトン閉路数も、a[n] = (1/2)*コ[n] + (1/2)*二[n] = (1/2)*二[n+1] と考えると、
a[1] = 6, a[2] = 22, a[n+2] = 4*a[n+1] - a[n]
という漸化式が成り立つことが示されます。
（ここでは n を立方体数として考えているので、A003699 とは n の値が 1 つずれます）
