石取りゲーム                               戻る

 当HPがいつもお世話になっているHN「GAI」さんからの出題です。
                                        (平成27年6月9日付け)

 3×4の碁盤(正方形が縦に3、横に4連なる形状)があり、これを仕切る線の交点(格子点)
上の20ヶ所に碁石を置いておく。今、この左下から碁石を取り始め、次は右横に進んで次
の碁石を取るものとする。

 このとき、全ての碁石を取って元の位置(格子点の左下)へ戻ってこれる方法は何通りあ
るか?

 ただし、全ての格子点は一度しか通過できなく、進む方向は水平か垂直に限るとする。

<ヒント> 手作業でも頑張れば全ルートを発見できる総数です。

 そこで、今度はこれの2倍、3×8の碁盤(格子点数36個)ならば、ルートの総数は何通り
あるか?

<ヒント> 手作業では無理だと思います。


























(答) DD++さんが考察されました。(平成27年6月9日付け)

3×1 0+1=1通り
3×2 1+1=2通り
3×3 2+4=6通り
3×4 6+6=12通り
3×5 12+19=31通り
3×6 31+37=68通り
3×7 68+100=168通り
3×8 168+216=384通り

なんかミスってそう。


 らすかるさんが考察されました。(平成27年6月9日付け)

 格子点を、以下のようにA〜Tとして

ABCDE
FGHIJ
KLMNO
PQRST


 地道に数えたら、次の14通りがありましたので、多分12通りではないと思います。(自信
はありません。まだ数え落としている可能性もあります。)

PQRSTOJEDCBAFGHINMLKP 、PQRSTOJEDCHINMLGBAFKP
PQRSTOJEDINMHCBAFGLKP 、PQRSTOJEDINMLGHCBAFKP
PQRSTONIJEDCBAFGHMLKP 、PQRSTONIJEDCHMLGBAFKP
PQRSTONMHIJEDCBAFGLKP 、PQRSTONMLGHIJEDCBAFKP
PQRMNSTOJEDIHCBAFGLKP 、PQRMHINSTOJEDCBAFGLKP
PQRMLGHINSTOJEDCBAFKP 、PQLMRSTONIJEDCHGBAFKP
PQLGHMRSTONIJEDCBAFKP 、PQLGHINMRSTOJEDCBAFKP


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


3×1 0+1=1通り
3×2 1+1=2通り
3×3 2+4=6通り
3×4 6+6=12通り・・・・・・もう少し多いです。
3×5 12+19=31通り・・・・・30台ですがまだあります。
3×6 31+37=68通り・・・・・90台です。
3×7 68+100=168通り・・・・230台です。
3×8 168+216=384通り・・・・590台です。


 DD++さんからのコメントです。(平成27年6月9日付け)

 「PQRSTOJEDCHINMLGBAFKP」・・・ あー、DCHIのとこでターンする形があるんですね。
これを見落としていました。「PQLGHINMRSTOJEDCBAFKP」も同様に。そして、列を増築し
ながら数えたので、ここから始まる系列と途中で似たような形になるものが全部抜けた、と。

 今度こそ。" "部分を修正して計算も合ったっぽいです。

パターンA・・・右端の4点を2個ずつにわけて回収する。

パターンB・・・右端の4点をまとめて回収する。

パターンX(条件を満たさない)・・・反時計回りの2つのループで全てを回収する。ただし右端
                     はそれぞれのループで2個ずつ回収する。
             "右端2個をただ往復する形に限り同じ場所を2回通ることを許可する。"

とすると、 A[n] = A[n-1] + B[n-1]

       B[n] = 2A[n-2] + 3B[n-2] + X[n-2]

       X[n] = 2A[n-1] + 2B[n-1] + X[n-1]

という漸化式ができる。

 A[1] = 0、B[1] = 1、B[2] = 1、X[1] = 1 から順に計算すると、

A[1] = 0、B[1] = 1、X[1] = 1 → 0+1=1通り
A[2] = 1、B[2] = 1、X[2] = 3  → 1+1=2通り
A[3] = 2、B[3] = 4、X[3] = 7  → 2+4=6通り
A[4] = 6、B[4] = 8、X[4] = 19 → 6+8=14通り
A[5] = 14、B[5] = 23、X[5] = 47 → 14+23=37通り
A[6] = 37、B[6] = 55、X[6] = 121 → 37+55=92通り
A[7] = 92、B[7] =144 → 92+144=236通り
A[8] = 236、B[8] = 360 → 236+360=596通り


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

 完全正解です。

(参考) A006864によれば、

  漸化式:a(n)=2a(n-1)+2a(n-2)-2a(n-3)+a(n-4)
      a(0)=0、a(1)=1、a(2)=2、a(3)=6

  母関数 G(x)=x2/(1-2x-2x2+2x3-x4)

だそうです。これと類似して、

 A006865A145401A145416A145418A160149A003763A222200

などが調査されていました。これらの問題分野として、Hamiltonian Cycle についていろいろ
と調べてみたら、ほんとにいろいろな図形パターンでの調査が既に奥深くなされていること
に驚きました。