練習問題

二つのコップがある。一つ目のコップには \(1\) ピントの水が、二つ目のコップには \(1\) ピントにはワインが入っている。一つ目のコップから \(1/3\) ピントを二つ目のコップに移し、それから二つ目のコップから \(1/3\) ピントを一つ目のコップに移す操作を \(n\) 回繰り返す操作を考える。ただし、液体を移した後はコップを十分かき混ぜるとする。

1. \(n\) 回の操作の後にそれぞれのコップに含まれるワインの量を表す閉形式の式を示せ。

2. \(n\) を無限に大きくするとき、それぞれのコップに含まれるワインの量はどのような値に近づくか？

第 14.1.2 項で見たように、摂動法を使うと幾何級数の公式を導出できる:

同様のアプローチを使って、次の和を閉形式に変形せよ:

Sammyサミー theザ Sharkシャーク は次の条件で融資を行う金融機関である:

1. 融資開始日の朝、Sammy は顧客に \(m\) ドルを渡す。この瞬間、顧客は Sammy に対する \(m\) ドルの負債を負う。

2. 毎晩、Sammy はサービス使用料として顧客の負債を \(f\) ドルだけ増やし、それから金利として顧客の負債を \(p\) 倍にする。例えば、Sammy が「控えめ」なら \(10\) セントのサービス使用料と \(1\%\) の金利を課すかもしれない。このとき \(f = 0.1\) および \(p = 1.01\) である。

次の設問に答えよ:

1. 融資開始日の終了時点における顧客の負債を求めよ。

2. 融資開始日の次の日の終了時点における顧客の負債を求めよ。

3. 融資開始日から \(d\) 日目が終了した時点における負債を表す閉形式の式を求めよ。

4. Sammy から \(10\) ドルを \(1\) 年間借りると、負債はいくらになるか？

Harvardハーバード の学位は MIT の学位より高い価値を持つだろうか？ Harvard の新卒は月給 \(\$10{,}000\) からスタートし、毎月 \(\$1{,}000\) だけ昇給するとしよう。つまり Harvard の新卒は就職して \(1\) か月後に \(\$10{,}000\) を受け取り、\(2\) か月後に \(\$11{,}000\) を受け取り、\(3\) か月後に \(\$12{,}000\) を受け取り、以下同様となる。

一方、MIT の新卒は月給 \(\$6{,}000\) からスタートし、毎月 \(2\%\) だけ昇給するとしよう。つまり MIT の新卒は就職してから \(1\) か月後に \(\$6{,}000\) を受け取り、\(2\) か月後に \(1.02 \cdot \$6{,}000 = \$6,120\) を受け取り、\(3\) か月後に \(1.02 \cdot \$6,120 = \$6240.4\) を受け取り、以下同様となる。

また、インフレ率は毎月 \(0.3\%\) で固定だと仮定する。つまり現在の \(\$1\) は \(1\) か月後の \(\$1.003\) と等しい価値を持つ。

1. Harvard の新卒が就職後 \(n\) 年で受け取る金額を表す閉形式の式を求めよ。\(n = 25\) とした値を計算せよ。

2. Harvard の新卒が就職後に \(n\) 年間だけ働くと仮定したとき、現在のドルに換算した Harvard の学位の価値を表す閉形式の式を求めよ。\(n = 25\) とした値を計算せよ。

3. MIT の学位に対する同様の設問に答えよ。

MIT 信用組合の口座に今日 \(\$100\) を振り込み、\(1\) か月後に \(\$99\) を振り込み、\(2\) か月後に \(\$98\) を振り込み、以下同様とする。利息が毎月 \(0.3\%\) で固定のとき、預金が \(\$5{,}000\) 以上となるのは何か月後か？

次の総和を閉形式に変換せよ:

1. \(\ \ \displaystyle \sum_{i=1}^{n} \left( \frac{1}{i + 2012} - \frac{1}{i + 2013} \right)\)
2. \(\ \ \displaystyle \sum_{i=1}^{n} i^{3}\)

   この総和が \(n\) の多項式に等しいと仮定し、その多項式を見つけ、その正しさを数学的帰納法で検証する方法を用いよ。

