当ＨＰがいつもお世話になっているＨＮ「ＧＡＩ」さんからの出題です。（令和５年７月３日付け）
同じ大きさの立方体を４個横に並べたものを考える。このとき、２つの立方体が繋がってい
れば各頂点は合わさっているので、そこに一つの頂点があるものと考えると、上部と下部に
それぞれ１０個の頂点を持つ。上部の各頂点を、左上部の奥から時計回りに頂点 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] 全部の頂点を一度ずつ訪れて、出発点に最後戻ってこられるコースは、何処を出発点
にしておけば、最も多く存在できるか？また、それは何通りか？
（参考） 数え上げの問題
（答） [A] (1) 2918(通り) 、(2) 2188(通り) 、(3) 2116(通り)
[B] どの頂点から出発しても 612（通り）
うんざりはちべえさんからのコメントです。（令和５年７月４日付け）
一筆書きだと思いますが、Wikipedia一筆書きの「一筆書き可能かどうかの判定法」によると、
ある連結グラフが一筆書き可能な場合の必要十分条件は、以下の条件のいずれか一方が
成り立つことである（オイラー路参照）。
・ すべての頂点の次数（頂点につながっている辺の数）が偶数
（→運筆が起点に戻る場合（閉路））
・ 次数が奇数である頂点の数が２で、残りの頂点の次数は全て偶数
（→運筆が起点に戻らない場合（閉路でない路））
とあります。これを満足してますか？上図で見ると、頂点１、11、20、10、5、6、15、16 は辺
が３本で奇数で、8 個です。また、頂点 2、3、4、12、13、14、9、8、7、19、18、17 で、辺が４
本で偶数で、12 個です。
偶数の場合、「入→出」の繰り返しで通過点ですが、奇数は「出→入→出」か「入→出→入」
しかありえないので、出発点か終点です。だから、奇数は２つしかありえないのです。
勘違いでしたら、すみません。
ＧＡＩ さんからのコメントです。（令和５年７月４日付け）
{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 段目と称する。
全部の頂点を通り出発点に最後に戻るコースの数は、すべての頂点を通るループの数の
２倍(どちら周りかの区別)になるので、どこを出発点にしてもコースの数は変わらない。
その数を 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-j-1] 通りとなる。
以上の３つの場合の数を合わせると、(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 段目までのどこかの段でその段内の少なくとも
３点を通ることになるが、そうすると、部分列 b→…→d がその段を往復で通過するための
少なくとも２点が確保できないためありえない。
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」にハミルトン閉
路の数(=コース数の半分)が載っていました。ここの３項間漸化式を見るに、もっとシンプル
な考え方がありそうです。最初から半分の数で検索しておけばよかったのか……。
DD++ さんからのコメントです。（令和５年７月１１日付け）
りらひいさんのと考え方が共通する部分も多いですが、こんなのでどうでしょう。
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 つずれます。
以下、工事中！