1月培训组合趣题_氯化钡和硫酸银

http://blog.sina.com.cn/u/2791435477

首页博文目录关于我

个人资料

微博

加好友发纸条

写留言加关注

博客等级：
博客积分：

博客访问：
关注人气：
获赠金笔：0支
赠出金笔：0支
荣誉徽章：

正文字体大小：大中小

1月培训组合趣题

(2014-02-01 22:10:56)

标签：

组合

最值

期望

染色

构造

分类：数学趣题-组合-图论-操作-游戏

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 个格不能拿走棋子。很容易发现下面画叉的格不能拿走棋子。

http://s3/mw690/0032UzSRgy6Gb1N3F4u52&690

稍微解释一下这些叉都是如何得到的：在前五行画上 8 条竖线，最后两行的最左边再画 2 条横线，这样右下的 6 个格子是空的，这些棋子不能被取走。四个角上共 24 个叉同理。在左上和右下各画 3 条竖线，在左下和右上各画 2 条竖线，剩下中间 6 个格子，这些棋子也不能被取走。

然后又可以得出，四个圈里的棋子必须拿走，否则就和画叉的格子连五了。而这显然违反了“每条线上恰好有一个棋子”的规矩（这条线可以从上面任何一种划线方案中找...）。矛盾。

而拿走 11 个棋子则是可以的。如下图，画圈的棋子是被拿走的。

http://s16/mw690/0032UzSRgy6GfhU9pi79f&690

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 方格表的左下角放有一枚棋子，规定棋子每次只能往上，往右或往左下走一格，那么这枚棋子能否从左下角出发不重复地经过所有格子？

答案：

显然这时不能用两种颜色染色了...不过，我们可以用三种颜色。如下图涂色即可。

http://s5/mw690/0032UzSRgy6Gfjp4oe094&690

显然，如果按照题目要求移动棋子，那么棋子走过的颜色一定按照“红蓝绿红蓝绿...”的顺序变化。现在数一下三种颜色的方格有多少：共有 21 个红格， 22 个蓝格， 21 个绿格。而如果按照“红蓝绿红蓝绿...”的顺序，蓝格一定不会比红格多。矛盾。于是题目要求是不可以满足的。

6.对于什么样的 n ，在凸 n 边形的边上依次标上 1,2,3,...,n 后，存在一种划分，将凸 n 边形分成 n-2 个三角形后，在没有标数的边上标上合适的整数，可以使得每一个三角形边上三个数的和相等。

答案：

先对于比较小的 n 进行试验，发现 n=3,4,5 时这种划分是存在的。

http://s10/mw690/0032UzSRzy6JnRpzwr729&690

而 n=6 时找不到满足条件的划分，事实上，只要 n 除以 4 余 2 ，那么没有满足条件的划分。证明很简单，若 n=4k+2 ，则划分成的三角形有偶数个，把它们对应的三数和加起来，应该是个偶数（因为所有三数和都一样）。而这个总和里所有对角线算了两次，所有边算了一次，因此各边之和应该是个偶数。但是 1+2+3+...+n 是个奇数，矛盾。

对于其它的 n ，满足条件的划分都是存在的。我们以 4 为步长，用数学归纳法证明。假设凸 n 边形存在满足要求的划分，可以构造证明凸 n+4 边形存在满足要求的划分：

http://s12/mw690/0032UzSRgy6GfkEmuRZ9b&690

先把图中标着 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.设http://s11/mw690/0032UzSRgy6GfBW4oT85a&690为互不相等的两组实数，在一个 100*100 的方格表里填数，第 i 行第 j 列的方格填入http://s8/mw690/0032UzSRgy6GfCjk903b7&690，已知每一列数的乘积均为 1 ，求证每一行数的乘积均为 -1 。

答案：把已知条件写出来就是

http://s12/mw690/0032UzSRgy6GfCriV0D2b&690

其中 j 可以取 1,2,3,...,100 。把 1 移到左边来，再把 b_j 看成变量的话，左边就是一个次数为 100 ，且最高次项的系数为 1 的多项式。这个多项式有 100 个根 b_1,b_2,b_3,...,b_100 。于是下面这个恒等式肯定成立：

http://s14/mw690/0032UzSRgy6GfCGmz4Vad&690

然后把 x 取为各个 a_i 的相反数，就把这个题证出来了。

多项式有时是解决问题的非常有力的工具，后面慢慢再说...

10.在边长为 20*25 的长方形内任意放置 120 个边长为 1 的正方形（可以重叠），证明在长方形内还可以放置一个直径为 1 的圆，它与 120 个正方形中的任意一个都不重叠。