\(S\) を次のように定める:

第 14.3 節で解説した積分を用いる近似法を使って、次の不等式を満たす整数 \(a\), \(b\), \(c\), \(d\) および実数 \(e\) を求めよ:

\(f \colon \mathbb{R} \to \mathbb{R}\) を広義増加な連続関数とする。\(f\) が次の条件を満たすとき、\(f\) は低速増加 (grows slowly) と言うことにする:

1. 任意の \(a > 0\) に対する関数 \(f_{a}(n) ::= n^{a}\) が低速増加だと示せ。

2. 関数 \(f(n) ::= e^{n}\) が低速増加でないと示せ。

3. \(f\) が低速増加なら次の関係が成り立つと示せ:

   \[ \int_{1}^{n} f(x) \, dx \sim \sum_{i=1}^{n} f(i) \]

\(n\) を \(2\) 以上の整数とする。次に示す不等式の中で正しいものを全て選べ。

1. \(\displaystyle \sum_{i=1}^{n} \ln (i + 1) \leq \ln 2 + \int_{1}^{n} \ln (x + 1) \, dx\)
2. \(\displaystyle \sum_{i=1}^{n} \ln (i + 1) \leq \int_{0}^{n} \ln (x + 2) \, dx\)
3. \(\displaystyle \sum_{i=1}^{n} \frac{1}{i} \geq \int_{0}^{n} \frac{1}{x+1} \, dx \)

ヒント: 図 \(\text{14.9}\) が利用できるだろう。

\(f \colon \mathbb{R}^{+} \to \mathbb{R}^{+}\) を広義減少関数とする。\(S\), \(I\) を次のように定める:

次の不等式を示せ:

非常に分かりやすい図であれば証明で使っても構わない。

積分を使って、次の総和の上界と下界を求めよ。ただし、両者の差は \(0.1\) 以下である必要がある。

ヒント:最初の数項を明示的に計算し、残りの項に対する上界と下界を求める。

探検家が砂漠に眠る聖杯を目指している。彼女の考えでは、その聖杯が置かれた神殿は最も近いオアシスから徒歩で \(d\) 日の場所にある。砂漠は灼熱なので、定期的な水分補給が欠かせない。彼女が持ち運べる水は最大で \(1\) ガロンであり、\(1\) ガロンの水は \(1\) 日で消費される。ただし、彼女は自分の持っている水の一部を途中に置いてオアシスに引き返し、後でその水を利用できる。

例えば、オアシスから徒歩で \(2/3\) 日の場所に神殿があるなら、彼女は次の戦略で \(2\) 日かけて聖杯を持ち帰ることができる。まず、彼女は \(1\) ガロンの水を持ってオアシスを出発し、神殿に向かって \(1/3\) 日だけ進み、その場に \(1/3\) ガロンの水を置いてオアシスに引き返す ── オアシスに到着する瞬間に水の残量は \(0\) になる。それから彼女は \(1\) ガロンの水を補給し、\(1/3\) 日だけ神殿に向かって歩き、そこで \(1/3\) ガロンの水を拾い、さらに \(1/3\) 日だけ歩いて神殿に到着する。そこで聖杯を手にしたら、\(2/3\) 日をかけてオアシスに帰還する ── ここでもオアシスに到着する瞬間に水の残量が \(0\) になる。

では、神殿がもっと遠くにある場合はどうだろうか？

1. 砂漠に水が置かれていないと仮定する。オアシスから補給できる水が \(1\) ガロンだけのとき、オアシスから往復できる最も遠い地点はどこか？

2. 砂漠に水が置かれていないと仮定する。オアシスから補給できる水が \(2\) ガロンだけのとき、オアシスから往復できる最も遠い地点はどこか？ 証明は必要ない。見つけられた最良の値を答えよ。

