问双色多边形比无色多边形多多少？

野菜花 · 发表于 2008-2-28 20:51:35

圆周上12有个点，其中有一个点是红色，还有一个点是蓝色，其余10个点没有着色。以这些点为顶点的凸多边形中，其顶点包含了红点及蓝点的多边形称双色多边形；只包含了红点(蓝点)的称红色(蓝色)多边形，不包含红点及蓝点的称无色多边形。www.ddhw.com

问双色多边形比无色多边形多多少？请给出过程。

yinyin's student · 发表于 2008-2-29 12:29:23

Each polygon contains at least three points. The number of polygons containing red and blue points is 2¹⁰-1, while the number of polygons containing only points without color is 2¹⁰-1-C(10,1)-C(10,2). So, the former is C(10,1)+C(10,2)=10+45=55 more than the latter.

idiot94 · 发表于 2008-3-1 07:37:59

只能组合出一个凸5边形呢？为啥不能有两个，三个什么的呢？

野菜花 · 发表于 2008-3-3 18:50:30

名师出高徒

野菜花 · 发表于 2008-3-3 18:53:13

看看，水平高的人喜欢装傻，可是随便问个问题就把我们难住了！

孜孜不倦@. · 发表于 2008-3-4 08:12:42

看到几何头就一片空白。。。

www.ddhw.org---

idiot94 · 发表于 2008-3-5 00:18:07

凸五边形什么的也好像不是平凡的。。。。为啥不是0个呢？呵呵。。

（当然好象也不是那么复杂。。。有了存在性之后，证明唯一性也就简单一些了。。。）

野菜花 · 发表于 2008-3-5 03:40:55

假设ABCDE分别为圆周上依次相邻的五个点，证明ABCDE是凸的。www.ddhw.com

不失一般性，只要说明CDE中任何两点连线与AB不相交就可以了。www.ddhw.com

AB将圆弧分成两部分，一部分没有其它点，一部分包含CDE。直线AB将平面分成两部分， CDE都在AB的同侧。所以CDE三点中任两点连线都在AB的同侧，也就是不会穿过AB。

www.ddhw.com

反之，假设园上五点ABCDE是凸五边形，但ABCDE不是依次相邻，假设AB将圆弧分成两部分，两部分都有点，比方说C和D，那么AB和CD必相交，与凸多边形定义矛盾。

www.ddhw.com

从来没想过这样的问题，也懒得想，连凸多边形的定义也忘了。

野菜花 · 发表于 2008-3-5 03:48:08

你的钻研精神就和你的名字一样，令人佩服！

孜孜不倦@. · 发表于 2008-3-5 07:46:57

被美女称赞，偶脸都红咯

www.ddhw.org---

idiot94 · 发表于 2008-3-5 08:44:21

小的没有看太明白，感觉好像准备从边界入手，和偶的想法不太一样。

偶大概是这么想的：

（先给朋友们热热身，回忆一下几个关于平面上的点集的定义和性质：

1）点集C叫做凸集，如果它满足：如果点A, B 属于C, 那么直线段AB上所有点也属于C.

2）简单多边形：边界为不自相交的有限封闭折线（有限条直线段首尾相连）的图形（以及其内部）。

3）凸多边形：凸的简单多边形。

4）凸集的交集是凸集（无论多少个）。（这里认为空集是凸集）(?)

5) 对于任何一个平面点集S, 所有包含S的凸集的交集，叫做S的凸包。这个凸包是凸的，也是唯一的。（？）

6) 圆（包括边界和内部）是凸集。（？）

好了，后面的问号是表示这些不是定义，也不是完全平凡的结论，需要证明：））

偶们先来证明一个引理：平面上任何一个凸集A，如果被一条直线L分成两半的话，那么被分出来的两半边A1, A2（都是新集合，为了简单起见，都包含L上的那段公共边界好了）都是凸集。

