Think Stitch
  最近の更新

Pebbling a Chessboard

Pebbling a Chessboard というパズルを紹介します.

名前を忘れていたのですが,Twitter で hist102 さんに名前とビデオの存在を教えてもらいました.

右方向と上方向に無限に広がっている格子平面を考えます.マス目に駒があって,右隣りと上隣りが空いているとき,下図のように駒が分裂移動できるものとします.

はじめは下図のように平面の左下角に3個の駒が配置されているとします.これを上のルールにしたがって移動させて,結果的に緑の枠の中から駒をなくすことができるでしょうかというのが問題です.

以下解答を書くので,自分で考えてみたい人は見ないように気をつけてください.

余白の代わりに数式でも置いておきましょうか.

\[ S = \sum_{k=0}^\infty p^k \]

\[ \begin{split} pS &= \sum_{k=0}^\infty p^{k+1} \\ &= \sum_{k=1}^\infty p^k \\ &= \sum_{k=0}^\infty p^k - 1 \\ &= S - 1 \end{split} \]

\[ S = \frac{1}{1-p} \]

0  不変条件

答えは「できない」です.

不可能であることを証明するときに役に立つ考え方の1つは不変条件に着目することです.ルールにしたがって駒を動かすときに,常に成り立つ不変な条件があったとします.もし目指しているゴールがその条件を満たしていなければ,ゴールにたどり着くことができないことがわかります.

下図のように,平面上のマス目に左下から順に数を割り当てます.対角線が1つ進むごとに値を半分にします.

あるマス目に駒があって,そのマス目に割り当てられた数を $x$ とします.この駒を分裂移動させると2つになりますが,そのマス目の値はどちらも $x/2$ ですから合計値は変わりません.

つまり,駒が配置されているマス目の数の合計は,どのように駒を動かしても変わらないというわけです.初期状態では3つの駒があって,その数の合計は2ですから,ルールにしたがって移動している限り,どのような配置になったとしても合計値は2のままです.

ここで,平面に割り当てられた数の総和を求めてみます. $0$ から数えて $k$ 番目の対角線上にあるマス目の数は $1/2^k$ で,対角線上のマス目は $k+1$ 個ありますから合計値 $S$ は次のように書けます.

\[ S=\sum_{k=0}^\infty \frac{k+1}{2^k} \]

これは次のようにして計算できます.まず $2S$ を変形して

\[ \begin{split} 2S &= \sum_{k=0}^\infty \frac{k+1}{2^{k-1}} \\ &= 2 + \sum_{k=1}^\infty \frac{k+1}{2^{k-1}} \\ &= 2 + \sum_{k=0}^\infty \frac{k+2}{2^{k}} \end{split} \]

これから $S$ の定義式を辺々引くと

\[ \begin{split} 2S - S &= 2 + \sum_{k=0}^\infty \frac{1}{2^{k}} \\ &= 2 + \frac{1}{1 - 1/2} \\ &= 4 \end{split} \]

つまり $S=4$ です.これはどういうことかというと,初期状態の3個の数の合計が2ですから,残りのマス目すべてを無限個の駒で埋め尽くしたとしてやっと合計が2になるということです.しかし駒は有限個しかありませんから,結局緑の枠の外にどのように駒を配置しても2にはなりません.つまりすべての駒を枠の外に持っていくことはできないというわけです.

1  高次元化

次元を上げたらどうなるのだろうと思いました. $n$ 次元の場合は各座標軸方向 $n$ 個に分裂するとします.

2次元のときと同様に考えて,合計値が不変となるようにマス目に割り当てる数は $1/n$ ずつ減少するようにします.

$n$ 次元での超平面 $x_1 + x_2 + \ldots + x_n = k$ 上にあるマス目の数は ${k+n-1}\choose{n-1}$ となります.($k$ 個のボールと $n-1$ 個のしきりを並べる場合の数を考えればわかります.)

すると $n$ 次元空間上のすべての数の合計はつぎのように書けます.

\[ S_n = \sum_{k=0}^{\infty} {{k+n-1}\choose{n-1}} \frac{1}{n^k} \]

これを求めるために,ちょっと一般化して次の値を考えます.

\[ S(n, j) = \sum_{k=0}^{\infty} {{k+n-1}\choose{j}} \frac{1}{n^k} \]

いつものように指数をずらすために $n$ をかけて変形します.

