专题1-- 组合试题

lzk05_lzk0530

写在前面的话：
组合数学，又称为离散数学，但有时人们也把组合数学和图论加在一起算成是离散数学。组合数学是计算机出现以后迅速发展起来的一门数学分支。计算机科学就是算法的科学，而计算机所处理的对象是离散的数据，所以离散对象的处理就成了计算机科学的核心，而研究离散对象的科学恰恰就是组合数学。组合数学的发展改变了传统数学中分析和代数占统治地位的局面。

现代数学可以分为两大类：一类是研究连续对象的，如分析、方程等，另一类就是研究离散对象的组合数学。组合数学不仅在基础数学研究中具有极其重要的地位，在其它的学科中也有重要的应用，如计算机科学、编码和密码学、物理、化学、生物等学科中均有重要应用。微积分和近代数学的发展为近代的工业革命奠定了基础。而组合数学的发展则是奠定了本世纪的计算机革命的基础。计算机之所以可以被称为电脑，就是因为计算机被人编写了程序，而程序就是算法，在绝大多数情况下，计算机的算法是针对离散的对象，而不是在作数值计算。正是因为有了组合算法才使人感到，计算机好像是有思维的。
在1997年11月的南开大学组合数学研究中心成立大会上，吴文俊院士指出，每个时代都有它特殊的要求，使得数学出现一个新的面貌，产生一些新的数学分支，组合数学这个新的分支也是在时代的要求下产生的。最近，吴文俊院士又指出，信息技术很可能会给数学本身带来一场根本性的变革，而组合数学则将显示出它的重要作用。杨乐院士也指出组合数学无论在应用上和理论上都具有越来越重要的位置，它今后的发展是很有生命力，很有前途的，中国应该倡导这个方面的研究工作。万哲先院士甚至举例说明了华罗庚，许宝禄，吴文俊等中国老一辈的数学家不仅重视组合数学，同时还对组合数学中的一些基本问题作了重大贡献。迫于中国组合数学发展自身的需要，以及中国信息产业发展的需要，在中国发展组合数学已经迫在眉睫，刻不容缓。  


1。若多边形V的每个顶点都在多边形W的周界上，就称V是W的一个内接多边形，证明：对于每个具有单位面积的凸多边形W，存在一个非退化的中心对称的内接凸六边形V，且V的面积不小于2/3  
2.已知从有限个平面向量构成
的集合M 中任取三个元素，其中总存在两个
元素a、b，使得a+b∈ M．试求M 中元素个
数的最大值．
3.平面上有7个点，每三点的
两两连线都组成一个不等边三角形．求证：一
定可以找到4对三角形，使每对三角形的公
共边既是其中一个三角形的最长边又是另一
个三角形的最短边．
4.已知r、m、n∈N+．(m>1)．
集合M ={l，2，.…，r}，且A1 ,A2,,…Amn为M
的mn个不同的m元子集．证明：存在集合
A、B满足下列条件：
(1)A∩B=φ，A U B=M；
(2)在A∩ Ai ，B ∩Ai( i=1．2，…,mn)
2mn 个集合中至多有n-1个为空集．
5已知集合X={2006，2006+
l，2006+2，…，2006+k}．求正整数k，使得
集合 X可划分成三个集合A、B、C，满足：
(1) AUBU C=X，
A ∩B=B ∩C=C∩A=φ； ；
(2)集合A、B、C的元素和相等．

lzk05_lzk0530