这是因为，对于A1中的任何点，B, C，如果直线段BC上有一点D在A1之外的话，那么，D必然在A2内（因为 A 本身是凸集）。可是B在A1内，D在A2内，L是把它们分开的直线，所以BD必然和L有交点E,同理CD和 L也一定有交点 F。D在线段 BC内，所以 E和 F必然不同， BC和 L有了两个不同的交点，这是不可能的。（另外要稍微考虑一下边界L上的点，这个情形是简单的）。于是引理证完了。

现在我们证明圆周上n个不同的点可以至少组成一个凸n边形的n个顶点。（存在性）

具体点说，我们从某一点A1开始，顺时针依次标定相邻的点为A2,A3...An. 那么多边形A1A2...An是凸的。

为啥呢？我们看弦A1A2, 它把圆切成了两半，一半含有其他的“A"点们，另一半则没有（因为A1,A2相邻啊。。）。根据宪法第6条，圆是凸集，再根据引理，这两片被切下来的西瓜也都分别成了凸集。当然，其中那个含有其他“A"大爷们的那个也是啦，我们称之为B1好了。这样如法切割，西瓜片B2,...Bn什么的也都是凸集，可是我们如果看看他们的交集：交（B1, B2, ... , Bn) ----这不就是多边形A1A2...An吗？宪法第4条明文规定了，这个集合也享受凸集待遇。

就这么混来个本科文凭，找到个工作，下面我们来独霸一方不许公司hire别人就好办了。。。（唯一性）

咋就容易呢？就凭偶是个白痴吗？不，是草包？哦。。不是，不是，我是说，凸包。

其实，偶想说的是，任何一个以 A1，A2...An为顶点的凸多边形都是是点集A={A1,A2,..,An}的草包。。又错了。。凸包。

比方说F是一个这样的凸多边形，我们要证明，任何一个包含A的凸集C，都包含F.

我们这么来看：F的任何一条边 AiAj，（i, j 不必相邻）因为Ai, Aj 属于A, 于是也就属于 C，于是整条线段AiAj也都属于C. 好了，现在F的整个边界全在C内了。对于F内部任何一点R, 过R的直线L至少和F的边界有两个交点（F有界，封闭），可是这两个交点都在C内，于是整个交点内的直线段也都在C内，当然也包括R 了。于是F在C内。

于是F是草包，而且宪法第5条还规定了这世界上只有偶这一个草包。。。。。

野菜花 · 发表于 2008-3-5 22:58:19

一付“玩世不恭” 的样子(绝无贬意，只是找不到恰当的词) ，没想到做起学问来还是挺认真的。

www.ddhw.com

我用的凸多边形的定义是：任何对角线，全部点都在里面。

www.ddhw.com

谢谢你，还借此机会给我们上了一堂清晰而风趣的有关凸集的扫盲课。你当老师的话一定是一流的。

野菜花 · 发表于 2008-3-5 23:00:03

这样的桂冠可不能随便发送啊

idiot94 · 发表于 2008-3-6 05:20:31

where where no guest gas no guest gas ...

孜孜不倦@. · 发表于 2008-3-6 06:06:09

I'ma so sry

www.ddhw.org---

		自动登录	找回密码
密码			立即注册

动态微博

问双色多边形比无色多边形多多少？

回复：问双色多边形比无色多边形多多少？

呵呵，偶傻傻的忽然有点不明白，圆周上比如说拿5个点出来，为啥

[:-Q] 名师出高徒

看看，水平高的人喜欢装傻，可是随便问个问题就把我们难住了！[:((]

看到几何头就一片空白。。。[:-K][:-K]

高什么高？！看了您的跟贴，偶才傻傻的发现，其实连有一个

这样可以吗？怎么好像没证一样。[:%]

你的钻研精神就和你的名字一样，令人佩服！[:-Q][:B][:)]

被美女称赞，偶脸都红咯[:))]

菜花MM的论述

精妙的证明！[@};-][@};-][@};-] 哇，你看起来整天开开玩笑，

这样的桂冠可不能随便发送啊[;)]

where where no guest gas no guest gas ...

I'ma so sry [:-D]