6个点,每3点不在一条直线上,从连接这些点的15条线段中选若干,使原来点中任意3点未成三角形,最多可取?请附上说明,

Question

6个点,每3点不在一条直线上,从连接这些点的15条线段中选若干,使原来点中任意3点未成三角形,最多可取?
请附上说明,

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.