资源描述：
《组合问题的解题方法与策略》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、组合问题的解题方法与策略I:海中学数学组周建新顾滨一.基础知识组合问题可分为三个方面：一是存在性问题；二是计数问题；三是构造问题；而组合最值问题通常需要估计和构造，具有较强的综合性，解答组合最值问题时，我们一般需要按如下步骤來做：(1)探素所要找的最人(小)值；(2)证明已找到的值满足题设：(3)构造实例说明已找到的值是最佳的，是能够达到的因此，解这类问题需要解题者敏锐的洞察力，较强的抽象推理能力和构造能力，也是更需要一定的创新能力•下面我们先通过一些例题，介绍解组合最值问题的基本思路和方法策略.例1{1，2,3,……，2n,2/7+1}的一些非空子集，使得任意两个子集的交或者
2、只有一个数，或者由几个和连的口然数组成.问：这批子集最多可能有几个？解：对每个子集，标出其最大元素b和最小元素由条件易知，所有的子集对应的区间［。力］互不相同(否则，若&与&(心刀对应的［d,b］相同，由于人C舛为连续的自然数，这将导致4=4矛盾)，而所冇的区间［d,b］都有公共元素.设所冇。中授大者为则b2k恒成立，所以至多有k・(2n+2-k)个不同的区间［d,b］(含a=b的情况)，故子集个至多有S(2〃+2-灯W(n+1)2(个).而(/?+1)2是可以取到的.令A(a,b)={a,a+1,……,b-l,b},则当q=1,2..….,n+l;b=n+l,……,2n+1时
3、得到的(〃+1尸个不同的{1,2……,2n+l}的子集A(a,b)便满足题中所有条件，故这样的了集个数的最大值为5+1)2.例2.设M={1,2,3……,2m-n}(m,/ie?V+)是连续2'“/个正整数组成的集合，求最小的正整数k,使得M的任何k元子集中都存在m+1个数如,。2,色”+i满足Q=1,2,……rn).解：所求的k的最小正整数值为“.=2mn-n+l.WA={1,2,3,……n},任何一个以i为首项(lWiWn)2为公比的等比数列与A的交集记为4.一方面，由于M中的2mn-n个元的了集直+1/+2/+3,…2%}中不存在满足要求的加+1个数，故所求的£2mn-n
4、--l.上述断言可用反证法证明.假设直+1/+2,・・・・,2"5}中存在加+1个数〃+1Wa{2J,矛盾•故这样的m+1个数不存在.另一方面,当k=25-/2+1时,可以证明M中的任何R元子集T中必有加+1个数5勺，•…，佥+】满足4庞+1(1W'W加)•依然采用反证法•反设这样的m+1个数不存在，考n—虑以2i+l为首项(/W―)2为公比的等比数例，它与集合M的交的元素个数为2
5、A2/+11+7/7,山反设它至少应有肉諒个元素不在I中，再注意到当&
6、j吋，所以,可知M中至少有个元素不在T中,注意到U
7、A2Z+1=A.MIT1=1A1=n.从而軒WM-n=2mn-n.这与
8、T
9、=2"'H-2+1才盾.故反设不成立.说明：组合极值是组合杂题中最常见、最重要的一种综合题型，即冇组合论证，乂冇组合构造，通过组合论证，说明找到的值符合条件；通过组合构造，说明找到的值是最佳的不容改进的.例3.求最小的自然数心使得在12xn的方格表中，任意给每个方格染上红、黑、白三色之一后，必存在4个方格，其屮心构成一个平行于格线的矩形，且4个方格中颜色相同.如果是llxn的方格表，又怎样呢？解；"最小值为10•首先证明12X10方格表必满足要求，
10、由于12X10方格表共有120格，因此至少有一种颜色出现在至少40格中，不妨设红色.考察所有同行红格对的数目，设各行红格数目分别为Nd…,九，则仏+〃2+••…+%240,所以C；+C：+・・・・C：2的最小值当Nd••…〃吃尽可能平均，也即8个取3,4个取4时达到，即同行红格对的总数为C；+Qi+…•CX»8C^+4C~=48对，而48>C：=45'于是必有2对同行红格时，和应的红格同列，这样的4格便构成了红色矩形，因此在n=10时，12X10方格表总满足要求而可构造，9X12表格中可以三染色后无同色矩形，因此〃的最小值为10.乡■@■3乡多■场乡多■乡・3@乡■乡■@■2%
11、a乡乡・@回乡參・a乡对11X7?方格中，结论仍将是10!11X9方格表的反例可以在图中任意去掉一行得到，下面我们只需证明11X10方格表三染色后必存在同色矩形即可，这个命题不太好证，利用12X10方格表的证明不能奏效，我们必须加以更细致的讨论才行.对11X10方格表，不妨设红格至少有37格，则至少有一行，红格至少有4格，不妨设是第一行，若笫一行恰有4个红格，不妨设是前4格.则后10行中，每行両4格中最多有一个红格，否则便有红色矩形，因此，如果去掉第一行与前4列，那么至多去掉了4+10=14