3. 探検家は次の再帰的な戦略を使うことにした。この戦略は水を \(n\) ガロンを使用し、現在位置から一定の距離だけ前進した地点に \(n - 1\) ガロンの水と現在地点に帰るのに必要な分の水を配置する。それだけの水を配置した後、彼女は以前にいた地点に戻る代わりに、\(n - 1\) ガロンを使用する同じ戦略を実行してさらに前進する。このように砂漠を進んでいくと、砂漠にはオアシスに戻るだけの水が常に配置される。

   \(n\) ガロンの水が使用可能なとき、この戦略を使うとオアシスから徒歩 \(H_{n}/2\) 日分の地点まで往復できると示せ。ここで \(H_{n}\) は \(n\) 次の調和数を表す:

   \[ H_{n} ::= \frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n} \]

   探検家は神殿がオアシスからどれだけ離れていようと到達できると結論付けよ。

4. 神殿がオアシスから徒歩 \(d = 10\) 日分だけ離れているとする。漸近近似 \(H_{n} \sim \ln n\) を利用して、彼女が聖杯を手にするには \(100\) 万年以上がかかることを示せ。

次の条件を満たす実数 \(a\) を答え、それが条件を満たすことを証明せよ:

ヒント: 正しいと思われる \(a\) を見つけ、積分で評価する。

非負項の無限和は、項の順序に関係なく同じ値に収束 (または常に発散) する。これは正の項と負の項が両方とも無限に存在するとき一般に正しくない。非常に分かりやすい例を示す:

この無限和では、括弧の付け方を変えると異なる「和」が得られる:

ここでの問題は、先頭から第 \(n\) 項までの和が \(0\) と \(1\) を交互に取るので、\(n\) が無限に大きくなるときの極限が存在しないことである。

しかし無限級数が収束するとしても、正の項と負の項が両方とも無限に出現する場合は項の並び替えによって和が変化する可能性がある。この事実が確認できる例として、次の交代調和級数 (alternating harmonic series) がある:

この無限級数が \(\ln 2\) に収束することは初等的な微積分で示せる ([2], p. 403)。しかし、項を並び替えると状況が変化する。

交代調和級数の項を並び変えると和が \(7\) になる無限級数を作れると示せ。さらに、発散する無限級数も作れると示せ。

長さ \(1~\text{m}\) の魔法の絨毯の端に虫がいて、もう一方の端を目指して移動している。虫の移動速度は秒速 \(1~\text{cm}\) である。しかし、いたずら好きの \(1\) 年生 Mildredミルドレッド Andersonアンダーソン は \(1\) 秒ごとに魔法で絨毯を \(1~\text{m}\) だけ長くしてしまう。絨毯が長くする魔法は一瞬で完了し、絨毯を一様に引き延ばすとする。つまり、最初の数秒では次のことが起きる:

• 最初の \(1\) 秒で虫が \(1~\text{cm}\) だけ移動する。目的地までの距離は \(99~\text{cm}\) となる。

• Mildred が絨毯を \(1~\text{m}\) だけ引き延ばす。絨毯の長さが \(2\) 倍になるので、虫の位置は出発地点から \(2\text{cm}\) に変化し、目的地までの距離は \(198~\text{cm}\) となる。

• 次の \(1\) 秒で虫が \(1~\text{cm}\) だけ移動する。出発地点から \(3~\text{cm}\) の位置に到達し、目的地までの距離は \(197~\text{cm}\) となる。

• またしても Mildred が絨毯を \(1~\text{m}\) だけ引き延ばす。今回は絨毯の長さが \(2~\text{m}\) から \(3~\text{m}\) へと \(1.5\) 倍になるので、虫の位置は出発地点から \(3 \cdot 1.5 = 4.5~\text{cm}\) に変化し、目的地までの距離は \(197 \cdot 1.5 = 295.5~\text{cm}\) となる。

• 次の \(1\) 秒で虫が \(1~\text{cm}\) だけ移動し、以下同様となる。

この憐れな虫の運命を考えよう。

1. \(i\) 秒目に虫が距離する距離を絨毯全体に対する割合として表せ。

