把三文大哥“短信贺年”题中的四改成五，三改成四，即“如今时兴短信贺年。某公司有 n 位雇员（n > 5），已知任意五名雇员中都有一人与其余的四人交换过短信贺年。那么问：是否任意五名雇员中必有一人与其余所有的 n-1 人都交换过短信贺年?”
把三文大哥“短信贺年”题中的四改成五，三改成四，即“如今时兴短信贺年。某公司有 n 位雇员（n > 5），已知任意五名雇员中都有一人与其余的四人交换过短信贺年。那么问：是否任意五名雇员中必有一人与其余所有的 n-1 人都交换过短信贺年?”
Gut's told me the answer is "Yes“。 本贴由[salmonfish]最后编辑于：2009-2-7 21:48:48 |
答Yes，要证明；答No，要举反例。  |
试了一下。把“短信贺年”题中的四改成六，三改成五好像都能证。但是，把“短信贺年”题中的四改成五，三改成四， 原来的思路就行不通了。不容易。要找新思路。
本贴由[salmonfish]最后编辑于：2009-2-8 0:8:21 |
加油啊！ |
将这n（> = 5）个雇员用n个点来表示。两个雇员之间有短信贺年则规定这两个点相连，否则为不相连。已知任意五个点中总有一个点与其余四点相连。欲证明：在任意五个点中，有一个点与其余n-1个点都相连。
用反证法。 设结论不成立。从这n个点中任取五个点 （X1，X2，X3，X4，X5），其中每个Xi (1=< i =<5) 都有与其不相连的点。设x1, x2, x3, x4, x5分别为与X1，X2，X3，X4, X5不相连的点。
根据已知条件, 五个点 （X1，X2，X3，X4，X5）中有一个点, 不妨设其为 X1, 与其余四个点X2，X3，X4，X5，均相连。那么，与X1 不相连的x1≠ X2, x1≠ X3, x1≠ X4，x1≠ X5。
所以, 五个点 （x1, X1， X2，x3, X3）中只有X2与其余四个点 （包括X1，X3）均相连.
五个点 （x1, X1，x2, X2，X3）中只有X3与其余四个点 （包括X1，X2）均相连。 。。。
同理推演可得：五个点 （X1，X2，X3，X4，X5）中，每个点都与其余四点相连。
又因为，（X1，X2，X3，X4，X5）为 n 中任意所取得五点，在假设结论不成立的前提下，由所给条件得到的上述推论应具普遍性。
显然，这与 n 中五点 （x1, X1，X2，X3，X4）相矛盾。
故，结论成立。
--------------------------------------------- 附：“短性贺年（1）”的证明。 用反证法试一试。 将这n（> = 4）个雇员用n个点来表示。两个雇员之间有短信贺年则规定这两个点相连，否则为不相连。已知任意四个点中总有一个点与其余三点相连。欲证明：在任意四个点中，有一个点与其余n-1个点都相连。
设结论不成立。从这n个点中任取四个点 （X1，X2，X3，X4），其中每个Xi (1=< i =<4) 都有一个与其不相连的点。设x1, x2, x3, x4, 分别为与X1，X2，X3，X4不相连的点。
根据已知条件, 四个点 （X1，X2，X3，X4）中有一个点, 不妨设其为 X1, 与其余三个点X2，X3，X4，均相连。那么，与X1 不相连的x1≠ X2, x1≠ X3, x1≠ X4。
已知，x1 与 X1，x2 与X2 均不相连。那么，x1=x2. 否则，（x1, X1，x2, X2）中没有一个点与其余三个点都相连，与条件不相符。
同理可证：x1=x2=x3. 至此，四个点（x1=x2=x3，X1，X2，X3）中没有一个点与其他三个点相连，与已知条件相违。
所以，结论成立。在任意四点中必有一个点与其余n-1个点都相连。 本贴由[salmonfish]最后编辑于：2009-2-8 14:50:11 |
大哥再想想  |
Is the last part too hurry? (I guess so).
同理推演可得：五个点 （X1，X2，X3，X4，X5）中，每个点都与其余四点相连。 又因为，（X1，X2，X3，X4，X5）为 n 中任意所取得五点，在假设结论不成立的前提下，由所给条件得到的上述推论应具普遍性。 显然，这与 n 中五点 （x1, X1，X2，X3，X4）相矛盾。 |
用反证法。 设结论不成立。从这n个点中任取五个点 （X1，X2，X3，X4，X5），其中每个Xi (1=< i =<5) 都有与其不相连的点。设x1, x2, x3, x4, x5分别为与X1，X2，X3，X4, X5不相连的点。
根据已知条件, 五个点 （X1，X2，X3，X4，X5）中有一个点, 不妨设其为 X1, 与其余四个点X2，X3，X4，X5，均相连。那么，与X1 不相连的x1≠ X2, x1≠ X3, x1≠ X4，x1≠ X5。
又，五个点 （x1, X2，X3，X4，X5）中有一个点, 不妨设其为 X2, 与其余四个点x1，X3，X4，X5，均相连。那么，与X2 不相连的x2≠ x1, x2≠ X3, x2≠ X4，x2≠ X5。
变化下标，重复上述步骤可证：xi, Xi (1=< i =<5) 不重复，不重叠。
这样就有, 五个点 （x1, X1， X2，x3, X3）中只有X2与其余四个点 （包括X1，X3）均相连.
五个点 （x1, X1，x2, X2，X3）中只有X3与其余四个点 （包括X1，X2）均相连。 。。。
同理推演可得：（n 中）任意五个点 （X1，X2，X3，X4，X5）中，每个点都必与其余四点相连。
显然，这与 n 中任意五点 （x1, X1，X2，X3，X4）相矛盾。
故，结论成立。
|
|
三文大哥的“证明”有漏洞啊 。拿以色列国旗中的六角星连上六边作为反例，对照着查查，看问题出在哪儿。 |
Leaving for a long trip. I'll think about it when I feel bored on the way. 本贴由[salmonfish]最后编辑于：2009-2-12 11:3:30 |
| 欢迎光临 珍珠湾ART (http://art.zhenzhubay.com/) | Powered by Discuz! X3 |
