1月培训组合趣题
2014-02-01 22:10阅读：
1.平面上有 2004
个圆，已知任意两个圆都有交点（含切点），是否存在一条直线与所有的圆相交（含相切）？
答案：
在平面上任取一条直线，把所有圆投影到这条直线上得到 2004
条线段，任意两条线段都有至少一个公共点，只需证明所有线段有至少一个公共点，过这个点作这条直线的垂线即可满足要求。
至于如何证明，我们对线段条数归纳。当有 2 条线段时显然成立。当线段条数 n
不小于 3 时，任取三条线段 a,b,c ，并且记线段 b,c 与其余 n-3 条线段的一个公共点为 A
（这一步用了归纳假设），同理定出点 B,C ，则必有一个点在另两个点确定的线段上，不妨设 A 在线段 BC 上，那么由点 B,C
都在线段 a 上可得点 A 在线段 a 上，点 A 就是所有线段的一个公共点。
后面这个小结论可以推广到二维：平面上一组凸集中任意三个都有公共点，则所有凸集有公共点。（凸集是这样的点集，它包含的任意两个点所连线段上的所有点都在点集内）证明类似，当有
3 个凸集时显然成立，当凸集个数不小于 4 时，任取三个凸集 a,b,c,d ，并且类似地定出点 A,B,C,D
，考虑这四个点的凸包，若为三角形，则不妨设点 A 在 △BCD 内部或边界上，那么点 A 显然在凸集 a 内，点 A
就是所有凸集的公共点；若凸包为四边形，则容易看出两条对角线的交点就是所有凸集的公共点。
这个结论还可以推广到高维，这里就不再说了。一些有趣的推论见
这里。
2.圆周上标出 40 个红点， 30 个蓝点 ，20 个绿点，圆周被分割为 90
段弧，每段弧上写一个数：红蓝弧写 1 ，红绿弧写 2 ，蓝绿弧写 3 ，两端点同色则写 0 。求写下的 90
个数之和的最大值。
答案：
在每个点上写一个数，红点写 0 ，蓝点写 1 ，绿点写 2
，则每段弧上的数不大于它两端点写的数之和， 90 段弧上数的总和不大于 90 个点上数之和的 2 倍，也就是 140 。
下面证明这个数可以取到，事实上只需要没有两个蓝点相邻，也没有两个绿点相邻即可，这是很容易做到的，比如说 20 个'蓝绿'接 10
个'蓝红'再接 30 个'红'。
如果要求最小值，显然要让蓝点尽可能相邻，绿点尽可能相邻，最小值为
140-2*29-4*19=6 。
3.在 7*8
棋盘的每个格放一个棋子，现在要拿走一些棋子，使得剩下的棋子没有五个在横、竖或斜方向上依次相连（就像五子棋一样），求最少拿走多少棋子。
答案：
容易看出，拿走 9 个棋子是不够的，因为我们很容易在棋盘上画出 10
条线（横竖斜向，占据 5 个格子，当然我们只需要横竖线），它们互不相交，拿走 9
个棋子则至少有一条线的棋子没有动，就不合题意了。
进一步可以发现，拿走 10 个棋子也是不够的。我们仍然画出 10
条互不相交的线，则只能是每条线上恰好拿走一个棋子，而剩下没被画到的 6
个格不能拿走棋子。很容易发现下面画叉的格不能拿走棋子。
稍微解释一下这些叉都是如何得到的：在前五行画上 8 条竖线，最后两行的最左边再画 2
条横线，这样右下的 6 个格子是空的，这些棋子不能被取走。四个角上共 24 个叉同理。在左上和右下各画 3 条竖线，在左下和右上各画
2 条竖线，剩下中间 6 个格子，这些棋子也不能被取走。
然后又可以得出，四个圈里的棋子必须拿走，否则就和画叉的格子连五了。而这显然违反了“每条线上恰好有一个棋子”的规矩（这条线可以从上面任何一种划线方案中找...）。矛盾。
而拿走 11 个棋子则是可以的。如下图，画圈的棋子是被拿走的。
4.从 {1,2,3,...,n} 中随机取两个 k
元子集（每个集合的所有取法等可能，并且两个集合的选取是独立的），求两个集合交集元素个数的数学期望。
答案：
本来这题没啥好说的，不过原题还有一问是求分布列，带着一大堆组合符号...（好像是超几何分布...）。后面求期望的时候就直接拿来用了...
不过有个非常简单的方法，就是直接利用
和的期望等于期望的和。说得清楚一些，就是几个随机变量的和的数学期望，等于它们各自数学期望的和，不管它们是不是独立的。（还记得
七选五那题吗？）
把每个元素属于不属于交集看成 n 个随机变量（属于就是 1 ，不属于就是 0
），则每个随机变量的期望值显然就等于它属于两集合交集的概率，也就等于 k^2/n^2 （注意 k/n
是某个元素属于某个集合的概率，而某个元素属于第一个集合或属于第二个集合是独立的），于是所求的数学期望就是 n 个期望值的和
k^2/n 。
和的期望等于期望的和这个小结论非常容易理解，但是一遇到实际问题就容易把人弄迷糊...还有一个应用是求二项分布的期望，如果知道这个小结论，一眼就可以看出结果等于
np ， n 是试验次数， p 是成功概率。
5.在 8*8
方格表的左下角放有一枚棋子，规定棋子每次只能往上，往右或往左下走一格，那么这枚棋子能否从左下角出发不重复地经过所有格子？
答案：
显然这时不能用两种颜色染色了...不过，我们可以用三种颜色。如下图涂色即可。
显然，如果按照题目要求移动棋子，那么棋子走过的颜色一定按照“红蓝绿红蓝绿...”的顺序变化。现在数一下三种颜色的方格有多少：共有 21
个红格， 22 个蓝格， 21
个绿格。而如果按照“红蓝绿红蓝绿...”的顺序，蓝格一定不会比红格多。矛盾。于是题目要求是不可以满足的。
6.对于什么样的 n ，在凸 n 边形的边上依次标上 1,2,3,...,n
后，存在一种划分，将凸 n 边形分成 n-2
个三角形后，在没有标数的边上标上合适的整数，可以使得每一个三角形边上三个数的和相等。
答案：
先对于比较小的 n 进行试验，发现 n=3,4,5 时这种划分是存在的。
而 n=6 时找不到满足条件的划分，事实上，只要 n 除以 4 余 2
，那么没有满足条件的划分。证明很简单，若 n=4k+2
，则划分成的三角形有偶数个，把它们对应的三数和加起来，应该是个偶数（因为所有三数和都一样）。而这个总和里所有对角线算了两次，所有边算了一次，因此各边之和应该是个偶数。但是
1+2+3+...+n 是个奇数，矛盾。
对于其它的 n ，满足条件的划分都是存在的。我们以 4
为步长，用数学归纳法证明。假设凸 n 边形存在满足要求的划分，可以构造证明凸 n+4 边形存在满足要求的划分：
先把图中标着 n 的那条对角线连好，右边就是凸 n
边形，它存在一种满足要求的划分，记每个三角形的三边数字和为 S ，将左边那个凸 6 边形如图所示划分并填数即可。
7.对于什么样的 n ，在凸 n
边形的每条边和每条对角线上分别填入 1,2,3,...,n
中的一个数，可以使得每个三角形没有两条填有相同数字的边，并且每两个三角形边上填有的数字不完全相同（顺序不同也算相同）。这里的三角形是指
n 个顶点中的任意三个顶点构成的三角形。
答案：
不妨先数个数，一共有多少个三角形，这个很简单， n 个顶点任取 3 个，一共有
C(n,3) 个三角形。
现在，如果从三角形三边所填数的角度考虑，有多少种填法。既然三角形的三边都不能相同，并且次序不计，那么填法也就是从
1,2,3,...,n 这 n 个数中任取 3 个，一共有 C(n,3) 种填法。
两个数字恰好相等，这说明每种填法恰好被一个三角形使用。
接下来我们数一数含有数 1 的三角形有多少个。如果从填法的角度考虑，显然是从
2,3,4,...,n 中任取 2 个数，一共有 C(n-1,2) 种填法。
另一方面，我们可以数一下有多少条边填了数字 1 。然后，注意到每条这样的边都可以产生
n-2 个含有数字 1 的三角形，并且没有重复的（否则就有一个三角形有两条边都是 1 ，这是不合题意的）。于是
C(n-1,2) 应该是 n-2 的整数倍。两者相除，也就是说， (n-1)/2 应该是整数，从而 n
是奇数。
下面证明，对于所有的奇数 n 都有满足题意的填法。
事实上，凸 n
边形的形状没什么影响，不妨设它为正多边形，而正奇数边形的每条对角线都恰好与一条边平行，我们把边依次标以 1,2,3,...,n
，每条对角线标的数与和它平行的边上标的数一样。
这种方法显然满足第一个条件，因为只有相互平行的线段（不管是边还是对角线）标的数一样，三角形的三条边不可能有两条互相平行。
只需证明第二个条件，假如有两个三角形，它们边上的数相同，那么它们对应边平行，两个三角形应该是相似的。又因为它们内接于同一个圆，于是它们应该全等，而且其中一个绕着外心旋转可以变成另一个。如果对应边平行的话，只能旋转
180° ，而在正奇数边形中，一个顶点绕中心旋转 180°
是不能变成另一个顶点的。所以不存在这样的两个三角形，这种填数方法是成立的。
8.证明：可以将所有正整数分为 100 个非空子集，使得对于任意满足关系式 a+99b=c
的三个数 a,b,c ，都可以从某个子集中找到其中的两个数。
答案：
如果把 100 换成不大于 99 的正整数，这个问题就简单多了：只要保证模 99
同余的所有正整数都在一个集合里，随便怎么分都行，因为 a,c 肯定是模 99 同余的。现在要分成 100
个非空子集，我们还要从另一个角度观察。
其中一种可行的方法是分析奇偶性。显然 a,b,c
三个数或者全为偶数，或者恰好有两个奇数。于是我们把所有奇数拿出来作为一个集合，剩下的数再按模 99
分类。如果有两个奇数，它们就在同一个集合，否则三个数都是偶数，那么 a,c 在同一个集合里。这种方案是可行的。
9.设 
为互不相等的两组实数，在一个 100*100 的方格表里填数，第 i 行第 j 列的方格填入
，已知每一列数的乘积均为 1 ，求证每一行数的乘积均为 -1 。
答案：把已知条件写出来就是
其中 j 可以取 1,2,3,...,100 。把 1 移到左边来，再把 b_j
看成变量的话，左边就是一个次数为 100 ，且最高次项的系数为 1 的多项式。这个多项式有 100 个根
b_1,b_2,b_3,...,b_100 。于是下面这个恒等式肯定成立：
然后把 x 取为各个 a_i 的相反数，就把这个题证出来了。
多项式有时是解决问题的非常有力的工具，后面慢慢再说...
10.在边长为 20*25 的长方形内任意放置 120 个边长为 1
的正方形（可以重叠），证明在长方形内还可以放置一个直径为 1 的圆，它与 120
个正方形中的任意一个都不重叠。
答案：
“能不能放下一个圆”这类问题有个很强的转化：能不能放下一个半径为 1/2
的圆，等价于能不能找到一个点，它到所有“障碍物”的距离不小于 1/2 。那么我们先把所有“障碍物”都往外扩一圈宽度为 1/2
的边，再看一看还有没有没被覆盖的地方（如果有的话，在里面随便取一点为圆心就行了）。
这里“障碍物”就是长方形的边界和 120
个正方形。大长方形经过“扩边”（注意是朝里扩）后显然变成了一个 19*24
的长方形。而正方形向外“扩边”后得到的图形就有意思了：
中间的虚线围成的正方形边长为 1 ，周围的四条线段距离相应正方形边的距离为 1/2
，四个角上各有一段 90°圆弧，半径也为 1/2 。实线围成的面积可以计算出来，是 3+π/4 ，我们发现这个数的 120 倍是小于
19 乘 24 的。这样就证明了总有没覆盖到的地方，在没覆盖的地方随便取一点为圆心，作个半径为 1/2
的圆就满足题目要求了。
11.设 p 为奇素数，求证：
其中 i^(-1) 表示 i 模 p 的数论倒数，即在 1,2,3,...,p-1
内唯一的与 i 的乘积模 p 余 1 的整数。
答案：
好吧，既然混在组合题里面了...那就提示一下，第一步用二项式定理，后面还用到某些组合恒等式。
二项式定理...公式里的 2^i
看着有点二项式定理的影子。那么我们把左边展开一下：
