高中数学-- 组合问题选讲 详细解题思路

《高中数学-- 组合问题选讲 详细解题思路》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、清北学堂-高中学业规划专家http://www.qbxt.cn组合问题选讲题1.m个互不相同的正偶数和n个互不相同的正奇数的总和为1987，对于所有这样的m与n，问3m+4n的最大值是多少？请证明你的结论。（1987年第二届全国数学冬令营试题）思路分析：先根据题设条件求得3m+4n的一个上界，然后举例说明此上界可以达到，从而得到3m+4n的最大值。解：设a1,a2,„,am是互不相同的正偶数，b1,b2,„,bn是互不相同的正奇数，使得a1+a2+„+am+b1+b2+„+bn=1987（1）这时

2、分别有：a1+a2+„+am≣2+4+„+2m=m(m+1)（2）2b1+b2+„+bn≣1+3+„+(2n-1)=n(3)2122由①,②,③得m²+m+n≢1987,因而有（m+）+n≢19871④241由④及柯西不等式，得3（m+）+4n≢221221,34.(m)n51987224由于3m+4n为整数，所以3m+4n221,⑤22另一方面，当m=27,n=35时，m+m+n=1981<1987,且3m+4n=221。故3m+4n的最大值为221。评注：在论证过程中用到了柯西不

3、等式与一般二元一次不定方程的求解方法。题2．设空间中有2n(n≣2)个点，其中任何四点都不共面。将它们之间任意连接N条线段，这些线段都至少构成一个三角形，求N的最小值。22思路分析：通过构造实例，说明N≣n+1，进而证明当N=n+1时，若在2n点间连有N条线段，则这些线段至少构成一个三角形。其证明过程可用数学归纳法或反证法或极端原理，在证明过程中要精打细算。解法一：将2n个已知点均分为S和T两组：S={A1，A2，„，An}，T={B1，B2，„Bn}。现将每对点Ai和Bj之间都连结一条线段AiB

4、j，而同组的任何两点之间均不连线，则共2有n条线段。这时，2n个已知点中的任何三点中至少有两点属于同一组，二者之间没有连22线。因而这n条线段不能构成任何三角形。这意味着N的最小值必大于n。2下面我们用数学归纳法来证明：若在2n个已知点间连有n+1条线段，则这些线段至少构成一个三角形。2当n=2时，n+1=5，即四点间有五条线段。显然，这五条线段恰构成两个三角形。设当n=k（k≣2）时命题成立，当n=k+1时，任取一条线段AB。若从A，B两点向其余2K点引出的线段条数之和不小于2k+1，则必定存在

5、一点C，它与A，B两点间都有连线，从而△ABC即为所求。若从A，B两点引出的线段条数之和不超过2K，则当把A，B两点除去后，其余2的2K点之间至少还有K+1条线段。于是由归纳假设知它们至少构成一个三角形，这就完成了归纳证明。2综上可知，所求N的最小值为n+1。2解法二。构造例子同解法一，可知所求的N的最小值不小于n+1。2由于2n个点间连有n+1条线段，平均每点引出n条线段还多，故可猜想必定有一条线段的两个端点引出的线段数之和不小于2n+1，让我们用反证法来证明这一点。设从A1，A2，„，A2n引

6、出的线段条数分别为a1，a2，„，a2n且对于任一线段AiAj都有ai+aj2≢2n。于是，所有线段的两个端点所引出的线段条数之和的总数不超过2n（n+1）。但在此清北学堂-高中学业规划专家http://www.qbxt.cn计数中，Ai点恰被计算了ai次，故有2na22i≢2n（n+1）。（1）i12na2另一方面，显然有i=2（n+1）。由柯西不等式有i12n2na2a2（i）≢2n（i），i1i12n21222ai≣×4（n+1）＞2n（n+1）（2）i12n（2）与（1

7、）矛盾。从而证明了必有一条线段，从它的两个端点引出的线段数之和不小于2n+1。不妨设A1A2是一条这样的线段，从而又有Ak（k≣3），使线段A1Ak，A2Ak都存在，于是△A1A2Ak即为所求。2解法三构造例子同解法一，可知所求的N的最小值不小于n+1。下面我们用极端原理22来证明，当N=n+1时，这些线段至少构成一个三角形。从而所求的N的最小值即为n+1。2设2n个已知点间连有n+1条线段，且这些线段不构成任何三角形，设A是2n点中引出线段条数最多的一个点，共引出k条线段：ABj，j=1，2，„

8、，k。于是{B1，„，Bk}之中任何两点间都没有连线，否则必构成三角形。因而，从任一Bj引出的线段条数不超过2n-k。除了A，B1，„，Bk之外还有2n-k-1点，其中任何一点引出的线段条数当然不超过k。于是得到21［k+k(2n-k)+(2n-k-1)k］=k(2n-k)≢n2n+1≢,矛盾，这就完成了全部证明。2评注：本题用了三种方法求解，都是先通过例子确定出N的一个下界，然后用不同的方法证明这个下界是可以达到的，进而求出N的最小值。解法一用到数学归纳法，解法二运用了反证法与柯