答案：

“能不能放下一个圆”这类问题有个很强的转化：能不能放下一个半径为 1/2 的圆，等价于能不能找到一个点，它到所有“障碍物”的距离不小于 1/2 。那么我们先把所有“障碍物”都往外扩一圈宽度为 1/2 的边，再看一看还有没有没被覆盖的地方（如果有的话，在里面随便取一点为圆心就行了）。

这里“障碍物”就是长方形的边界和 120 个正方形。大长方形经过“扩边”（注意是朝里扩）后显然变成了一个 19*24 的长方形。而正方形向外“扩边”后得到的图形就有意思了：

http://s1/mw690/0032UzSRgy6GfDss704e0&690

中间的虚线围成的正方形边长为 1 ，周围的四条线段距离相应正方形边的距离为 1/2 ，四个角上各有一段 90°圆弧，半径也为 1/2 。实线围成的面积可以计算出来，是 3+π/4 ，我们发现这个数的 120 倍是小于 19 乘 24 的。这样就证明了总有没覆盖到的地方，在没覆盖的地方随便取一点为圆心，作个半径为 1/2 的圆就满足题目要求了。

11.设 p 为奇素数，求证：

http://s12/mw690/0032UzSRgy6GfDUfmL9ab&690

其中 i^(-1) 表示 i 模 p 的数论倒数，即在 1,2,3,...,p-1 内唯一的与 i 的乘积模 p 余 1 的整数。

答案：

好吧，既然混在组合题里面了...那就提示一下，第一步用二项式定理，后面还用到某些组合恒等式。

二项式定理...公式里的 2^i 看着有点二项式定理的影子。那么我们把左边展开一下：

http://s10/mw690/0032UzSRgy6GfEhiwqt29&690

第二个等号前后是一样的，对 sigma 符号头疼的可以拆开写...不过看着没简单多少，反倒复杂了。还好我们发现了求和项的一个共同点：-1 下面那个数与 C 右下角那个数一样。

这有啥用？我们不妨把 i^(-1) 类比为 1/i ，这就和某个组合恒等式联系起来了：

http://s12/mw690/0032UzSRgy6GfEDkCD19b&690

在实数的领域，我们两边同乘以 1/ij ，左边就出现了 C(i,j)/i ，在这里，我们稍微变通一下，两边乘以 i,j 的数论倒数之积，就可以得到

http://s12/mw690/0032UzSRgy6GfERYIPx5b&690

这样，原来的式子可以继续化简。为方便起见，我们先交换求和次序，便于把 j=0 的情况拿出来，剩下的部分可以提出 j^(-1) ：

http://s13/mw690/0032UzSRgy6GfFsrnSA1c&690

为了方便，这里把 = 和 ≡ 放在一块用，反正所有运算在模 p 下进行。第一个等号是交换求和顺序（对 sigma 符号头疼的可以拆开写...看看是不是一样。后面不再说了）。第二个等号用了上述公式替换。最后一个等号的前面一项利用了一个显然的事实：当 i 取遍 1,2,3,...,p-1 时， i 的数论倒数也取遍这 p-1 个整数。事实上，前面一项就等于 p(p-1)/2 ，因为 p 为奇数，所以这一项是 p 的倍数，在模 p 意义下可以忽略它。后面一项则是乘法分配律。

现在问个问题，后面一项的里面那个 sigma 能不能求。这是很简单的，用高中课本上的知识就可以解决：利用公式 http://s2/mw690/0032UzSRgy6GfFXwVUte1&690替换各项（当然， i=j 时这个式子要变成 C(i-1,j-1)=C(i,j) ），然后就可以消项了。于是里面那个 sigma 就变成了 C(p-1,j)：

http://s10/mw690/0032UzSRgy6GfGedT6h59&690

最后，我们试着证明 C(p-1,j) 与 (-1)^j 模 p 同余（如果这是对的，那么我们就证完了）。只要注意到一个事实：当 p 为质数时， C(p,k) 是 p 的倍数，其中 k=1,2,3,...,p-1 。于是考虑数列 C(p-1,0),C(p-1,1),C(p-1,2),...,C(p-1,p-1) ，任意相邻两项的和都被 p 整除，而首尾两项被 p 除都余 1 ，这样这个数列被 p 除的余数必然是 1,-1,1,-1,...,1 交替的。这样这题就证完了。

12.设正整数数列 {a_n} (n>=1) 中，每个正整数恰好出现一次。证明：

