求证必有一个凸四边形

hujunhua

平面上有5个点，任意3点都不共线。求证：其中必有4个点是一个凸四边形的四顶点。

百度知道的一个问题，那里有2个回复，一个文不对题，一个不够充分但被提问者采纳了。

hujunhua

百度知道还有一处提出此问，回答也不正确，而且也被采纳了。

看起来证明并不困难，毕竟组合很少，穷举也费不了多少事，居然没人搞对。

证明1：记这5点为ABCDE, 考虑这5点的凸包，有3种可能：
          1) 凸包是一个四边形，则可得到3个凸四边形。
          2) 凸包是一个五边形，则可得到5个凸四边形，任取其中4点皆可。
          3) 凸包是一个三角形，不妨设即ABC，那么DE在三角形ABC内，直线DE只与三角形两边相交，
              不交的那条边不妨设即AB，则ABDE是一个凸四边形的四顶点（为什么？）。

wayne

等效一下：
在三角形内选一个点，即可构成一个凹四边形。(充分)
换句更强的话来说，就是凹四边形在结构上等效于三角形及其内部一点构成的集合。(充分必要)

原命题的否命题 等效于在两个共边三角形的图形结构内放置一个点，使得该点同时属于这两个三角形的内部。
而这个是矛盾的。所以命题成立。

mathe

可先证明一个引理，凸图形被直线划分成的俩部分都是凸的

hujunhua

这个引理不錯，正好回答了2楼最后括号中的为什么。

@mathe 貌似手机浏览器可以直接看到白色字吧？

mathe

非常容易忽略掉，很不清楚。不过全选后就可以看清了

fwjmath

这个叫Happy ending problem，Erdos也做过的：http://en.wikipedia.org/wiki/Happy_Ending_problem

可以推广到更多的点，上下界之间差很多，很有发挥空间。

yyy_fcz

取a、b、c三点构成三角形，设d、e在三角形内，因为没有三点共线，所以abc三点中必有两点在线段de的同一侧，且四点中任意三点不共线，则这两点与de构成凸四边形。

hujunhua

找到一个简明的表述。
凸四边形与凹四边形可以用对角线是否相交来区分。相交为凸，不交为凹。
问题等价转化为：直边完全图k5画在一个平面上时必有两非邻边相交。
这当然是正确的。别说是直边k5，就是曲边k5也不可避免两边相交，因为k5不是平面图。
证明很简单：k4将平面划分为4个△，第5点必落于其中一个△内，它与该△外的那个顶点的连线必定与△的某条边相交。