加载中…抽屉原理的精彩变形——覆盖问题
(2011-09-02 18:09:53)
标签：
抽屉原理反证法两点距离覆盖 |
分类： 中学数学答疑室 |
【问题】平面上给定有2n+1个点，已知其中每3个点中都至少有2个点的距离不大于1。证明存在一个半径是1的圆，至少可以盖住其中n+1个点。
【证明·反证法】假如结论不成立，即任意一个半径是1的圆，至多可以盖住给定的2n+1个点中的n个点。
在给定的2n+1个点中任取一点A，以A为圆心1为半径作圆，那么圆A至多可以盖住给定的2n+1个点中的n个点。即至少有n+1个点不在圆A内。
在这不在圆A内的n+1个点中任取一点B，再以B为圆心1为半径作圆，那么圆Ｂ至多可以盖住不在圆A内的n+1个点中n个点。
这样，至少有一点C既不在圆A内，又不在圆B内。于是就得到了三个点A、B、C，他们之间的连线AB、AC、BC的长都大于1。
即在A、B、C三点中无两点距离不大于1，与题设条件矛盾。
因此原先假定不成立，即存在一个半径是1的圆，至少可以盖住其中n+1个点。
【解析】证明的过程似乎与抽屉原理无关，这是表象。就其本质来说，圆A、圆B就是两个抽屉，反证法最终证明了，2n+1个点能够放得进两个抽屉内的，根据抽屉原理结论成立。
明白了这一点，再把问题归结为抽屉原理，就显得勉强和噜苏了。
喜欢
0
赠金笔
后一篇：山路水桥调侃：一键之误 意远万里