この問題は、利用者からの報告を受けて確認中です。答えや解説に誤りがあるかもしれません。

計算理論・ラムダ計算の問題

難易度 4大学院入試の難問レベル大学院数学計算理論・ラムダ計算

$N = {0, 1, 2, \dots}$ （ $0$ を含む）とし、関数 $A : N \times N \to N$ をすべての $m, n \in N$ について
$A (0, n) = n + 1, A (m + 1, 0) = A (m, 1), A (m + 1, n + 1) = A (m, A (m + 1, n))$
で定める。

この定義をそのまま再帰手続きとして実行して $A (m, n)$ を計算する。すなわち、手続き $A (m, n)$ が呼ばれると、 $m = 0$ なら再帰呼び出しをせずに $n + 1$ を返し、 $m \geq 1, n = 0$ なら $A (m - 1, 1)$ を $1$ 回呼んでその値を返し、 $m \geq 1, n \geq 1$ ならまず $A (m, n - 1)$ を呼んでその値 $r$ を得たのち $A (m - 1, r)$ を呼んでその値を返す。最初の呼び出しも含めて、 $A (m, n)$ の計算で手続き $A$ が呼ばれる回数の合計を $C (m, n)$ とする（たとえば $C (0, n) = 1$ 、 $C (1, 0) = 2$ ）。

$n \in N$ に対し、 $C (3, n)$ を $n$ の式で表せ。

この問題で使うもの

アッカーマン関数の値（説明と入口の問題）
等差・等比数列の和と Σ（説明と入口の問題）
等差数列・等比数列の一般項（説明と入口の問題）
数学的帰納法と一般項の推定（説明と入口の問題）

この問題を解けるようになるまで（18 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの問題で使う技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

ヒント

行き詰まったら、上から順に 1 つずつ開いてください。

ヒント 1

手続きの定義から $C (m, n)$ の漸化式を立てる。 $C (m + 1, n + 1)$ には $C (m, A (m + 1, n))$ が現れるので、 $A (1, n), A (2, n), A (3, n)$ の閉じた形も必要になる。

ヒント 2

$A (1, n) = n + 2$ , $A (2, n) = 2 n + 3$ , $A (3, n) = 2^{n + 3} - 3$ である。これを使って $C (1, n)$ , $C (2, n)$ を順に求めよう。

ヒント 3

$C (1, n) = 2 n + 2$ , $C (2, n) = (2 n + 5) (n + 1)$ , $C (3, 0) = 15$ となる。 $C (3, n + 1) - C (3, n) = 1 + C (2, 2^{n + 3} - 3)$ を展開して和をとろう。

答えと解説

答えを見る

\frac{2 ^{2 n + 7} + 37}{3} - 5 \cdot 2^{n + 3} + 3 n

結果を記録する（このブラウザにだけ保存されます）:

解説を読む

手続きの定義から、呼び出し回数は次の漸化式をみたす。
$C (0, n) = 1, C (m + 1, 0) = 1 + C (m, 1), C (m + 1, n + 1) = 1 + C (m + 1, n) + C (m, A (m + 1, n)) .$
（最後の式の $1$ は $A (m + 1, n + 1)$ 自身の呼び出し、残りは内側の $A (m + 1, n)$ の計算と外側の $A (m, r)$ の計算の分である。）

$A$ の値. 帰納法で次がわかる。
- $A (1, n) = n + 2$ : $A (1, 0) = A (0, 1) = 2$ 、 $A (1, n + 1) = A (0, A (1, n)) = A (1, n) + 1$ 。
- $A (2, n) = 2 n + 3$ : $A (2, 0) = A (1, 1) = 3$ 、 $A (2, n + 1) = A (1, A (2, n)) = A (2, n) + 2$ 。
- $A (3, n) = 2^{n + 3} - 3$ : $A (3, 0) = A (2, 1) = 5$ 、 $A (3, n + 1) = A (2, A (3, n)) = 2 A (3, n) + 3$ より $A (3, n) + 3$ は公比 $2$ の等比数列で $A (3, n) + 3 = 8 \cdot 2^{n}$ 。

$C (1, n)$ . $C (1, 0) = 1 + C (0, 1) = 2$ 、 $C (1, n + 1) = 1 + C (1, n) + C (0, \cdot) = C (1, n) + 2$ 。よって $C (1, n) = 2 n + 2$ 。

$C (2, n)$ . $C (2, 0) = 1 + C (1, 1) = 1 + 4 = 5$ 。
$C (2, n + 1) = 1 + C (2, n) + C (1, 2 n + 3) = 1 + C (2, n) + (4 n + 8) = C (2, n) + 4 n + 9.$
よって
$C (2, n) = 5 + k = 0 \sum n - 1 (4 k + 9) = 5 + 2 n (n - 1) + 9 n = 2 n^{2} + 7 n + 5 = (2 n + 5) (n + 1) .$

