第二章 组合数学观点下的中学数学 作业).doc

一、必做作业： 1．设ABC为一等边三角形，E是三边上点的全体。对于每一个把E分成两个不相交子集的分划，问这两个子集中是否至少有一个子集包含着一个直角三角形的三个顶点？ 解：如图，在边BC、CA、AB上分别取三点P、Q、R，使显然△ARQ，△BPR，△CQP都是直角三角形. 它们的锐角是30°及60°. 设E1，E2是E的两个非空子集，且,由抽屉原则知P、Q、R中至少有两点属于同一子集，不妨设P、Q∈E1. 如果BC边上除P之外还有属于E1的点(如下图)，那么结论已明. 设BC的点除P之外全属于E2，那么只要AB上有异于B的点S属于E2，设S在BC上的投影点为Ｓ′，则△SS′B为直角三角形. 再设AB内的每一点均不属于E2，即除B之外全属于E1，特别，R、A∈E1，于是A、Q、R∈E1，且为一直角三角形. 从而命题得证. 平面上给定2005个点，其中任何三点中都有两点的距离小于1。求证：存在一个半径为1的圆，它至少盖住给定的2005个点中的1003个点。 证明：（1）在给定的2005个点中任选一点，记为,以为圆心作一个半径为1的圆，若其余的2004个点都在圆内，则结论成立； （2）否则，在圆外的点中任选一点，记为，以为圆心作一个半径为1的圆，则，除去以外的其余2003个点必在圆或圆内；否则，至少存在一点在圆或圆的外部，则三点任意两点间的距离均大于1，与条件矛盾，所以除去以外的其余2003个点必在圆或圆内。根据抽屉原理：必有一个圆内至少有个点，再加上圆心共有1003个点。因此，存在一个半径为1的圆，它至少盖住给定的2005个点中的1003个点。 3．求不大于100（题目少了的）而至少能被3，5，7之一整除的自然数的个数。 解：不大于100的数中： 能被3整除的自然数有33个； 能被5整除的自然数有20个； 能被7整除的自然数有14个； 既能被3整除又能被5整除（即能被15整除）的自然数有6个； 既能被3整除又能被7整除（即能被21整除）的自然数有4个； 既能被5整除又能被7整除（即能被35整除）的自然数有2个； 既能被3整除又能被5整除，还能被7整除（即能被105整除）的自然数有0个； 从而可得求不大于100而至少能被3，5，7之一整除的自然数的个数为：33+20+14-6-4-2+0=55（个）。 4．某会议的1991个人参加，已知他们每个人都至少和其中的一个人握过手，证明：必有一个人至少和其他两个人握过手。 证明：先从3个人开始考虑，用点的个数来表示人数，设3个人为,则由已知可设为与握手，而对于来说，他必与其中一人握手，不妨设与握手；如图；从而命题得证； 接着考虑5个人，如图,同样命题可证； 总之，只要考虑奇数点可以得出命题成立；而题中为1991人，正好是奇数，因此命题得证。 5．证明任意6个人中，总有3个人或者互相认识，或者互相不认识。 证明：两人互相认识用红色相连，两人互相不认识用黑色相连，则由抽屉原理，6人中的某个人至少和个人互相认识（或者不认识）；不妨设与这三个人互相认识，如下图： 这三人中，若有其中两人互相认识，不妨设与互相认识，则这三人互相认识，命题得证； 这三人中，都互相不认识，命题得证； 综上，任意6人中，总有3个人互相认识，或者互相不认识。 二、选做作业： 1．整数1，2，…，n的排列满足：除最前面的一个数外，每个数都与前面的某个数差1。试问有多少个这样的排列？ 2．设[x]表示不超过x的最大整数。试对任意的正整数n，计算和。 解：①当为奇数时，则，并且当时，我们有，所以 ②当为偶数时，，令，则有，而，所以。 综合①②，由数学归纳法容易证明。 3．n个城市，每个城市都可以通过一些中转城市与另一个城市通话，证明：至少有n-1条直通的电话线路，每条连结两个城市。 4．设是平面上的一个点集，它的任意两点间的距离至少为1。证明：S中最多有3n-6个点对，它们之间的距离为1。 证明： 5．某厂生产由6种不同颜色的纱织成的双色布。在这个工厂生产的双色布中，每1种颜色至少和3种其他的颜色搭配。证明：可以排出3种不同的双色布，它们含有所有6种颜色。 证明：（1）建立图：一个点代表一种颜色，两个点相邻当且仅当这个工厂生产出一种由这两个点所对应的这两种颜色搭配而成的双色布； （2）由题意，所得图是6阶简单图，且每个点的度至少为3； （3）证明这个图有一个完美对集。 6．名选手参加循环赛，任何两人都比赛