一道与生活有关的问题,困扰我很久了——希望学数学的看看

一道与生活有关的问题,困扰我很久了——希望学数学的看看
在一次会议上,任一与会者至少与5人交换过意见.求证:存在六个人v1,v2,……,v6,使得v1与v2,v2与v3,……,v5与v6,且v6与 v1交换过意见.
另外补充一下,这是一道与图论有关的问题.
在《竞赛数学解题研究》中找到的一个结论:每人至少与m(大于2)人交流过意见,则存在k个人,k大于m,v1,v2,……,vk且v1与v2,v2与v3,……,vk与v1交流过意见。
至于k的最小值是多少,k能不能取m+1,
原问题是《竞赛数学教程(第一版)》(2004印刷)中的一道练习题(没有解答)。
51965 1年前 已收到5个回答 举报

leowang945 幼苗

共回答了19个问题采纳率:89.5% 举报

很期待这命题的证明.
如果简化一下,变成任一与会者至少与2人交换过意见.存在v1,v2,v3,使得v1与v2,v2与v3,v3与 v1交换过意见.这个命题就很容易给出反例了.
推广一下,变成任一与会者至少与3人交换过意见.存在v1,v2,v3,v4,使得v1与v2,v2与v3,v3与v4,v4与v1交换过意见.这个命题就也能够给出反例:当8个人时,1与238见面,2与138见面,3与124见面,4与356见面,5与467见面,6与457见面,7与568见面,8与127见面,可以保证不存那样的4个人.
所以果断推测这个命题是错的.
如果有达人能够证明原命题,请一并解释一下为什么这个命题不能够推广.

1年前

8

雕刻时光的左手 幼苗

共回答了2个问题 举报

从题中很容易看出原结论是对的是不是题打错了

1年前

2

乐乐3331 幼苗

共回答了3个问题 举报

六个人为六个顶点,题目转化为,从V1开始经过所有的点,并且只经过一次,这样就可以使用图论理论进行证明

1年前

1

我爱ww 幼苗

共回答了4个问题 举报

对的。6人都最多与5人全交换!K为3,如果K=2那不成立,所以K=m 1是对的!

1年前

1

口怜滴zz 幼苗

共回答了11个问题 举报

由题意知6个人也满足条件,设总人数为6人,那么其中每两个人都必有交流,题目所说的就解决了。其实用图来解释,这个图是一个连通图,任意两个顶点间都有路径,因此正确。

1年前

1
可能相似的问题
Copyright © 2024 YULUCN.COM - 雨露学习互助 - 20 q. 3.098 s. - webmaster@yulucn.com