（1）对于任意正整数 n ，都存在正整数 d ，使得http://s4/mw690/0032UzSRgy6GfIo1hHt83&690；

（2）若对于任意符合要求的数列，都存在正整数 n,d ，使得

http://s12/mw690/0032UzSRgy6GfItJiIzbb&690

其中 k 为常数，则有 k<=4 。

答案：

第一问里 a_n 是固定的（不随 d 变化而变），由于每个正整数恰好出现一次，我们可以找到数列里的某一项 a_(n+t) ，使得数列里所有小于 a_n 的项都出现在它前面，然后考虑数列 a_(n+t),a_(n+2t),a_(n+4t),a_(n+8t),... ，该数列的任意一项都大于 a_n ，这个无穷数列不可能是递减的，因为它是正整数数列，因此必然存在相邻两项满足序号小的小于序号大的，这两项和 a_n 就满足题意。

第二问提示我们构造出不存在

http://s12/mw690/0032UzSRgy6GfK6X1xxab&690

的无穷数列 {a_n} 。常用的一个思路是让数列分段递减（显然不能每个地方都递减，因为这是正整数数列并且是无穷的），如果分段长度固定不变，那么很容易就找到了满足上式的 6 项，所以这样不行，最好是分段长度越往后越大。

我们构造这样一个数列：

1, 3,2, 7,6,5,4, 15,14,13,12,11,10,9,8, 31,30,29,28,27,26,25,24,23,22,21,20,19,18,17,16, 63,62,...

方法很简单，先是 1 项递减，然后是 2 项，然后 4 项， 8 项，依次类推。

下面证明这个数列中不存在等距的（即下标成等差数列）且递增的 6 项，事实上反证即可，若存在这样的 6 项，则不可能有两项在同一个递减区间。若倒数第二项 a_(n+4d) 所在的递减区间长度为 L （之所以考虑倒数第二项，是因为它的左右都有限制...），则 a_(n+3d) 和 a+(n+5d) 必然在这个递减区间的左右两边，也就是说 2d>L 。另一方面， a_(n+4d) 所在的递减区间的长度必然大于 (n+4d)/2 （这个由构造数列的规律很容易得出），于是 L>(n+4d)/2>2d 。这就矛盾了。

13.求最小的正整数 m ，使得对于所有整数 n>=m 均有：对于集合 {1,2,3,...,2n-1} 的任意 n 元子集 A ，都可以从集合 A 中选出一些元素（可以全选，但不能不选），它们的和能被 2n 整除。

答案：

n=3 时，取 A={1,3,4} ，则不能选出和为 2n 倍数的一些元素。

下面证明，对任意 n>=4 ，题目要求都是满足的，从而所求 m 的最小值就是 4 。

假设对于某个 n>=4 ，存在不满足条件的集合 A 。证明的关键在第一步，显然 1,2n-1 不能同时在集合 A 中（否则选出这两个元素，它们的和能被 2n 整除），同理 2,2n-2 不能同时在 A 中，……， n-1,n+1 不能同时在 A 中。而集合 A 含有 n 个元素，所以只可能是每对数中恰好取一个放入 A ，同时 n 必须在集合 A 中。

接下来就容易推理了。分类讨论，若 1 在集合 A 中，那么：

n-1 不在集合 A 中（因为 1+(n-1)+n=2n ） ==> n+1 在集合 A 中；

n-2 不在集合 A 中（因为 1+(n-2)+(n+1)=2n ） ==> n+2 在集合 A 中；

……

接下来就是同理可得，这样可得出 n+1,n+2,n+3,...,2n-2 都在集合 A 中。最后注意到 1+n+(n+1)+(2n-2)=4n 是 2n 的倍数（注意这一步要求 n>=4 ，这样才能保证这四个数没有重复的），这就矛盾了。

若 2n-1 在集合 A 中，那么：

n+1 不在集合 A 中（因为 n+(n+1)+(2n-1)=4n ） ==> n-1 在集合 A 中；

n+2 不在集合 A 中（因为 (n-1)+(n+2)+(2n-1)=4n） ==> n-2 在集合 A 中；

……

接下来同理可得 2,3,4,...,n-1 都在集合 A 中，最后注意到 2+(n-1)+n+(2n-1)=4n 是 2n 的倍数（这一步同样要求 n>=4 ），仍然得出矛盾。

于是，不存在不合题意的集合 A ，从而证明了对于任意 n>=4 总满足题意。于是 m 的最小值是 4 。

14.平面上有 n 个点，任意三点不共线，每个点都被染为红黄蓝绿四色中的一种，且满足下述条件：