Question

给定整数n（n≥3），记f（x）为集合{1，2，…2ⁿ-1}的满足如下两个条件的子集A的元素个数的最小值：
a）1∈A，2ⁿ-1∈A；
b）A中的元素（除1外）均为A中的另两个（可以相同）元素的和．
（1）求f（3）的值；
（2）求证：f（100）≤108．

Answer 1

考点：集合中元素个数的最值

专题：集合

分析：根据定义，分别进行验证即可求出f（3）的值，然后根据条件进行递推，即可得到不等式的结论．

解答： 解：（1）设集合A⊆{1，2，…2³-1}，且A满足（a），（b）．
则1∈A，7∈A．
由于{1，m，7}，（m=2，3，4，5，6）不满足（b），故A集合的元素个数大于3．
又 {1，2，3，7}，{1，2，4，7}，{1，2，5，7}，{1，2，6，7}，{1，3，4，7}，{1，3，5，7}，{1，3，6，7}，{1，4，5，7}，{1，4，6，7}，{1，5，6，7}都不满足 （b），
故A集合的元素个数大于4．
而集合{1，2，4，6，7}满足（a），（b），
∴f（3）=5．
（2）首先证明f（n+1）≤f（n）+2，n≥3                     ①
事实上，若A⊆{1，2，…2ⁿ-1}，满足（a），（b），且A的元素个数为f（n）．
令B=A∪{2ⁿ⁺¹-2，2ⁿ⁺¹-1}，由于{2ⁿ⁺¹-2＞2ⁿ-1，
故|B|=f（n）+2．
又2ⁿ⁺¹-2=2（2ⁿ-1），2ⁿ⁺¹-1=1+（2ⁿ⁺¹-2），
所以，集合B⊆{1，2，…，2ⁿ⁺¹-1}，且B满足（a），（b）．从而
f（n+1）≤|B|=f（n）+2，
其次证明：f（2n）≤f（n）+n+1，n≥3                    ②
事实上，设A⊆{1，2，…2ⁿ-1}，满足（a），（b），且A的元素个数为f（n）．令
B=A∪{2ⁿ⁺¹-2，2ⁿ⁺¹-1…2²ⁿ-1}，
由于  2（2ⁿ-1）＜2²（2ⁿ-1）＜???＜2²ⁿ-1，
所以B⊆{1，2，…2²ⁿ-1}，且|B|=f（n）+n+1．
而2^k+1（2ⁿ-1）=2^k（2ⁿ-1）+2^k（2ⁿ-1），k=0，1，2???n-1，
从而B满足（a），（b），于是
f（2n）≤|B|=f（n）+n+1． …（14分）
由①，②得 f（2n+1）≤f（n）+n+1．                       ③
反复利用②，③可得
f（100）≤f（50）+50+1≤f（25）+25+1+51≤f（12）+12+3+77≤f（6）+6+1+92≤f（3）+3+1+99=108．

点评：本题主要考查与集合有关的试题的证明，难度较大，综合性较强．