2. 移動を始めてから \(n\) 秒後までの虫の移動距離を絨毯全体に対する割合として表せ。解答は調和数 \(H_{n}\) を使って表現せよ。

3. 宇宙の直径は約 \(3 \cdot 10^{10}\) 光年だと考えられている。虫が絨毯の端に到達するまでに自分の足で移動する距離は宇宙の直径の何倍か？ \(1\) 光年を \(10^{15}~\text{m}\) として計算せよ。

次の交代調和級数 (alternating harmonic series) が収束すると示せ:

次の関係を示せ:

次の関数を \(f\) とするとき、\(f(x) = O(x^{n})\) となる最小の非負整数 \(n\) をそれぞれ求めよ。

1. \(2x^{3} + (\log x) x^{2}\)
2. \(2x^{2} + (\log x) x^{3}\)
3. \((1.1)^{x}\)
4. \((0.1)^{x}\)
5. \(\dfrac{x^{4} + x^{2} + 1}{x^{3} + 1}\)
6. \(\dfrac{x^{4} + 5 \log x}{x^{4} + 1}\)
7. \(2^{3\log_{2} x^{2}}\)

\(f(n) = n^{3}\) とする。\(g(n)\) が次の表に示す関数のとき、表の右側に示された漸近関係が成り立つかどうかそれぞれ答えよ。

次に示す命題から正しいものを全て選べ。

1. \(n^{2} \sim n^{2} + n\)
2. \(3^{n} = O(2^{n})\)
3. \(n^{\sin(n \pi / 2) + 1} = o(n^{2})\)
4. \(n = \Theta \left( \dfrac{3n^{3}}{(n + 1)(n - 1)} \right)\)

次の関係を示せ:

ヒント: \(n^{2}!\) に Stirling の公式 (定理 14.5.1) を適用する。

次の値は本書で後に利用される:

この値は公平なコインを \(2^{2n}\) 回投げたときに表がちょうど \(n\) 回になる確率に等しい。この値が漸近的に \(\dfrac{1}{\sqrt{n \pi}}\) に等しいと示せ。

\(f\), \(g\) を実数値関数とする。

1. 次の二つの条件を満たす \(f\), \(g\) の例を示せ:

   • \(\limsup fg < \limsup f \cdot \limsup g\)

   • \(\limsup fg\), \(\ \limsup f\), \(\ \limsup g\) が有限

2. 次の二つの条件を満たす \(f\), \(g\) の例を示せ:

   • \(\limsup fg > \limsup f \cdot \limsup g\)

   • \(\limsup fg\), \(\ \limsup f\), \(\ \limsup g\) が有限

1. 正実関数上の二項関係 \(R\) を次の規則で定義する:

   \[ f \mathrel{R} g \ \ \overset{\text{def}}{\longleftrightarrow}\ \ g = o(f) \]

   \(R\) が狭義半順序だと示せ。

2. \(g\) を正実関数とする。次の関係を示せ:

   \[ f \sim g \ \ \longleftrightarrow \ \ f = g + h \text{ と } h = o(g) \text{ を満たす関数 } h \text{ が存在する} \]

次に示す関数の組 \(f(n)\), \(g(n)\) について、表の右側に示された漸近関係が成り立つかどうかを答えよ。\(k \leq 1\), \(\varepsilon > 0\), \(c > 1\) は定数とする。最も難しいまたは興味深いと思うマスを取り出し、そのマスの解答が正しいことを示せ。

次に示す関数を \(f_{1}\), \(f_{2}\), \(\ldots\), \(f_{24}\) に並び変え、任意の \(i\) で \(f_{i} = O(f_{i+1})\) が成り立つようにせよ。\(f_{i} = \Theta(f_{i+1})\) が成り立つ \(i\) を答えよ。

