“短信贺年”(2)

冷眼看戏的Lili

把三文大哥“短信贺年”题中的四改成五，三改成四，即“如今时兴短信贺年。某公司有 n 位雇员（n > 5），已知任意五名雇员中都有一人与其余的四人交换过短信贺年。那么问：是否任意五名雇员中必有一人与其余所有的 n-1 人都交换过短信贺年?”

www.ddhw.com

 

salmonfish

Gut's told me the answer is "Yes“。  www.ddhw.com     本贴由[salmonfish]最后编辑于：2009-2-7 21:48:48

冷眼看戏的Lili

答Yes，要证明；答No，要举反例。 www.ddhw.com

salmonfish

试了一下。把“短信贺年”题中的四改成六，三改成五好像都能证。但是，把“短信贺年”题中的四改成五，三改成四， 原来的思路就行不通了。不容易。要找新思路。 error: In hunch diagram, n should be n-4.  www.ddhw.com     本贴由[salmonfish]最后编辑于：2009-2-8 0:8:21

冷眼看戏的Lili

加油啊！ www.ddhw.com

salmonfish

www.ddhw.com    www.ddhw.com 将这n（> = 5）个雇员用n个点来表示。两个雇员之间有短信贺年则规定这两个点相连，否则为不相连。已知任意五个点中总有一个点与其余四点相连。欲证明：在任意五个点中，有一个点与其余n-1个点都相连。  www.ddhw.com 用反证法。www.ddhw.com 设结论不成立。从这n个点中任取五个点 （X1，X2，X3，X4，X5），其中每个Xi (1=< i =<5) 都有与其不相连的点。设x1, x2, x3, x4, x5分别为与X1，X2，X3，X4, X5不相连的点。  www.ddhw.com 根据已知条件,  五个点 （X1，X2，X3，X4，X5）中有一个点, 不妨设其为 X1, 与其余四个点X2，X3，X4，X5，均相连。那么，与X1 不相连的x1≠ X2, x1≠ X3, x1≠ X4，x1≠ X5。  www.ddhw.com 所以, 五个点 （x1, X1， X2，x3, X3）中只有X2与其余四个点 （包括X1，X3）均相连.  www.ddhw.com 五个点 （x1, X1，x2, X2，X3）中只有X3与其余四个点 （包括X1，X2）均相连。 。。。www.ddhw.com  www.ddhw.com 同理推演可得：五个点 （X1，X2，X3，X4，X5）中，每个点都与其余四点相连。www.ddhw.com  www.ddhw.com 又因为，（X1，X2，X3，X4，X5）为 n 中任意所取得五点，在假设结论不成立的前提下，由所给条件得到的上述推论应具普遍性。www.ddhw.com  www.ddhw.com 显然，这与 n 中五点 （x1, X1，X2，X3，X4）相矛盾。www.ddhw.com   故，结论成立。  www.ddhw.com --------------------------------------------- 附：“短性贺年（1）”的证明。 用反证法试一试。www.ddhw.com 将这n（> = 4）个雇员用n个点来表示。两个雇员之间有短信贺年则规定这两个点相连，否则为不相连。已知任意四个点中总有一个点与其余三点相连。欲证明：在任意四个点中，有一个点与其余n-1个点都相连。www.ddhw.com  www.ddhw.com 设结论不成立。从这n个点中任取四个点 （X1，X2，X3，X4），其中每个Xi (1=< i =<4) 都有一个与其不相连的点。设x1, x2, x3, x4, 分别为与X1，X2，X3，X4不相连的点。  www.ddhw.com 根据已知条件,  四个点 （X1，X2，X3，X4）中有一个点, 不妨设其为 X1, 与其余三个点X2，X3，X4，均相连。那么，与X1 不相连的x1≠ X2, x1≠ X3, x1≠ X4。www.ddhw.com  www.ddhw.com 已知，x1 与 X1，x2 与X2 均不相连。那么，x1=x2. 否则，（x1, X1，x2, X2）中没有一个点与其余三个点都相连，与条件不相符。   同理可证：x1=x2=x3. www.ddhw.com 至此，四个点（x1=x2=x3，X1，X2，X3）中没有一个点与其他三个点相连，与已知条件相违。  www.ddhw.com 所以，结论成立。在任意四点中必有一个点与其余n-1个点都相连。www.ddhw.com     本贴由[salmonfish]最后编辑于：2009-2-8 14:50:11

冷眼看戏的Lili

大哥再想想 www.ddhw.com

salmonfish

Is the last part too hurry? (I guess so).    www.ddhw.com 同理推演可得：五个点 （X1，X2，X3，X4，X5）中，每个点都与其余四点相连。www.ddhw.com 又因为，（X1，X2，X3，X4，X5）为 n 中任意所取得五点，在假设结论不成立的前提下，由所给条件得到的上述推论应具普遍性。www.ddhw.com 显然，这与 n 中五点 （x1, X1，X2，X3，X4）相矛盾。 www.ddhw.com

salmonfish

用反证法。 设结论不成立。从这n个点中任取五个点 （X1，X2，X3，X4，X5），其中每个Xi (1=< i =<5) 都有与其不相连的点。设x1, x2, x3, x4, x5分别为与X1，X2，X3，X4, X5不相连的点。  www.ddhw.com 根据已知条件,  五个点 （X1，X2，X3，X4，X5）中有一个点, 不妨设其为 X1, 与其余四个点X2，X3，X4，X5，均相连。那么，与X1 不相连的x1≠ X2, x1≠ X3, x1≠ X4，x1≠ X5。  www.ddhw.com 又，五个点 （x1, X2，X3，X4，X5）中有一个点, 不妨设其为 X2, 与其余四个点x1，X3，X4，X5，均相连。那么，与X2 不相连的x2≠ x1, x2≠ X3, x2≠ X4，x2≠ X5。  www.ddhw.com 变化下标，重复上述步骤可证：xi, Xi  (1=< i =<5) 不重复，不重叠。  www.ddhw.com 这样就有, 五个点 （x1, X1， X2，x3, X3）中只有X2与其余四个点 （包括X1，X3）均相连.www.ddhw.com  www.ddhw.com 五个点 （x1, X1，x2, X2，X3）中只有X3与其余四个点 （包括X1，X2）均相连。www.ddhw.com 。。。  www.ddhw.com 同理推演可得：（n 中）任意五个点 （X1，X2，X3，X4，X5）中，每个点都必与其余四点相连。  www.ddhw.com 显然，这与 n 中任意五点 （x1, X1，X2，X3，X4）相矛盾。  www.ddhw.com 故，结论成立。

冷眼看戏的Lili

www.ddhw.com

冷眼看戏的Lili

三文大哥的“证明”有漏洞啊。拿以色列国旗中的六角星连上六边作为反例，对照着查查，看问题出在哪儿。 www.ddhw.com

salmonfish

Leaving for a long trip. I'll think about it when I feel bored on the way. www.ddhw.com     本贴由[salmonfish]最后编辑于：2009-2-12 11:3:30