Question

已知六个点,每三个点不在一条直线上,从这些点的15条线段中选出若干条,使得原来的点中任意三

已知六个点,每三个点不在一条直线上,从这些点的15条线段中选出若干条,使得原来的点中任意三点没有连成一个三角形，问最多可以选出多少条线段能满足这一条件？

Answer 1

最多可取9条.
如A,B,C,D,E,F六点，连AB,BC,CD,DE,EF,FA,AD,BE,CF，9条线段，原来点中任意3点未成三角形.

任意连接这些点的10条线段，必能构成三角形，证明如下：
如果每个点都只连接了不超过3条线段，那么，总共连接的线段数不超过3*6/2=9，既然现在连接了10条线段，可见至少有一个点，连接了4条或更多条线段。
设AB,AC,AD,AE已经连接，BC,BD,BE,CD,CE,DE这六条线段如果都不连，总共连接的线段数不超过15-6/2=9，
所以，这六条线段中至少连接了一条，比方说连接了BC，
那么，连接的线段中有三角形ABC。

Answer 2

9条。

首先，存在这样的方式：
周围选取一圈（6条），再选三条隔两个点的对角线
唔……
这样说吧，顺时针编号为123456，选取12，23，34，45，56，61和14，25，36不构成任何三角形。

然后说明对10条及以上，一定会出现三角形：
10条线，每条线两个端点，共使用20次端点。
20÷6=3……2
每个点最多连接五条线段
因此下述两种情况必居其一：
1。至少有一个点连接5条线段
2。至少有2个点连接4条线段

对情况1。设此点为A，A和其他五个点都连有线段，任取这五条线段外的一条线段，该线段的两端点都和A连接。这三点连成三角形。
对情况2。设为A,B。则A，B在除了线段AB之外还各自连了3条线。除A，B外还有4个点。因此至少有一个点和A，B都连接。这三个点连成三角形。

因此十条线及以上一定会出现三角形