数学奥林匹克题解E组合数学 E2计数和离散最值031-040)

1、E2-031 在一种“咬格子”的游戏中，两名选手轮流“咬”一个由单位正方形组成的5×7网格所谓“咬一口”，就是一个选手在剩下的正方形中挑一个正方格子去掉（“吃掉”）它的左面的一条边（朝上延长）与底边（朝右延长）所确定的象限中的全部正方形格子，如图a所示，有阴影的格子是选定的，吃掉的是这个有阴影的及打“×”的四个格子（虚线部分是在这之前已被“吃掉”的）游戏的目标是要对手“咬”最后一口图b所示的是35个正方形组成的集合的一个子集，它是在“咬格子”游戏过程中可能出现的一个子集在游戏过程中，可能出现的不同的子集总共有多少个？整个网格及空集也计算在内【题说】 第十届（1992年）美国

2、数学邀请赛题12【解】 根据游戏规则，每次“吃”剩下的图形有如下特点：从左到右，各列的方格数不增因为如某一方格被“吃”，那么它右面和上面的格子全部被“吃”于是每次剩下的图形从A到B的上边界是一条由7段横线与5段竖线组成的折线，且它是不增的；反之，每一条这样的折线，也对应一块“吃”剩下的方格集 E2-032 1克、30克、50克三种砝码共110个，总重量为1000克，问其中30克的砝码有多少个？【题说】 第一届（1990）希望杯高一二试题2（4）原是填空题【解】 设1克、30克和50克砝码数分别有x、y、z，则有以下关系：（2）-（1）得29y+49z=890  &

3、#160;                                             （3）因29 890，49 890，所以y0，z0即y1，z

4、1从而890=29y+49z29+49z由于z是整数，故z17令z=1，2，17，代入（3），知：只有当z=1时，y=29是唯一整数解又由（1）知，x=80即这一组砝码中有29个30克的砝码E2-033 下图中将等边三角形每边3等分，过等分点作每边平行线，这样所形成的平行四边形个数，记为f（3），则f（3）=15将等边三角形每边n等分，过各分点作各边平行线，所形成的平行四边形个数记为f（n），求f（n）表达式【题说】 第二十三届（1991年）加拿大数学奥林匹克题5【解】 如图所示的平行四边形，由a、b、c、d四个数决定这4个数满足a1， b1， c0，d02a+b+c+dn即0a1+b1+c+

5、dn-2其中a1=a-1，b1=b-1，c，d均为非负整数因此平行四边形的总数为【别解】 在BA、BC的延长线上分别取E、F，使BE=BF=n+1，则EF=n+1图中的平行四边形，每一边恰好与EF相交于一点这四点不同，都是EF上的格点（即将EF等分为n+1份的分点）反之，从EF的n+2个格点（包括E、F在内）中任取四点，过靠近E的两点作AB的平行线，过另两点作BC的平行线，便可得到一个图中的平行四边形，所以E2-034 若平面上有997个点，如果每两点连成一条线段，且中点涂成红色证明：平面上至少有1991个红点你能找到一个正好是1991个红点的特例吗？【题说】 1991年亚太地区数学奥林匹克题

6、2【证】 在给定的997个点中，设M、N两点间的距离最大，分别以 M、N为圆心，MN/2为半径作圆，这两个圆仅有一个公共点，即MN的中点E于是MP的中点必在M内部或圆周上，这样的995个点互不相同同理，NP的中点必在N内部或圆周上，这样的995个点互不相同，而且与上面的995个中点均不相同，加上点E，共有2×995+1=1991个红点x轴上横坐标分别为1，2，997的997个点就是满足要求的例子 E2-035 A，B分别是坐标平面上的格点的集合：A=（x，y）|x，y为正整数，1x20，1y20B=（x，y）|x，y为正整数，2x19，2y19A中的点分别染成红色或蓝色染成