$C (3, n)$ . $C (3, 0) = 1 + C (2, 1) = 1 + 14 = 15$ 。 $a = A (3, n) = 2^{n + 3} - 3$ とおくと
$C (2, a) = (2 a + 5) (a + 1) = (2^{n + 4} - 1) (2^{n + 3} - 2) = 2^{2 n + 7} - 2^{n + 5} - 2^{n + 3} + 2 = 2^{2 n + 7} - 40 \cdot 2^{n} + 2.$
したがって
$C (3, n + 1) = C (3, n) + 1 + C (2, a) = C (3, n) + 128 \cdot 4^{n} - 40 \cdot 2^{n} + 3.$
和をとると
$C (3, n) = 15 + k = 0 \sum n - 1 (128 \cdot 4^{k} - 40 \cdot 2^{k} + 3) = 15 + \frac{128 ( 4 ^{n} - 1 )}{3} - 40 (2^{n} - 1) + 3 n .$
整理すると
$C (3, n) = \frac{128 \cdot 4 ^{n} + 37}{3} - 40 \cdot 2^{n} + 3 n = \frac{2 ^{2 n + 7} + 37}{3} - 5 \cdot 2^{n + 3} + 3 n .$

検算. $n = 0$ : $\frac{128 + 37}{3} - 40 = 55 - 40 = 15$ で $C (3, 0) = 15$ と一致。 $n = 1$ : 直接 $C (3, 1) = 1 + C (3, 0) + C (2, A (3, 0)) = 1 + 15 + C (2, 5) = 16 + 15 \cdot 6 = 106$ 、式は $\frac{512 + 37}{3} - 80 + 3 = 183 - 77 = 106$ 。 $n = 2$ : 直接 $C (3, 2) = 1 + 106 + C (2, 13) = 107 + 31 \cdot 14 = 541$ 、式は $\frac{2048 + 37}{3} - 160 + 6 = 695 - 154 = 541$ 。

したがって $C (3, n) = \frac{2 ^{2 n + 7} + 37}{3} - 5 \cdot 2^{n + 3} + 3 n$ 。

別解

呼び出し回数の漸化式は、 $C (0, n) = 1$ 、 $C (m + 1, 0) = 1 + C (m, 1)$ 、 $C (m + 1, n + 1) = 1 + C (m + 1, n) + C (m, A (m + 1, n))$ 。

$m = 1$ : $A (1, n) = n + 2$ 。 $C (1, 0) = 1 + C (0, 1) = 2$ 、 $C (1, n + 1) = 1 + C (1, n) + C (0, n + 2) = C (1, n) + 2$ 。よって $C (1, n) = 2 n + 2$ 。

$m = 2$ : $A (2, n) = 2 n + 3$ 。 $C (2, 0) = 1 + C (1, 1) = 5$ 、 $C (2, n + 1) = 1 + C (2, n) + C (1, 2 n + 3) = C (2, n) + 1 + 2 (2 n + 3) + 2 = C (2, n) + 4 n + 9$ 。 $C (2, n) = 5 + \sum_{k = 0}^{n - 1} (4 k + 9) = 5 + 2 n (n - 1) + 9 n = 2 n^{2} + 7 n + 5$ 。

$m = 3$ : $A (3, n) = 2^{n + 3} - 3$ 。 $C (3, 0) = 1 + C (2, 1) = 1 + 14 = 15$ 。 $a = A (3, n) = 2^{n + 3} - 3$ とおくと
$C (3, n + 1) = 1 + C (3, n) + C (2, a)$ 、 $C (2, a) = 2 a^{2} + 7 a + 5 = (2 a + 5) (a + 1) = (2^{n + 4} - 1) (2^{n + 3} - 2) = 2^{2 n + 7} - 5 \cdot 2^{n + 3} + 2$ 。
ゆえに $C (3, n + 1) - C (3, n) = 2^{2 n + 7} - 5 \cdot 2^{n + 3} + 3$ 。

和をとると
$C (3, n) = 15 + \sum_{k = 0}^{n - 1} (2^{2 k + 7} - 5 \cdot 2^{k + 3} + 3) = 15 + \frac{128 ( 4 ^{n} - 1 )}{3} - 40 (2^{n} - 1) + 3 n = \frac{2 ^{2 n + 7} - 120 \cdot 2 ^{n} + 9 n + 37}{3}$ 。

検算: $n = 0$ で $(128 - 120 + 37) /3 = 15$ 。 $n = 1$ で $(512 - 240 + 9 + 37) /3 = 318/3 = 106$ 。直接 $C (3, 1) = 1 + C (3, 0) + C (2, 5) = 1 + 15 + 90 = 106$ で一致する。

計算理論・ラムダ計算の問題

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題