2：所求M中元素个数的最大值为7．
设点A、B、C是平面上任意三点，考虑7元集合
M={AB，BC，CA，BA，CB，AC，0}，它显然满足条
件．下面证明：M中的元素不能多于7个．
当M中的元素全部共线时；将所有元素的起点
移至同一点，作一条与所有元素平行的直线l并作
出M中所有元素在直线l上的投影。于是，M中的所
有向量均对应以M中元素的共同起点在l上的投影
为原点，直线l的任意取定一个方向为正方向的数
轴上的坐标．从而，同题可转化为求与原题对应的数
集问题(由二维转化为一维)．
接下来证明：该数集中至多有7个元素．
首先证明：该数集中最多有3个正数．假设可能
有不少于4个的元素是正数，其中，最大的4个数分
别为a1，a2，a3，a4，且a1<a2<a3<a4
事实上，a3+a4>a2+a4>a1+a4>a4a4，所以，
和数ai+a4不属于M（i=1，2，3）1，2，3)．而大于a3的元素只
有a4一个，却有a2+a3>a1+a3>a3，于是，在集合{a1，a3，a4}或{a2，a3，a4}中至少有一个集合的任意两个元素之和不在M 中．这与已知矛盾，故该
数集中最多有3个正数．同理，该数集中最多有3个
负数．加上一个0，从而，数集M 中至多有7个元素．
当M中的元素不全共线时，将所有元素的起点
移至同一点0，0，由M的有限性知可作出平面直角坐
标系xOy，使得M中的元素均不与坐标轴平行．下面证明：上半平面内至多有3个元素
首先证明：上半平面的所有元素全不共线．假设
上半平面内存在M中的元素a1与a2共线，则可取，则可取
与a1和a2夹角最小的元素bb．考虑集合{a1，a2，b}，由b的取法，a1+b和a2+b均不在M中(两向量的和向量在这两个向量之间)，于是M中存在a3，使得a3=a1+a2.从而
a3与a1，a2共线，考虑集合{a1，a3，b}}，类似上面的讨论，知M中存在a4与a1，a2共线．如此讨论下去，知M 中存在无穷多
个元素与a1，a2共线，矛盾．故上半平面的所有元素
全不共线。
其次证明：上半平面内至多有3个元素．假设在
上半平面内有不少于4个元素，按逆时针方向顺次
取其中4个相邻元素a、b、c、d．．考虑集合{a，b，c}则有b=a+c；考虑集合{b，c，d}则有c=b+d；从而b=a+c=a+b+d，即a+d=0．这与a、d
同在上半平面内矛盾，故上半平面内至多有3个元
素．同理，下半平面内至多有3个元素．加上零向量，
从而，集合M中至多有7个元素．
综上所述，集合M中元素个数的最大值为7．

[ 本帖最后由 lzk05_lzk0530 于 2008-4-5 19:13 编辑 ]

lzk05_lzk0530

3：记平面上的7个点为A1，A 2，…… ，A7。因为每
三点两两连线都组成不等边三角形，故每个三角形
都有最长边，也都有最短边．现将每个三角形的最长
边都染上红色，剩下的边染上蓝色，则每一个三角形
都有红色边．下面证明：C（3，7）个三角形中必有4个同色三角
形．
(1)6阶完全图的边作二染色，至少有2个同色
三角形．
设Ai的引线中有xi条红线，5-xi条蓝线，，以
Ai为顶点的非同色三角形有xi（5-xi）个
由xi（5-xi）小于等于（5/2）^2，知xi（5-xi）小于等于6
则非同色三角形总计为1/2  Σ xi（5-xi）≤1/2（6*6）=18（i=1，2，3，4，5，6）
故同色三角形的个数N满足N=C(3,6）-1/2  Σ xi（5-xi）≥20-18=2
(2)7阶完全图的边作二染色，至少有4个同色
三角形．
由(1)的证明知，此时，至少有2个同色三角形．
不妨设其中一个为△A1A2A3，去掉A1，对剩下的6
个点又应有2个同色三角形，且异于△A1A2 A3，这
就得到3个同色三角形．这3个同色三角形有9个顶点，取自7个不同
的点，故至少有2个顶点重合于某一Aj（1≤j≤7），去掉Aj，则去掉了2个同色三角形，剩下的6个点又应有2个同色三角形，它们与被去掉的2个同色三
角形是不相同的，故一共有4个不同的同色三角形．
(3)由于每一个三角形都有红边，这4个同色三
角形必为红色三角形，每个红色三角形的最短边必
为另一个三角形的最长边．这就找到了4条连线(每
个红色三角形的最短边，即使是两个红色三角形的
公共边也没有关系)，每一条既是一个三角形的最长
边(红色)，又是另一个三角形(所在红色三角形)的
最短边．

lzk05_lzk0530

5：X中元素的和：2006（k+1）+1/2k（k+1）=2004（k+1)+1/2（k+1）（k+4)
故3I （k+l）*（k+4)．
又(k+1)( k+4)=(k+1）^2 +3(k+1)，则
3I(k+1) ^2，因此3I(k+1) ，即k=3m-1(m∈N+)．
(i)当m为偶数，即k=6n-1(n∈N+)时，集
合x中的元素个数为6的倍数．只须从2 006起，将
每6个连续整数中的首尾两数划入A，中问两数划
入曰，余下的两数划入C。则这样得到的集合A、B、
C符合要求．
(ii)当m为奇数，即k=6n-4(n ∈N+)时，若n=1
X={2 006，2006+1，2006+2}，显然不存在符
合条件的划分．若n=2，取A={2 006，2006+4，2 006+8}，
B={2 006+2。2006+3，2006+7}，
C={2 006+1，2 006+5，2 006+6}，是符合条件的一个划分．
若n=3，集合X中的元素比n=2时多6个元素，，将多出的6个元素按（i）中方法并入n=2时划分的集合A,B,C，知所得的集合符合要求，依此类推，知n>3时，所得的集合符合要求。综上，所求的正整数
k=3rn-l(m属于N+，m>1)．

ccmmjj

是好东西呢