趣题: 剩下的数的最大值

趣题: 剩下的数的最大值 #

题目 #

在黑板上写有 $2023$ 个 $1$ , 下面进行 $2022$ 次如下操作: 擦掉黑板上的两个数 $a$ 和 $b$, 并写下 (a + b) 或者 $\min{a^2, b^2}$ , 最后剩下一个数. 设操作得到的这个数的最大值为 $r$ . 求证: $$ 2^{\frac{2023}{3}} < r < 3^{\frac{2023}{3}} $$

Solution 1 #

先证明左半边. 考虑 ${1, 1, 1, 1, 1, 1}\rightarrow{3, 3}-{9}$ , 那么 $2023$ 个 $1$ 可以得到 $337$ 个 $9$ 与 $1$ 个 $1$, 对这 $337$ 个 $9$ 取出 $256$ 个用 $\min{a^2, b^2}$ 可以得到 $9^{2^8}$ , 故 $r > 9^{2^8} > 2^{\frac{2023}{3}}$ .

接下来证右半边. 记黑板上有 $n$ 个 $1$ , 经过 $n - 1$ 次操作后能够得到的最大值为 $f(n)$ . 由于 $a + b$ 和 $\min{a^2, b^2}$ 都是关于 $a, b$ 的不减函数, 故考虑得到 $f(n)$ 的最后一步操作, 必然是由 $f(k)$ 和 $f(n - k)$ 得到的. 故有递推式 $$ f(n) = \max_{1\leq k\leq \lfloor \frac{n}{2}\rfloor} {\max{f(k) + f(n - k), \min{f^2(k), f^2(n-k)}}} $$ 后续归纳法易证, 不做赘述.