Yet Another 雑記

再帰で解くらしい問題の一般項を求めたい

2018/10/30

「プログラマ脳を鍛える数学パズル」という本がある。

https://www.amazon.co.jp/dp/479814245X/

この本に「ブラックジャックで大儲け！？」という以下のような問題があった（適当に文言を変えている）。

ゲームを行い、勝つと 1 枚コインを得て、負けると 1 枚コインを失う。 最初、手持ちに nn 枚のコインがあった。 mm 回ゲームを行い、一度も手持ちのコインが 0 枚とならないようなコインの枚数の遷移の仕方は何通りあるか。

nn, mm は 1010, 2424 のように指定されているのだが、それはそれとして一般項を求められないのか気になり、色々やってみたので、そのプロセスをまとめる。

まず、求める通りを An,mA_{n, m}とおくと、以下のような漸化式が立てられる。

An,m={An−1,m−1+An+1,m−1(n>0,m>0)1(n>0,m=0)0(n=0)\newcommand{\arraystretch}{1.7} A_{n, m} = \left\{ \begin{array}{rcl} A_{n-1, m-1} + A_{n+1, m-1} & (n > 0, m > 0) \\ 1 & (n > 0, m = 0) \\ 0 & (n = 0) \end{array} \right.

勿論これにより与えられた nn, mm について再帰的に解くことはできるし、模範解答はそれで終了していた。しかし、一般項を求めるとなると、やたら単純に見えるのに難しい（実はそんなことない？）。

そこで別のアプローチを考えた。

以下のように、縦横 mm マスの格子を考える。左下の点からスタートし、ゲームに勝つと上に進み、負けると右に進むこととする。 以下では適当に座標系を設けることとする。

mm 回ゲームを行った時、上方向、右方向の移動の合計が mm となるから、点は x+y=mx + y = m 上にある。また、上・右にしか進んでいないためこれは最短経路である。

そして、その途中もしくは終了時にコインが 0 枚になったとすると、それは負けた回数 - 勝った回数が nn となった瞬間があるということであり、すなわち図に赤線で示した x−y=nx - y = n 上の点を一度は訪れたことを表す。

よって、求める通り An,mA_{n, m} は、図において一度も赤線 y=x−ny = x - n を訪れずに y=−x+my = -x + m に到達する最短経路の個数に他ならない。

この個数を考えるにあたって、逆に赤線 y=x−ny = x - n を一度以上通過する経路の個数 Bn,mB_{n, m}を考える。経路全体の個数は 2m2^m であるため

An,m=2m−Bn,mA_{n, m} = 2^m - B_{n,m}

となる。

Bn,mB_{n, m} について、最終到達地点が赤線の上もしくは左側にある経路の個数 Bn,m,LB_{n, m, L} と、赤線の上もしくは右側にある経路の個数 Bn,m,RB_{n, m, R} を求めて以下のように算出することを考える。なお、 nn と mm の偶奇が等しい時、最終到達地点が赤線の上である経路が存在する。この個数を Bn,m,BB_{n, m, B} とする。

Bn,m={Bn,m,L+Bn,m,R−Bn,m,B(n≡m(mod2))Bn,m,L+Bn,m,R(n≢m(mod2))\newcommand{\arraystretch}{1.7} B_{n, m} = \left\{ \begin{array}{rcl} B_{n, m, L} + B_{n, m, R} - B_{n, m, B} & (n \equiv m \pmod 2) \\ B_{n, m, L}+B_{n, m, R} & (n \not\equiv m \pmod 2) \end{array} \right.

上記のような「赤線を訪れた経路であって、最終到達地点が赤線の上もしくは右側にある経路」の個数を求めたい。最終到達地点が赤線の右側にあれば必ず赤線を跨ぐ必要があることを踏まえると、これは最終到達地点が赤線の上もしくは右側にある経路の個数そのものであることがわかる。

最終到達地点の xx 座標は右に進んだ回数に等しいから、それが赤線の右側、すなわち n+m2\frac{n + m}{2} 以上であればよい。言い換えると、上に進んだ回数が m−n+m2=m−n2m - \frac{n + m}{2} = \frac{m - n}{2} 以下であればよい。上に進んだ回数が ii 回の経路の個数は mCi{}_m C_i 個であることを踏まえると、求める個数は以下となる。

Bn,m,R={∑i=0⌊m−n2⌋mCi(n≤m)0(n>m)B_{n, m, R} = \left\{ \newcommand{\arraystretch}{1.7} \begin{array}{rcl} \sum\limits_{i=0}^{\lfloor \frac{m - n}{2} \rfloor} {}_m C _i & (n \leq m) \\ 0 & (n > m) \end{array} \right.

続いて上記のような「赤線を訪れた経路であって、最終到達地点が赤線の上もしくは左側にある経路」の個数を求めたい。

上記を満たすある経路について、最初に赤線を訪れた時点で、以降の上・右の移動を反転させ、右・上へ移動した経路（以下：操作後の経路）を考える。

以下では「赤線を訪れた経路のうち、最終到達地点が赤線の左側にある経路」を「左経路」、「赤線を訪れた経路のうち、最終到達地点が赤線の右側にある経路」を「右経路」と呼ぶ。

操作後の経路の最終到達地点は、もとの経路の最終到達地点を赤線を対称に折り返した地点である。もとの経路の最終到達地点は赤線の左側であるため、操作後の経路の最終到達地点は赤線の右側となる。操作が単射であることを考えると、全ての左経路に対して異なる右経路を得ることができるということとなり、よって左経路の個数は右経路の個数以下であることがわかる。

また、右経路にも同じ操作を行うことで、全ての右経路に対して異なる左経路を得ることができるため、右経路の個数は左経路の個数以下となることがわかる。

以上より左経路の個数は右経路の個数と等しく、

Bn,m,L={∑i=0⌊m−n2⌋mCi(n≤m)0(n>m)\newcommand{\arraystretch}{1.7} B_{n, m, L} = \left\{ \begin{array}{rcl} \sum\limits_{i=0}^{\lfloor \frac{m - n}{2} \rfloor} {}_m C _i & (n \leq m) \\ 0 & (n > m) \end{array} \right.

であることがわかる。

上述の通り、 nn と mm の偶奇が等しい時、最終到達地点が赤線の上である経路が存在し、 Bn,m,RB_{n, m, R}, Bn,m,LB_{n, m, L} のどちらにも含まれており、この経路の個数は「上に m−n2\frac{m - n}{2}回進む経路の個数」と等しく以下となる。

Bn,m,B={mCm−n2(n≤m)0(n>m)\newcommand{\arraystretch}{1.7} B_{n, m, B} = \left\{ \begin{array}{rcl} {}_m C _{\frac{m-n}{2}} & (n \leq m) \\ 0 & (n > m) \end{array} \right.

これも踏まえると、少なくとも一度赤線を訪れる最短経路の個数 Bn,mB_{n,m} は以下となる。

Bn,m={2∑i=0m−n2mCi−mCm−n2(n≤m,n≡m(mod2))2∑i=0⌊m−n2⌋mCi(n<m,n≢m(mod2))0(n>m)\newcommand{\arraystretch}{1.7} B_{n, m} = \left\{ \begin{array}{rcl} 2 \sum\limits_{i=0}^{\frac{m - n}{2}} {}_m C _i - {}_m C _{\frac{m-n}{2}} & (n \leq m, n \equiv m \pmod 2) \\ 2 \sum\limits_{i=0}^{\lfloor \frac{m - n}{2} \rfloor} {}_m C _i & (n < m, n \not\equiv m \pmod 2) \\ 0 & (n > m) \end{array} \right.

最短経路全体の個数は 2m2^m 個であるため、一度も赤線を訪れない最短経路の個数は

An,m={2m−2∑i=0m−n2mCi+mCm−n2(n≤m,n≡m(mod2))2m−2∑i=0⌊m−n2⌋mCi(n<m,n≢m(mod2))2m(n>m)\newcommand{\arraystretch}{1.7} A_{n, m} = \left\{ \begin{array}{rcl} 2 ^ m - 2 \sum\limits_{i=0}^{\frac{m - n}{2}} {}_m C _i + {}_m C _{\frac{m-n}{2}} & (n \leq m, n \equiv m \pmod 2) \\ 2 ^ m - 2 \sum\limits_{i=0}^{\lfloor \frac{m - n}{2} \rfloor} {}_m C _i & (n < m, n \not\equiv m \pmod 2) \\ 2 ^ m & (n > m) \end{array} \right.

となる。

Yet Another 雑記
Twitter