14.4 机から突き出る本の長さ

本を机の端に、一部が机から出るように置く状況を想像してほしい。机から落ちない限り本を何冊でも積み重ねられるとき、机から突き出る部分の長さはどこまで長くできるだろうか？例えば、一番上の本が水平方向に机から完全に離れるように本を積み上げられるだろうか？もちろん、本を固定する接着剤などの道具は使えないとする。

この「本積み上げ問題」を尋ねると、多くの人はすぐに (あるいは少し考えてから) 「水平方向に本が机から完全に離れるような積み上げ方は存在しない」と答える。しかし実際には、一番上の本が机から突き出る長さに上限はない: 本一冊分でも、二冊分でも、いくらでも離れた位置に一番上の本が置かれる積み上げ方が存在する！

14.4.1 問題の定式化

この問題の定式化では再帰的な考え方を利用する。一冊の本を机の端に置くとき、机から突き出る部分はどれだけ長くできるだろうか？本が机から落ちるのは重心が机から離れたときだから、机から突き出る部分の長さは最大でも本の長さの半分である (図 \(\text{14.4}\))。

積み上がった本をスタック (stack) と呼び、机に置いても崩れないスタックを安定スタック (stable stack) と呼ぶことにする。安定スタックの重心から一番上の本の右端までの水平距離を、安定スタックの突き出し (overhang) と定義する。突き出しは安定スタックの性質であり、それを机にどのように置くかとは関係なく定まる。図 \(\text{14.5}\) のように重心が机の端に来るように安定スタックを配置すれば、その突き出しは一番上の本が机から突き出す部分の長さに等しくなる。

一般に、\(n\) 冊のスタックが安定スタックとなるのは、全ての \(i = 1, 2, \ldots, n - 1\) に対して上から \(i\) 冊の本の重心の水平座標が上から \(i + 1\) 冊目の本の占める水平区間に納まるときであり、かつそのときに限る。

では、可能な突き出しの最大値 \(B_{n}\) を表す式を求めよう。先ほど見たように、一冊の本は最大でその長さの半分だけ机から突き出るように置くことができる。よって次の等式が分かる:

\[ B_{1} = \frac{1}{2} \]

続いて、最大の突き出しを持つ \(n + 1\) 冊の安定スタック \(S\) が得られたと仮定する。このとき、\(S\) の上部 \(n\) 冊の本は安定スタックを構成する。もし、この \(n\) 冊の安定スタックが最大の突き出しを持たないなら、この部分を突き出しがより大きい安定スタックに置き換えることで \(S\) の突き出しを大きくできてしまう。よって \(n + 1\) 冊の安定スタックが持つ最大の突き出しは、最大の突き出しを持った \(n\) 冊の安定スタックを \(1\) 冊の本の上に配置したとき得られる。そして、その \(n\) 冊の安定スタックの重心が一番下の本の右端に来るとき全体の突き出しは最大になる。この状況を図 \(\text{14.6}\) に示す。

これで \(n + 1\) 冊目の本の配置方法が分かった。さらに前段落の議論からは、突き出しが最大になる安定スタックが一意だと分かる。続いて、この最大の突き出しの長さを求めよう。

この計算は上部 \(n\) 冊の重心を原点として左方向を正とする座標を考えると簡単になる。このとき \(n + 1\) 冊全体の重心の水平座標は、突き出しの増加量 \(B_{n+1} - B_{n}\) に等しい。また、一番下の本の重心は水平座標 \(1/2\) にある。これらの事実から、最大の突き出しを持つ \(n + 1\) 冊の安定スタックの重心の水平座標を計算できる:

\[ \frac{0\cdot n + (1/2) \cdot 1}{n + 1} = \frac{1}{2(n+1)} \]

ここから次の関係を得る:

\[ B_{n+1} = B_{n} + \frac{1}{2(n+1)} \tag{14.19}\]

この関係は図 \(\text{14.6}\) に示されている。

等式 \(\text{(14.19)}\) を展開すると次の等式を得る。

\[ \begin{align*} B_{n+1} &= B_{n-1} + \frac{1}{2n} + \frac{1}{2(n+1)} \\ &= B_{1} + \frac{1}{2 \cdot 2} + \cdots \frac{1}{2n} + \frac{1}{2(n + 1)} \\ &= \frac{1}{2} \sum_{i=1}^{n+1} \frac{1}{i} \tag{14.20} \end{align*} \]

続いて \(n\) が大きくなるときの \(B_{n}\) の振る舞いを調べよう。

14.4.2 調和数

定義 14.4.1

次の \(H_{n}\) を \(n\) 次調和数 (\(n\)-th harmonic number) と呼ぶ:

\[ H_{n} ::= \sum_{i=1}^{n} \frac{1}{i} \]

つまり等式 \(\text{(14.20)}\) は次の関係を意味する:

\[ B_{n} = \frac{H_{n}}{2} \]

低次の調和数は簡単に計算できる。例えば \(H_{4} = 1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} = \frac{25}{12} > 2\) が成り立つ。\(H_{4}\) が \(2\) より大きい事実は特別な重要性を持つ: これは、\(4\) 冊の本を積み上げれば突き出しを本一冊分より長くできることを意味する！この状況を図 \(\text{14.7}\) に示す。

最大の突き出しを持つ 4 冊の安定スタック — 図 14.7最大の突き出しを持つ \(4\) 冊の安定スタック

調和数に関して良いニュースと悪いニュースがある。悪いニュースから伝えると、調和数と等しい閉形式の式は知られていない。そして良いニュースは、\(H_{n}\) の優れた上界と下界が定理 14.3.2 を使って計算できることである。まず定積分を計算する:

