给定整数 $n$（$n\geqslant 3$），记 $f(n)$ 为集合 $\left\{1,2,\cdots,2^n-1\right\}$ 的满足如下两个条件的子集 $A$ 的元素个数的最小值：
① $1\in A$，$2^n-1\in A$；
② $A$ 中的元素（除 $1$ 外）均为 $A$ 中另外两个元素（可以相同）的和．
① $1\in A$，$2^n-1\in A$；
② $A$ 中的元素（除 $1$ 外）均为 $A$ 中另外两个元素（可以相同）的和．
【难度】
【出处】
无
【标注】
-
求 $f(3)$ 的值；标注答案$ 5 $解析$f(3)=5$．首先，取集合 $\{1,2,3,5,7\}$ 可以说明 $f(3)\leqslant 5$；接下来说明不存在符合条件的 $4$ 个元素的集合．由于 $7\in A$，根据条件 ②，只需要逐一验证$$\{1,2,5,7\},\{1,3,4,7\},\{1,2,6,7\},\{1,3,6,7\},\{1,4,6,7\},\{1,5,6,7\}$$即可，不难得到以上集合均不符合要求；显然不可能存在符合条件的含 $3$ 个元素或 $2$ 个元素的集合，因此 $f(3)=5$．
-
求证：$f(100)\leqslant 108$．标注答案略解析尝试用递推的方式解决问题．
初步试探 首先考虑如何从 $n\to n+1$．假设现在手头已经有一个满足题意的集合$$A=\left\{1,\cdots,2^n-1\right\}$$它包含 $f(n)$ 个元素，那么是否可以对此集合加以改造（增加若干元素），使得它对 $n+1$ 的情形也符合题意呢？毫无疑问，元素 $2^{n+1}-1$ 应当马上放入集合 $A$．为了使得 $2^{n+1}-1$ 可以表示为集合 $A$ 中的两个元素之和，还应当放入元素$$2^n,2^n+1,\cdots,2^{n+1}-2$$中的至少一个．稍加尝试可知放入元素 $2^n$ 就可以了，此时集合$$A\cup\left\{2^n,2^{n+1}-1\right\}$$在 $n+1$ 的情形时符合题意．回顾反思 这样我们就得到了递推式$$f(n+1)\leqslant f(n)+2.$$但这个递推式的成本很高，每将 $n$ 推进 $1$，需要增加 $2$ 个元素．也就是无法应用该递推式得到 $f(100)\leqslant 108$ 这么好的结果．继续深入 接下来寻找成本更为低廉的递推式，考虑 $n\to 2n$．此时面临的困难在于如何迅速从 $2^n-1$ 到达 $2^{2n}-1$．事实上，每次翻番是非常好的前进方式：$$2^{n+1}-2,2^{n+2}-2^2,\cdots,2^{2n}-2^n,$$此时由于$$\left(2^{2n}-2^n\right)+\left(2^n-1\right)=2^{2n}-1,$$因此$$A\cup\left\{2^{n+1}-2,2^{n+2}-2^2,\cdots,2^{2n}-2^n,2^{2n}-1\right\}$$是在 $2n$ 的情形时符合题意的集合．最终胜利 据此，我们有递推式$$f(2n)\leqslant f(n)+n+1.$$这个递推式的成本基本上和结论要求很相近了，接下来只需要交替使用这两种递推式（优先使用第二个递推式）就可以得到$$\begin{split} f(100)\leqslant &f(50)+51\leqslant f(25)+77 \\\leqslant &f(24)+79\leqslant f(12)+92\\\leqslant &f(6)+99\leqslant f(3)+103=108.\end{split} $$
题目
问题1
答案1
解析1
备注1
问题2
答案2
解析2
备注2
