数学奥林匹克题解E组合数学 E2计数和离散最值071-080)汇总.pdfVIP

E2－071设n和k是正整数，S是平面上n个点的集合，满足：

（1）S中任何三点不共线；

（2）对S中的每一个点P，S中至少存在k个点与P距离相等．

【题说】第三十届（1989年）国际数学奥林匹克题3，本题由荷兰提

供．条件（1）可以取消．

【证】以S中的两个点为端点的线段称为“好线段”．

另一方面，以S中任一点P为圆心，可以作一个圆，圆上至少有k

计算在内）．从而至少有

条弦是好线段．

E2－072学校举办足球循环赛，每个参赛队都与其他队各赛一场，胜一

场积2分，平一场积1分，负一场积0分，已知仅有一个队积分最多，但他胜

的场数最少，问至少有几队参赛，才有可能这样？

【题说】第十六届（1990年）全俄数学奥林匹克九年级题5．

【解】称积分最多的为冠军，设冠军胜n场，平m场，则他共积2n+m

分，由题设，其余各队胜的场数不少于n+1，即积分不少于2（n+1）．由2n+m

＞2n+2得m≥3．从而有队踢过平局，他们的积分不少于2（n+1）+1，由

2n+m≥2n+3，得m≥4．

冠军队至少胜1场，否则，它的积分不多于S-1（S是参赛的队数）．其

余队的积分少于S-1，于是所有参赛队积分之和少于S（S-1）．而每赛一场，

双方积分之和总是2分，因此所有队积分之和应是2·S（S-1）/2=S（S-1），

矛盾．

这样，m≥4，n≥1，因此冠军队比赛场数不少于5，参赛队数（包括冠军

队）不少于6．

下面的比赛积分表表明，有6个队（分别用A、B、C、D、E、F表示）参

赛且满足题设要求的比赛结果．因此至少6队参赛．

E2－073设n≥3．考虑在同一圆周上的2n-1个互不相同的点所成的集合

E．将E中一部分点染成黑色，其余的点不染颜色．如果至少有一对黑点，以

它们为端点的两条弧中有一条的内部（不包含端点）恰含E中n个点，则称这

种染色方式为好的．如果将E中k个点染黑的每一种染色方式都是好的，求k

的最小值．

【题说】第三十一届（1990年）国际数学奥林匹克题2．本题由捷克提

供．

【解】将E中的点依次记为1，2，3，…，2n-1，并将点i与i+（n-1）

用一条边相连（我们约定j+（2n-1）k·，k∈Z，表示同一个点j）．这样得到

一个图G．G的每个点的次数均为2（即与两个点相连），并且相差为3的两个

点与同一点相连．

由于G的每个点的次数为2，G由一个或几个圈组成．

在32n-1时，1，2，…，2n-1中每一点j都可以表示成3k的形式

（即方程3x≡j（mod2n-1）有解），因此图G是一个长为2n-1的圈．在这圈

上可以取出n-1个互不相邻的点，而且至多可以取出n-1个互不相邻的点．

为

共可取出n-2个点互不相邻．

综上所述，在32n-1时，mink=n．在3|2n-1时，mink=n-1．

E2－074地面上有10只小鸟在啄食，其中任意5只鸟中至少有4只在一个圆

周上，问有鸟最多的一个圆周上最少有几只鸟？

【题说】1991年中国数学奥林匹克题3．

【解】9只鸟在同一圆周上，1只鸟不在这圆周上，满足题目条件．

设有鸟最多的圆上至少有l只鸟，则4≤1≤9．

首先证明，l≠4．由l≤9，必有4只鸟不在同一圆周上，过其中每3只作

一个圆，共得4个圆，其余6只鸟中的每一只与上述4只鸟组成5元组，因而

这