组合数学(3)|江阴雨辰互联

2023年7月19日发(作者：)

组合几何（3）

题型一覆盖

定义设Ｇ和Ｆ是两个平面图形．如果图形Ｆ或由图形Ｆ经过有限次的平移、旋转、对称等变换得到的大小形状不变的图形Ｆ′上的每一点都在图形Ｇ上．我们就说图形Ｇ覆盖图形Ｆ；反之，如果图形Ｆ或Ｆ′上至少存在一点不在Ｇ上，我们就说图形Ｇ不能覆盖图形Ｆ．

定义对于图形Ｇ１，Ｇ２，„，Ｇｎ，若图形Ｆ中的每一点都被这组图形中的某个所覆盖，则称这几个图形覆盖图形Ｆ

关于图形覆盖，下述性质是十分明显的：

（１）图形Ｇ覆盖自身；

（２）图形Ｇ覆盖图形Ｅ，图形Ｅ覆盖图形Ｆ，则图形Ｇ覆盖图形Ｆ．

定义图形Ｆ中任意两点间的距离最大值ｄ为图形Ｆ的直径．

原则１若图形Ｆ的面积大于图形Ｇ的面积，则图形Ｇ不能覆盖图形Ｆ．

原则２直径为ｄ的图形Ｆ不能被直径小于ｄ的图形Ｇ所覆盖．

1. 直径为１的图形Ｆ可被一个边长为的正三角形覆盖，试证明之．

2．设平面上有有限个正三角形覆盖着面积为S的区域.求证:可以从中取出若干个互不重叠的正三角形,使其覆盖面积大于S/16

题型二极端原理和组合方法

3．平面上有n个红点与n个蓝点，任意三点都不共线．求证：可以用n条线段连结这2n个点，每条线段连结一个红点与一个蓝点，且这n条线段没有公共点．

题型三构造

4．是否存在10个不同的整数，使得从中任选9个数，它们的和都是完全平方数？

5．S是平面上n个不同的点组成的点集，S中任意两点距离的最小值为d。求证：存在一个S的由至少n/7个点组成的子集T，T中任意两点至少相距d

6．在7×8的长方形棋盘的每个小方格的中心点各放一个棋子。如果两个棋子所在的小方格共边或共顶点，那么称这两个棋子相连。现从这56个棋子中取出一些，使得棋盘上剩下的棋子，没有五个在一条直线（横、竖、斜方向）上依次相连。问最少取出多少个棋子才可能满足要求？并说明理由

题型四格点及其性质

皮克公式：格点多边形面积=多边形一周的格点数÷2+多边形内部格点数-1

7.设S是nn的正方形，试证：S盖不住多于(n1)2个格点

8．在7×7的正方形方格表中，将k个方格的中心染成红点，使得其中任何4个红点都不是一个边平行于网格线的矩形的4个顶点，求k的最大值

题型五组合求和

9．设a1,aa,,an是1，2，…，n的一个排列，对于ai，若满足：或者i=n，或者对于一切j（i



题型六极值填数问题

10．是否存在自然数n使得n！的前4个数字为2009？

图论（4）

一、图的基本概念

图：图G是指两个集合(V，E)，集合V为图的顶点集，集合E为图的边集。|V||E|均有限的图称有限图。有边相连的两顶点称为相邻。有些顶点本身有边相连，这样的边称为环。若联结两顶点的边不止一条，称这些边为平行边或重边。不含环和重边的图G称为简单图。对于两个图G(V,E)和G'(V',E')，如果V'V,E'E，就称G'是G的子图。

有向图：每条边都是有向边的图。无向图：每条边都是无向边的图。

出度：与顶点v相连的边数称为该顶点的度数，记为d（v），以该定点为始边的边数为出度，记为d+(v)。入度：以该定点为终边的边数为入度，记为d-(v)。

无向完全图：无向图中如果任何两点都有一条边关连则称此图是无向完全图。记为Kn

完全有向图：有向图中如果任意两点都有方向相反的有向边相连称此图为完全有向图。

（n阶有向完全图的边数为n2；无向完全图的边数为n(n-1)/2。）

定理1 设图G是具有n个顶点m条边的无向图，其中点集V={v1,v2,…,vn}

∑d (vi)=2m

定理2 在无向图中，度数为奇数的顶点个数为偶数

1．某地区网球俱乐部的20名成员举行14场单打比赛，每人至少上场一次．求证：必有6场比赛，其12个参赛者各不相同

2.某俱乐部共有100名成员，每个成员都声称只愿意和自己认识的人一起打桥牌。已知每个成员至少认识67名成员。求证：一定有4名成员，他们可以一起打桥牌

二、树

链：由不同的边组成的序列。圈：如果链中始点与终点相同。