東京大学 新領域創成科学研究科 メディカル情報生命専攻 2023年8月実施 問題7

标签：

• Tokyo-University
• Recurrence-Relation

Author

zephyr

Description

For real number $n$ $(> 1)$ and non-negative integer $i$, let $f^{(i)}(n)$ denote the function $f$ applied $i$ times iteratively to $n$; namely, $f^{(0)}(n) = n$ and $f^{(i)}(n) = f(f^{(i-1)}(n))$ if $i > 0$. If $f^{(i)}(n) \leq 1$ for some $i$, define $f^{*}(n)$ as the minimum such $i$; namely, $f^{*}(n) = \min \{ i > 0 \mid f^{(i)}(n) \leq 1 \}$. Otherwise, $f^{*}(n)$ is undefined. Answer each of the following questions and the reasoning behind it.

(1) When $f(n) = \frac{n}{2}$, show $f^{*}(n) = \lceil \log_2 n \rceil$ ($\lceil x \rceil$ is the minimum integer that is $x$ or more).

(2) When $f(n) = \log_2 n$, answer the minimum value of $n$ that satisfies $f^{*}(n) = 5$.

(3) When $f(n) = \log_2 n$, which is greater or equal, $f(f^{*}(n))$ or $f^{*}(f(n))$?

---

对于实数 $n$ $(> 1)$ 和非负整数 $i$，设 $f^{(i)}(n)$ 表示将函数 $f$ 迭代地应用于 $n$ $i$ 次；即 $f^{(0)}(n) = n$ 并且 $f^{(i)}(n) = f(f^{(i-1)}(n))$ 当 $i > 0$。如果 $f^{(i)}(n) \leq 1$ 对某些 $i$ 成立，定义 $f^{*}(n)$ 为最小的 $i$；即 $f^{*}(n) = \min \{ i > 0 \mid f^{(i)}(n) \leq 1 \}$。否则，$f^{*}(n)$ 未定义。回答以下每个问题并解释其背后的理由。

(1) 当 $f(n) = \frac{n}{2}$ 时，证明 $f^{*}(n) = \lceil \log_2 n \rceil$ （$\lceil x \rceil$ 是大于或等于 $x$ 的最小整数）。

(2) 当 $f(n) = \log_2 n$ 时，回答满足 $f^{*}(n) = 5$ 的 $n$ 的最小值。

(3) 当 $f(n) = \log_2 n$ 时，比较 $f(f^{*}(n))$ 和 $f^{*}(f(n))$ 哪个更大或相等？

题目描述

对实数 $n>1$ 和非负整数 $i$，定义函数迭代

$$f^{(0)}(n)=n,\qquad f^{(i)}(n)=f(f^{(i-1)}(n))\quad(i>0).$$

若存在 $i$ 使 $f^{(i)}(n)\le1$，定义

$$f^*(n)=\min\{i>0\mid f^{(i)}(n)\le1\};$$

若不存在则 $f^*(n)$ 未定义。对每问给出答案及理由：

1. 当 $f(n)=n/2$ 时，证明
   $$f^*(n)=\lceil\log_2n\rceil,$$
   其中 $\lceil x\rceil$ 为不小于 $x$ 的最小整数。
2. 当 $f(n)=\log_2n$ 时，求满足 $f^*(n)=5$ 的最小 $n$。
3. 仍取 $f(n)=\log_2n$，比较 $f(f^*(n))$ 与 $f^*(f(n))$ 的大小关系。原定义只显式规定自变量 $n>1$；题面未另行说明当复合表达式的中间自变量不大于 1 时如何扩展 $f^*$ 的定义域。

考点

• 函数迭代与停止次数：把反复减半或取对数写成显式迭代，寻找首次降到 1 以下所需的最小整数步数。
• 迭代对数：通过反向指数塔确定指定停止次数对应的最小初值，并比较先取停止次数与先迭代函数的复合次序。
• 取整与边界：严格处理 $\lceil\log_2n\rceil$、临界等号及 $f^*$ 可能未定义的输入范围。

Kai

Written by zephyr

解题思路

这个问题涉及迭代函数的分析，主要考察了对数函数的性质和迭代过程的理解。我们需要仔细分析每个子问题，利用函数迭代和对数的性质来解决。问题 (1) 和 (2) 为问题 (3) 的解答铺垫，因为它们帮助我们理解 $f^*$ 函数的行为。

对于问题 (3)，我们需要更仔细地分析 $f(f^*(n))$ 和 $f^*(f(n))$ 的关系。这需要我们对不同范围的 n 进行分类讨论，因为 $f(n) = \log_2 n$ 的行为在不同的 n 值范围内会有所不同。

1. Proving $f^*(n) = \lceil \log_2 n \rceil$ when $f(n) = \frac{n}{2}$

To prove this, we need to show that $\lceil \log_2 n \rceil$ is the minimum number of iterations needed to reduce $n$ to a value less than or equal to 1.

Let $k = \lceil \log_2 n \rceil$. By definition, $2^{k-1} < n \leq 2^k$.

Applying $f$ iteratively $k$ times:

$f^{(k)}(n) = \frac{n}{2^k} \leq \frac{2^k}{2^k} = 1$