1. \(n \log n\)
2. \(2^{100} n\)
3. \(n^{-1}\)
4. \(n^{-1/2}\)
5. \((\log n) / n\)
6. \(\binom{n}{64}\)
7. \(n!\)
8. \(2^{2^{100}}\)
9. \(2^{2^{n}}\)
10. \(2^{n}\)
11. \(3^{n}\)
12. \(n2^{n}\)
13. \(2^{n+1}\)
14. \(2n\)
15. \(3n\)
16. \(\log n!\)
17. \(\log n\)
18. \(\log_{10} n\)
19. \(2.1^{\sqrt{n}}\)
20. \(2^{2n}\)
21. \(4^{n}\)
22. \(n^{64}\)
23. \(n^{65}\)
24. \(n^{n}\)

非負実数値関数 \(f\), \(g\) が \(\displaystyle\lim_{x \to \infty} f(x) = \infty\) と \(f \sim g\) を満たすという。

1. \(2^{f} \not\sim 2^{g}\) を満たす \(f\), \(g\) の例を示せ。

2. \(\log f \sim \log g\) を示せ。

3. Stirling の公式 (定理 14.5.1) を使って次の関係を示せ:

   \[ \log n! \sim n \log n \]

次に示す関数 \(\text{(a)}\)-\(\text{(e)}\) の漸近的な振る舞いを表現する漸近記法を次の中から選べ:

完全な証明は必要ないものの、解答を簡単に説明せよ。

1. \(\ n + \ln n + (\ln n)^{2}\)
2. \(\ \dfrac{n^{2} + 2n - 3}{n^{2} - 7}\)
3. \(\ \displaystyle \sum_{i=0}^{n} 2^{2i+1}\)
4. \(\ \ln (n^{2}!)\)
5. \(\ \displaystyle \sum_{k=1}^{n} k \left( 1 - \dfrac{1}{2^{k}} \right)\)

1. 次の命題を証明または反証せよ:

   1. \(n! = O((n + 1)!)\)
   2. \((n + 1)! = O(n!)\)
   3. \(n! = \Theta((n + 1)!)\)
   4. \(n! = o((n + 1)!)\)
   5. \((n + 1)! = o(n!)\)

2. 次の関係を示せ:

   \[ \left( \frac{n}{3} \right)^{\! n+e} = o(n!) \]

次の関係を示せ:

\(\log n! = \Theta (n \log n)\) の初等的な証明 (Stirling の公式を使わない証明) を示せ。

関数 \(f, g \colon \mathbb{N}^{+} \to \mathbb{N}^{+}\) が \(f \sim g\) を満たすという。

1. \(2f \sim 2g\) だと示せ。

2. \(f^{2} \sim g^{2}\) だと示せ。

3. \(2^{f} \not\sim 2^{g}\) を満たす \(f\), \(g\) の例を示せ。解答を簡単に説明せよ。

\(\mathbb{N}\) 上の二関数 \(f, g\) が \(f = O(g)\) とは、次の命題の成立を意味する:

次に \(f\), \(g\) の組をいくつか示す。それぞれについて、\(f = O(g)\) および \(g = O(f)\) が成り立つかどうかを答えよ。成り立つ場合は、命題 \(\text{(14.34)}\) の成立が示せる最小の非負整数 \(c\) と、その \(c\) に対応する最小の非負整数 \(n_{0}\) を答えよ。

1. \(f(n) = n^{2}\), \(\,g(n) = 3n\)

2. \(f(n) = (2n - 7)/(n + 4)\), \(\,g(n) = 4\)

3. \(f(n) = 1 + (n \sin (n\pi/2))^{2}\), \(\,g(n) = 3n\)

この主張が誤っている理由を説明せよ。さらに、次の誤った証明に含まれる間違いを特定・説明せよ。

誤った証明 \(n\) に関する数学的帰納法で示す。「関係 \(\text{(14.34)}\) が成り立つ」を帰納法の仮定 \(P(n)\) とする。

ベースケース: \(P(0)\) は明らかに成り立つ。

帰納ステップ: ある \(n > 0\) で \(P(n)\) が成り立つと仮定する。このとき、ある定数 \(c > 0\) で \(2^{n} \leq c \cdot 1\) が成り立つ。よって次を得る:

これは \(2^{n+1} = O(1)\) を意味するので、\(P(n+1)\) は成り立つ。これで帰納ステップが完了した。

