每日一题[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.\]