\[ \begin{split} nS(n, j) &= n \sum_{k=0}^{\infty} {{k+n-1}\choose{j}} \frac{1}{n^k} \\ &= \sum_{k=0}^{\infty} {{k+n-1}\choose{j}} \frac{1}{n^{k-1}} \\ &= n{{n-1}\choose{j}} + \sum_{k=1}^{\infty} {{k+n-1}\choose{j}} \frac{1}{n^{k-1}} \\ &= n{{n-1}\choose{j}} + \sum_{k=0}^{\infty} {{k+n}\choose{j}} \frac{1}{n^k} \end{split} \]

もとの定義式と辺々引いて,組み合わせの漸化式を使います.

\[ \begin{split} nS(n, j) - S(n,j) &= n{{n-1}\choose{j}} + \sum_{k=0}^{\infty} \left\{ {{k+n}\choose{j}} - {{k+n-1}\choose{j}} \right\} \frac{1}{n^k} \\ &= n{{n-1}\choose{j}} + \sum_{k=0}^{\infty} {{k+n-1}\choose{j-1}} \frac{1}{n^k} \\ &= n{{n-1}\choose{j}} + S(n, j-1) \end{split} \]

整理すると次のようになりました.

\[ (n-1)S(n, j) - S(n,j-1) = n{{n-1}\choose{j}} \]

これを差分の形にするために $(n-1)^{j-1}$ をかけます.

\[ (n-1)^j S(n, j) - (n-1)^{j-1}S(n,j-1) = n{{n-1}\choose{j}} (n-1)^{j-1} \]

これで数列 $(n-1)^j S(n, j)$ の差分の形になりましたから,$j=1$ から $n-1$ まで加えると両側だけ残ります.

\[ (n-1)^{n-1} S(n, n-1) - (n-1)^0 S(n,0) = \sum_{j=1}^{n-1} n{{n-1}\choose{j}} (n-1)^{j-1} \]

$S(n, 0)$ は等比級数です.

\[ \begin{split} S(n,0) &= \sum_{k=0}^{\infty} {{k+n-1}\choose{0}} \frac{1}{n^k} \\ &= \sum_{k=0}^{\infty} \frac{1}{n^k} \\ &= \frac{1}{1 - 1/n} \\ &= \frac{n}{n-1} \end{split} \]

右辺の和はよく見ると2項展開の形をしています.

\[ \begin{split} & \sum_{j=1}^{n-1} n{{n-1}\choose{j}} (n-1)^{j-1} \\ =& \frac{n}{n-1} \sum_{j=1}^{n-1} {{n-1}\choose{j}} (n-1)^{j} \\ =& \frac{n}{n-1} \left\{ \sum_{j=0}^{n-1} {{n-1}\choose{j}} (n-1)^{j} - 1 \right\} \\ =& \frac{n}{n-1} ( n^{n-1} - 1 ) \end{split} \]

これで $S_n$ が求まりました.$n=2$ のときは確かに $4$ です.

\[ S_n = S(n, n-1) = \left(\frac{n}{n-1}\right)^n \]

この値は単調に減少するので,次元が上がるほど条件は厳しくなり,高次元でもできないことがわかります.

ちなみに次のように変形すると,もとの定義式が自明に見えます.眼力のある人なら気がついたかもしれません.

\[ \begin{split} S_n &= \left(\frac{n}{n-1}\right)^n \\ &= \left(\frac{1}{1-1/n}\right)^n \\ &= \left(\sum_{k=0}^\infty \frac{1}{n^k}\right)^n \end{split} \]

ちょっと面白いのは極限で自然対数の底(Napier数) $e$ が出てくることです.これも直観的な説明があるかもしれません.

\[ \begin{split} S_n &= \left(\frac{n}{n-1}\right)^n \\ &= \left(1 + \frac{1}{n-1}\right)^n \\ &= \left(1 + \frac{1}{n-1}\right)^{n-1}\left(1 + \frac{1}{n-1}\right) \\ &\rightarrow e \quad (n \rightarrow +\infty) \end{split} \]

すましたことをいってますが,実は先にプログラムを書いて動かしてみたら $e$ に収束しそうだと気づいたのでした.

double series(long n)
{
    double s = 0.0;
    double t = 1.0;
    double r = 1.0 / n;
    long k = 0;
    double c = 1.0;
    double d;
    do {
        d = c * t;
        s += d;
        t *= r;
        c = (c / (k + 1)) * (k + n);
        k++;
    } while (d > 1e-14);
    return s;
}

同じような問題として「コンウェイの兵隊 (Wikipedia)」というのがあります.

2017/11/30

© 2013-2017 PRINCIPIA Limited