Skip to content

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

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))\) 哪个更大或相等？

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