跳到主要内容

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

Author​

zephyr

Description​

For real number and non-negative integer , let denote the function applied times iteratively to ; namely, and if . If for some , define as the minimum such ; namely, . Otherwise, is undefined. Answer each of the following questions and the reasoning behind it.

(1) When , show ( is the minimum integer that is or more).

(2) When , answer the minimum value of that satisfies .

(3) When , which is greater or equal, or ?

对于实数 和非负整数 ，设 表示将函数 迭代地应用于 次；即 并且 当 。如果 对某些 成立，定义 为最小的 ；即 。否则， 未定义。回答以下每个问题并解释其背后的理由。

(1) 当 时，证明 （ 是大于或等于 的最小整数）。

(2) 当 时，回答满足 的 的最小值。

(3) 当 时，比较 和 哪个更大或相等？

Kai​

Written by zephyr

解题思路​

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

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

1. Proving when ​

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

Let . By definition, .

Applying iteratively times:

This shows that iterations are sufficient to reduce to a value .

Now, let's consider iterations:

This shows that iterations are not enough to reduce to a value .

Therefore, is the minimum number of iterations needed, proving that .

2. Finding minimum such that when ​

We need to find the smallest such that it takes exactly 5 iterations of to reduce to a value .

Let's work backwards:

Continuing to apply :

Therefore, the minimum value of that satisfies is .

3. Comparing and when ​

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

  1. : This applies to the number of iterations needed to reduce to .
  2. : This finds the number of iterations needed to reduce to .

Let's consider different cases:

Case 1:

  • In this case, , because one application of is sufficient to reduce to .
  • , because
  • Therefore, when ,

Case 2:

  • In this case, , because two applications of are needed to reduce to .
  • , because
  • Therefore, when ,

Case 3:

  • In this case,

For , we can prove that :

Let .

This inequality holds because for any integer , .

Therefore, we can conclude:

  • When :
  • When :
  • When :

In summary, for all , with strict inequality when .

Knowledge​

难点思路​

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

解题技巧和信息​

  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