\[ \int_{1}^{n} \frac{1}{x}\, dx = \left. \text{\large\mathstrut} \ln x\, \right|_{1}^{n} = \ln n \]

定理 14.3.2 からは、次の不等式が分かる:

\[ \ln n + \frac{1}{n} \leq H_{n} \leq \ln n + 1 \tag{14.21}\]

言い換えれば、\(n\) 次の調和数は \(\ln n\) にとても近い。

調和数は様々な問題で頻繁に姿を現すので、調和数のさらに正確な近似が熱心な数学者によって計算されている。具体的には、次の関係が知られている:

\[ H_{n} = \ln n + \gamma + \frac{1}{2n} + \frac{1}{12n^{2}} + \frac{\varepsilon (n)}{120n^{4}} \tag{14.22}\]

ここで \(\gamma = 0.577215664\ldots\) は Eulerオイラーの定数 (Euler's constant) と呼ばれる値であり、\(\varepsilon (n)\) は全ての \(n\) に対して \(0\) から \(1\) の間の値を取る。

これでようやく、本の積み上げ問題の解析が完了した。\(H_{n}\) の値を等式 \(\text{(14.20)}\) に代入すると、\(n\) 冊の安定スタックの突き出しの最大値は \(\ln n / 2\) に非常に近いと分かる。\(\ln n\) は \(n\) が大きくなるとき無限に大きくなるので、これは積み上げた本の一番上の本が机から突き出る部分の長さをいくらでも長くできることを意味する。ただし、必要になる本の冊数は突き出しの長さに関して指数的に増加する。突き出しを本 \(3\) 冊分にするには \(227\) 冊の本が必要であり、\(100\) 冊分にするには途方もない冊数の本が必要になる。

さらに突っ込んだ話

ここまでの議論では、一番上の本が机からどれだけ突き出すかを考えてきた。そのため、最も右端にある本が一番上にない安定スタックがより大きな突き出しを持つ可能性は排除されていない。例えば図 \(\text{14.8}\) \(\text{(a)}\) では上の本より下の本の方が右にある。これは今までに考えてこなかった安定スタックであり、その突き出しは本の長さの \(3/4\) である。この値はこれまで考えてきた下の本より上の本の方が右にある安定スタックにおける最大の突き出しに等しい。

下の本が右端にある \text{(a)} の突き出しは、上の本が右端にある \text{(b)} の突き出しと等しい — 図 14.8下の本が右端にある \(\text{(a)}\) の突き出しは、上の本が右端にある \(\text{(b)}\) の突き出しと等しい

図 \(\text{14.8}\) の \(\text{(a)}\) と \(\text{(b)}\) が同じ突き出しを持つ事実から、次のことが分かる: これまで考えてきた、一番上の本が最も右にある突き出しが最大の(一意な) \(n\) 冊の安定スタックの上部 \(2\) 冊を図 \(\text{14.8}\) \(\text{(a)}\) のように置き換えると、同じ突き出しを持つ上から二番目の本が右端にある安定スタックが得られる。つまり \(n > 1\) なら、最大の突き出しを実現する \(n\) 冊のスタックは少なくとも二つ存在する ── 片方では一番上の本が右端にあり、もう一方では上から二番目の本が右端にある。

一冊の本の上に置ける本が一冊だけのとき、この二つのスタック以外に突き出しが最大となるスタックが存在しないことの証明はそれほど難しくない。しかし、本積み上げ問題はこれで終わりではない。一冊の本の上に複数冊の本を (ひっくり返ったピラミッドのように) 置くことを許すなら、\(n\) 冊の本で達成できる突き出しは \(\sqrt[3]{n}\) に比例し、\(\ln n\) より圧倒的に長くなる。詳しくは [16] を参照してほしい。

14.4.3 漸近等価性

等式 \(\text{(14.22)}\) のように、何らかの関数の振る舞いを (無視できる程度に小さい) 誤差項を無視して表現するときに利用できる特別な記法が存在する。\(\sim\) は最も大きな部分が一致することを表す。例えば \(H_{n} \sim \ln n\) は \(H_{n}\) の最も大きな部分が \(\ln n\) であることを意味する。正確には:

定義 14.4.2

関数 \(f \colon \mathbb{R} \to \mathbb{R}\) が関数 \(g \colon \mathbb{R} \to \mathbb{R}\) と漸近等価 (asymptotically equal) とは、次の条件が成り立つことを言う:

\[ \lim_{x \to \infty} \frac{f(x)}{g(x)} = 1 \]

このとき次のように書く:

\[ f(x) \sim g(x) \]

等式 \(\text{(14.22)}\) の右辺の項を大きい順に二つ取って \(H_{n} \sim \ln n + \gamma\) と書きたくなるかもしれないが、これは意図した事実を表現しない。定義 14.4.2 によれば、任意の定数 \(c\) に対して \(H_{n} \sim \ln n + c\) が成り立つ。二番目に大きな項が \(\gamma\) である事実を表現したいなら \(H_{n} - \ln n \sim \gamma\) と書く必要がある。

\(\sim\) の記法が便利なのは、値が小さい部分を無視しても構わない状況があるためである。例えば、\(n = 100\) のとき \(H(n)\) の値は最初の二つの項だけでかなり正確に計算できる:

\[ | H_{n} - \ln n - \gamma | \leq \left| \frac{1}{200} - \frac{1}{120000} + \frac{1}{120 \cdot 100^{4}} \right| < \frac{1}{200} \]

漸近記法については第 14.7 節でさらに詳しく議論する。ここでは、総和に関するテクニックの紹介を続けよう。