This shows that $k$ iterations are sufficient to reduce $n$ to a value $\leq 1$.

Now, let's consider $k-1$ iterations:

$f^{(k-1)}(n) = \frac{n}{2^{k-1}} > \frac{2^{k-1}}{2^{k-1}} = 1$

This shows that $k-1$ iterations are not enough to reduce $n$ to a value $\leq 1$.

Therefore, $k = \lceil \log_2 n \rceil$ is the minimum number of iterations needed, proving that $f^*(n) = \lceil \log_2 n \rceil$.

2. Finding minimum $n$ such that $f^*(n) = 5$ when $f(n) = \log_2 n$

We need to find the smallest $n$ such that it takes exactly 5 iterations of $\log_2$ to reduce $n$ to a value $\leq 1$.

Let's work backwards:

$f^{(5)}(n) \leq 1$

$f^{(4)}(n) > 1$

$\log_2(\log_2(\log_2(\log_2(\log_2 n)))) \leq 1$

$2^1 = 2 \leq \log_2(\log_2(\log_2(\log_2 n)))$

Continuing to apply $2^x$:

$2^2 = 4 \leq \log_2(\log_2(\log_2 n))$

$2^4 = 16 \leq \log_2(\log_2 n)$

$2^{16} = 65536 \leq \log_2 n$

$2^{65536} \leq n$

Therefore, the minimum value of $n$ that satisfies $f^*(n) = 5$ is $2^{65536}$.

3. Comparing $f(f^*(n))$ and $f^*(f(n))$ when $f(n) = \log_2 n$

Let's analyze these two expressions by considering different ranges of n:

1. $f(f^*(n))$: This applies $\log_2$ to the number of iterations needed to reduce $n$ to $\leq 1$.
2. $f^*(f(n))$: This finds the number of iterations needed to reduce $\log_2 n$ to $\leq 1$.

Let's consider different cases:

Case 1: $1 < n \leq 2$

• In this case, $f^*(n) = 1$, because one application of $\log_2$ is sufficient to reduce $n$ to $\leq 1$.
• $f(f^*(n)) = f(1) = 0$
• $f^*(f(n)) = f^*(\log_2 n) = 0$, because $0 < \log_2 n \leq 1$
• Therefore, when $1 < n \leq 2$, $f(f^*(n)) = f^*(f(n)) = 0$

Case 2: $2 < n \leq 4$

• In this case, $f^*(n) = 2$, because two applications of $\log_2$ are needed to reduce $n$ to $\leq 1$.
• $f(f^*(n)) = f(2) = 1$
• $f^*(f(n)) = f^*(\log_2 n) = 1$, because $1 < \log_2 n \leq 2$
• Therefore, when $2 < n \leq 4$, $f(f^*(n)) = f^*(f(n)) = 1$

Case 3: $n > 4$

• In this case, $f^*(n) \geq 3$
• $f(f^*(n)) = \log_2(f^*(n))$
• $f^*(f(n)) = f^*(\log_2 n) = f^*(n) - 1$

For $n > 4$, we can prove that $f(f^*(n)) < f^*(f(n))$:

Let $k = f^*(n)$.

$f(f^*(n)) = \log_2 k < k - 1 = f^*(n) - 1 = f^*(f(n))$

This inequality holds because for any integer $k \geq 3$, $\log_2 k < k - 1$.

Therefore, we can conclude:

• When $1 < n \leq 2$: $f(f^*(n)) = f^*(f(n))$
• When $2 < n \leq 4$: $f(f^*(n)) = f^*(f(n))$
• When $n > 4$: $f(f^*(n)) < f^*(f(n))$

In summary, $f(f^*(n)) \leq f^*(f(n))$ for all $n > 1$, with strict inequality when $n > 4$.

Knowledge

难点思路

问题 (2) 中，从 $f^*(n) = 5$ 反推 $n$ 的最小值需要仔细思考迭代过程。我们需要从最后一步开始，逐步应用指数函数来得到最终结果。

解题技巧和信息

1. 在处理迭代函数时，正向和反向思考都很重要。有时从最终状态反推初始值会更容易。
2. 对数函数和指数函数的性质在这类问题中经常用到，熟悉它们的特性和关系很重要。
3. 在比较复杂函数的大小关系时，考虑极限情况和通用情况都很重要。
4. 在分析复杂函数关系时，分类讨论是一个强有力的工具。它可以帮助我们处理不同范围内的特殊情况。
5. 对于涉及对数和整数的问题，特别注意整数边界情况（如 2 的整数次幂）往往很重要。
6. 在证明不等式时，有时需要考虑具体的数值范围，而不仅仅是一般情况。

重点词汇

• iterative function 迭代函数
• ceiling function 天花板函数
• logarithm 对数
• exponentiation 指数运算
• inequality 不等式

参考资料

1. Concrete Mathematics: A Foundation for Computer Science (2nd Edition) by Ronald L. Graham, Donald E. Knuth, and Oren Patashnik, Chapter 3: Integer Functions
2. Introduction to Algorithms (3rd Edition) by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Chapter 3: Growth of Functions