试证

来源: 万斤油 于 2023-09-01 05:35:45 [] [博客] [旧帖] [给我悄悄话] 阅读数 : (1038 bytes)
本帖于 2023-09-01 17:41:45 时间, 由普通用户 万斤油 编辑
回答: 发一个烧脑题 由 wxcfan123 于 2023-08-27 23:58:32

把9个专家化为平面上的9个点，且无3点共线，如果某两位专家可以用同一语言交流（多于一种语言的只算其中一种），就在这两点间连一条某一颜色的线段（代表某一语言）。反证法：显然从一点出发最多连3条不同颜色的线，否则至少有两条线颜色相同，这两条颜色相同的线所在的3个点所代表的3个专家可以说同一种语言。所以9个点最多连[9*3/2]=13根线。如果其中一点A，可连3条不同颜色的线段到B,C,D, 又B,C,D之间又至少存在一条线，其与A出发的3条线段颜色各不相同，否则可以形成3条边颜色相同的三角形（题被证）。所以ABCD4点之间至少存在4条不同颜色的线段。A和剩下的5个没有连线，但和其中任何两点所形成的三角形中至少有两点相连，即A的对边，共有C(5,2)=10条，即9个点至少有10+4=14条线段相连， 矛盾。如果A只能连2条，1条，0条，那么A和剩下的点能得到更多的连线。

所有跟帖： 

• 高！ -wxcfan123- ♂ 给 wxcfan123 发送悄悄话 (0 bytes) () 09/01/2023 postreply 12:02:19

请您先登陆，再发跟帖！