7、红色的点有219个，其中有180个包含于B中，又四个角上的点（1，1），（1，20），（20，1），（20，20）都染成蓝色将水平或垂直方向上相邻两点按下列要求用红、蓝、黑色的线段连接起来：两点均为红色时，用红线连接；两点均为蓝色时，用蓝线连结；两点为一红一蓝时，用黑线连结问：（长度为1的）黑线有237段时，（长度为1的）蓝线有多少段？【题说】 1992年日本数学奥林匹克预选赛题9【解】 集合A中有400个点，其中红点有219个，蓝点有181个，在B内有蓝点144个A的四周有76个点，其中红点39个，蓝点37个（包括四个角上的点）每个角上的点引出2条线段；每个边界上（除四个角）的点引出3条线段

8、；每个B内的点引出4条线段因此，对于蓝点共引出线段2×4+3×33+4×144=683（段）其中黑线有237段，所以蓝线有683-237=446（段）这些蓝线在上述计数时，被重复计算了一次，故实际上有蓝线446÷2=223（段） E2-036 设集合A=1，2，10A到A的映射f满足下列两个条件：（1）对任意XA，f(30（x）=x；（2）对每个正整数k，1k29，至少存在一个aA，使得f(k（a）a其中f(1（x）=f（x），f(2（x）=f（f（x），f(k+1（x）=f（f(k（x），求这样的映射的总数，【题说】 1992年日本数学奥林匹

9、克预选赛题12【解】 设A划分成3个互不相交的子集：a1，a2，a3，a4，a5b1，b2，b3c1，c2并且定义映射f：f（a1）=a2，f（a2）=a3，f（a3）=a4，f（a4）=a5，f（a5）=a1；f（b1）=b2，f（b2）=b3，f（b3）=b1；f（c1）=c2，f（c2）=c15，3，2两两互素，30是它们的最小公倍数由条件知，f不是恒等映射，且 f由若干个循环组成，这些循环的阶数的最小公倍数应为30从而，f是满足条件（1）、（2）的唯一一类映射所以，f的总数相当于从10个元素中选取5个，再从剩余的5个中选3个，它们再分别进行循环排列的个数故所求映射的总数是 E

10、2-037  一副牌有 2n+ 1张，由一张王及标 1至 n的牌每种各两张组成这2n +1张排成一行，王在正中间，对每个k，1kn，两张标k的牌之间恰有k-1张牌确定所有不超过10并且有这种排法的n对哪些n，不可能这样排？【题说】第二十四届（1992年）加拿大数学奥林匹克题5【解】设标i的牌，从左数起位置为ai与bi（aibi，i=1，2，n因为王牌位置为n+1，bi=i+ai，所以即因此4n（n+1）n=1，2，5，6，9，10不满足上述要求n=3时，解为232J311n=4时，解为2423J4311n=7时，解为2723563J7546114n=8时，解为78426247J865

11、31135 E2-038  在4000至7000之间有多少个四个数字均不相同的偶数？【题说】第十一届（1993年）美国数学邀请赛题1【解】答：728若千位数字为4或6，这时千位数字有2种选法，个位数字有4种选法，百位数字有8种选法，十位数字有7种选法所以共有2×4×8×7=448个数符合要求同理，若千位数字为5，有 1× 5× 8× 7= 280个偶数符合要求所以，共有448+280=728个 E2-039  令S为一个有6个元素的集合问有多少种不同的方法可以把S分成两个不一定不同的子集，使得这

12、两个子集的并恰好是S？两子集的顺序不必考虑，如a，c，b，c，d，e，f与b，c，d，e，f，a，c算一种分法【题说】第十一届（1993年）美国数学邀请赛题8【解】365设S=AUB，S中每一个元素，或属于A，或仅属于B，或同时属于A、B，共3种情况所以如果S中有n个元素，共有3n种方法选择集合A和B除了A=B=S的情况，如果不计顺序每种情形算了2次，所以共有种分法特别地，n=6时，共有365种分法E2-040  红色和白色的椅子各有5张，围成一个圆圈，共有多少种不同的排法？同色的椅子是没有区别的，经旋转后排列的顺序一致的排法只算1种【题说】1994年日本数学奥林匹克预选赛题7【解】将椅子的位置编号为09红色椅子的位置是集合A=0，然有f(10（R