数学的帰納法の原理より、全ての \(n\) で \(2^{n} = O(1)\) だと結論できる。つまり、指数関数は定数で抑えられる。 ■

1. 関数上の二項関係 \(R\) を次の規則で定義する:

   \[ f \mathrel{R} g \ \ \overset{\text{def}}{\longleftrightarrow}\ \ f = o(g) \]

   \(R\) が狭義半順序だと示せ。

2. ビッグオーの下で比較不能な二つの関数の例を示せ。つまり、次の条件を満たす \(f\), \(g\) を見つけよ:

   \[ f \neq O(g) \ \operatorname{\text{\footnotesize AND}} \ g \neq O(f) \]

   \(R\) が線形順序でないと結論付けよ。比較可能でない三つの関数を見つけられるか？

次の条件を満たす狭義増加な全域関数 \(f \colon \mathbb{N}^{+} \to \mathbb{N}^{+}\) と \(g \colon \mathbb{N}^{+} \to \mathbb{N}^{+}\) の例を示せ:

• \(f \sim g\)
• \(3^{f} \neq O(3^{g})\)

実数値関数 \(f\), \(g\) が \(f = \Theta(g)\) と \(\displaystyle \lim_{x \to \infty} f(x) = \infty\) を満たすとき、次の関係が成り立つと示せ:

1. \(f(n) = \Theta (n^{2})\) と \(f(n) \not\sim n^{2}\) を満たす関数 \(f \colon \mathbb{N} \to \mathbb{R}\) の例を示せ。解答が条件を満たす理由を説明せよ。

2. \(g(n) = O (n^{2})\) と \(g(n) \neq \Theta (n^{2})\) と \(g(n) \neq o(n^{2})\) を満たす関数 \(f \colon \mathbb{N} \to \mathbb{R}\) の例を示せ。解答が条件を満たす理由を説明せよ。

1. \(a\), \(b\) を正定数とする。次の関係が成り立つと示せ:

   \[ (an)^{b/n} \sim 1 \]

   ヒント: 等式 \(an = a2^{\log_{2} n}\) を利用する。

2. 次の関係が成り立つと示せ:

   \[ \sqrt[n]{n!} = \Theta(n) \]

1. 非負実数値関数上の漸近関係を次にいくつか示す。それぞれについて、「同値関係である」「狭義半順序である」「弱半順序である」「どれでもない」のどれが正しいか答えよ。

   1. [リトルオー] \(f = o(g)\)

   2. [ビッグオー] \(f = O(g)\)

   3. [漸近等価性] \(f \sim g\)

   4. [シータ] \(f = \Theta(g)\)

   5. \(f = O(g) \ \operatorname{\text{\footnotesize AND}} \ g \neq O(f)\)

2. \(\text{(a)}\) の \(\text{(i)}\)-\(\text{(v)}\) の間に成り立つ含意関係を全て示せ。例えば \(\text{(i)} \longrightarrow \text{(ii)}\) は成り立つ。解答を簡単に説明せよ。

\(\mathbb{Z}^{+}\) 上の非負実数値関数 \(f\) と \(g\) に対する \(f = O(g)\) は、次の条件を満たす \(c, n_{0} \in Z^{+}\) の存在を意味する:

次に \(f\) と \(g\) の組をいくつか示す。それぞれについて、上記の条件の成立が示せる最小の \(c \in \mathbb{Z}^{+}\) と、その \(c\) に対応する最小の \(n_{0} \in \mathbb{Z}^{+}\) を答えよ。\(f = O(g)\) が成立しないときは両方に \(\infty\) を答えよ。

1. \(\displaystyle f(n) = \frac{1}{2}\ln n^{2}\), \(\, g(n) = n\)

2. \(f(n) = n\), \(\, g(n) = n \ln n\)

3. \(f(n) = 2^{n}\), \(\, g(n) = n^{4} \ln n\)

4. \(\displaystyle f(n) = 3 \sin \left( \frac{\pi(n-1)}{100} \right) + 2\), \(\, g(n) = 0.2\)