每日一题[50] 步步为营

给定整数$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）求$f(3)$的值；

（2）求证：$f(100)\leqslant 108$．

 （1）$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\}$即可．不难得到以上集合均不符合要求，因此$f(3)\geqslant 5$．

综上，$f(3)=5$．

（2）尝试用递推的方式解决问题．

首先尝试如何从$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.$$

这个递推式的成本基本上和结论要求很相近了，接下来只需要交替使用这两种递推式（优先使用第二个递推式）就可以得到 $$f(100)\leqslant 108.$$