题目

给定整数n（n≥3），记f（x）为集合{1，2，…2n﹣1}的满足如下两个条件的子集A的元素个数的最小值：a）1∈A，2n﹣1∈A；b）A中的元素（除1外）均为A中的另两个（可以相同）元素的和．（1）求f（3）的值；（2）求证：f（100）≤108． 答案：解：（1）设集合A⊆{1，2，…23﹣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，…2n﹣1}，满足（a），（b），且A的元素个数为f（n）．令B=A∪{2n+1﹣2，2n+1﹣1}，由于{2n+1﹣2＞2n﹣1，故|B|=f（n）+2．又2n+1﹣2=2（2n﹣1），2n+1﹣1=1+（2n+1﹣2），所以，集合B⊆{1，2，…，2n+1﹣1}，且B满足（a），（b）．从而f（n+1）≤|B|=f（n）+2，其次证明：f（2n）≤f（n）+n+1，n≥3 ②事实上，设A⊆{1，2，…2n﹣1}，满足（a），（b），且A的元素个数为f（n）．令B=A∪{2n+1﹣2，2n+1﹣1…22n﹣1}，由于 2（2n﹣1）＜22（2n﹣1）＜⋅⋅⋅＜22n﹣1，所以B⊆{1，2，…22n﹣1}，且|B|=f（n）+n+1．而2k+1（2n﹣1）=2k（2n﹣1）+2k（2n﹣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．

查看本题答案和解析