短信贺年。

salmonfish · 发表于 2009-1-31 19:35:30

如今时兴短信贺年。某公司有 n 位雇员，已知任意四名雇员中都有一人与其余的三人交换过短信贺年。那么问：是否任意四名雇员中必有一人与其余的

n-1 人交换过短信贺年?

冷眼看戏的Lili · 发表于 2009-2-7 11:58:39

不高呀，见下面。

冷眼看戏的Lili · 发表于 2009-2-7 11:37:19

为了叙述方便，把“雇员”称作“点”，把“交换过短信”称作“连通”.

n=4 时不待证。

设 n>4。从n点中任取四点，分别记为１、２、３、４。按题设，其中必有一点与其他三点连通。不妨设此点为１。从这四点外任取一点，记为５。现需证明这四点中必有一点与其他三点以及５连通。若１与５连通，则１即是。否则，考虑１、２、３、５四点，按题设其中必有一点与其他三点连通。这个点不能是１或５，必是２、３中之一，不妨设是２。再考虑１、２、４、５四点，按题设其中必有一点与其他三点连通。同样，这个点不能是１或５，必是２、４中之一。这说明２、４连通。于是，２与１、３、４、５都连通。www.ddhw.com

俺以为这就证完了，省了后面一步。其实这时只证明了“四点外的任何一点都与四点中的某一点连通”，还没有证明“四点中的某一点与四点外的每一点都连通”（意思是说，还没有证明这“四点中的某一点”对于“四点外的所有点”是公共的）。

好啦，下面来补上这一步。www.ddhw.com

把四点外的所有点都按跟哪个点连通表上类号１、２、３、４（它们可有重叠部分，即某些点可能跟１、２、３、４中不止一个点连通）。现来证明这四类点都跟１、２、３、４四点中的某一点（为四类共用）连通，也就是说，这四类都被其中最大的一个类覆盖。实事上，任取两类，不妨设１、２两类，用反证法可以证明其中一类覆盖另一类：若不，则存在至少一１类点不在２类中，也存在至少一２类点不在１类中，分别记这两点为６和７。考虑１、２、６、７四点，由题设知必有一点与其他三点连通。若此点是１或７，则与７不在１类中矛盾；若此点是２或６，则与６不在２类中矛盾。证毕。（可能不用再去问俺老师啦）

冷眼看戏的Lili · 发表于 2009-2-7 08:07:46

不好意思，俺问老师时把题意说差了一点，俺又写漏了一些。俺整理整理，下周再问问老师。www.ddhw.com

salmonfish · 发表于 2009-2-7 07:12:05

高手！

冷眼看戏的Lili · 发表于 2009-2-7 06:55:23

Yes.

俺一直觉得答案是肯定的（举不出反例啊），但难以证明。今天问俺老师，从老师那里拿来了证明（为了叙述方便，把“雇员”称作“点”，把“交换过短信”称作“连通”）：

n=4 时不待证。

设 n>4。从n点中任取四点，分别记为１、２、３、４。按题设，其中必有一点与其他三点连通。不妨设此点为１。从这四点外任取一点，记为５。现需证明这四点中必有一点与其他三点以及５连通。若１与５连通，则１即是。否则，考虑１、２、３、５四点，按题设其中必有一点与其他三点连通。这个点不能是１或５，必是２、３中之一，不妨设是２。再考虑１、２、４、５四点，按题设其中必有一点与其他三点连通。同样，这个点不能是１或５，必是２、４中之一。这说明２、４连通。于是，２与１、３、４、５都连通。证毕。

冷眼看戏的Lili · 发表于 2009-2-5 09:18:03

三文大哥智商极高，也投俺老师门下如何？

salmonfish · 发表于 2009-2-5 09:07:22

谢谢，学到东西了。

salmonfish · 发表于 2009-2-5 09:06:21

那就只有等谁来证明“yes" 了。

冷眼看戏的Lili · 发表于 2009-2-5 09:02:10

"反例说明：“yes"."?????

对用universal quantifier表述的命题（原命题）的否定（No）陈述，用反例是不足以否定它的，也就是说，不足以就此肯定原命题的。俺老师强调过。

salmonfish · 发表于 2009-2-5 08:48:06

“那么问：是否任意四名雇员中必有一人与其余的n-1 人交换过短信贺年?“

LS的答案是“NO" （=否）. 反例说明：“yes".

本贴由[salmonfish]最后编辑于：2009-2-5 0:51:10

冷眼看戏的Lili · 发表于 2009-2-5 08:41:54

那您这例“反”在什么地方啊

salmonfish · 发表于 2009-2-5 08:40:43

“任意四人”包括（A, B, C, D) 这四人。

冷眼看戏的Lili · 发表于 2009-2-5 08:33:49

任意四名雇员

那您这例“反”在什么地方啊?

本贴由[冷眼看戏的Lili]最后编辑于：2009-2-5 0:41:0

salmonfish · 发表于 2009-2-5 08:26:42

C （或D）也是四人之一。且满足：四名雇员中必有一人与其余的 n-1人交换过短信贺年

（说明：n个雇员里只有A 和 B 没有相互交换短信，但与其他人有短信）

本贴由[salmonfish]最后编辑于：2009-2-5 0:31:8

冷眼看戏的Lili · 发表于 2009-2-5 08:21:36

您的例子不能构成反例。

“A, B没有相互交换短信”并没有否定 “任意四名雇员中必有一人与其余的 n-1人交换过短信贺年”啊。

salmonfish · 发表于 2009-2-5 08:05:34

从n 个雇员里选四人(A, B, C, D)，其中恰好有两个人A, B没有相互交换短信，但与另两人C, D交换了短信。而C, or D 分别同 n-1 （包括A, B, D or C) 人交换了短信. C 和 D 都符合条件“已知任意四名雇员中都有一人与其余的三人交换过短信贺年",

本贴由[salmonfish]最后编辑于：2009-2-5 0:12:6

冷眼看戏的Lili · 发表于 2009-2-5 07:18:50

说No，不需要证明，只需给出反例。

salmonfish · 发表于 2009-2-5 05:18:34

能否劳驾证明一下你的结论呢？

yma16 · 发表于 2009-2-4 21:48:46

Thx. The answer is no.

salmonfish · 发表于 2009-2-4 21:13:08

Exchange betwee A and B: A and B mutually sent and received message to/from each other.

yma16 · 发表于 2009-2-4 20:01:32

does 交换 means send AND receive?

		自动登录	找回密码
密码			立即注册

动态微博

短信贺年。

回复：高手！[:-Q][:-Q][:-Q]

回复：Yes.

回复：Yes.

高手！[:-Q][:-Q][:-Q]

Yes.

别客气

谢谢，学到东西了。[:-Q][:-Q]

那就只有等谁来证明“yes" 了。

回复：是对LS的答案的反例。

是对LS的答案的反例。

回复：“任意四人”包括（A, B, C, D) 这四人。

“任意四人”包括（A, B, C, D) 这四人。

回复：???

???

构不成反例

谢谢，找个反例。[;)][;)]

回复：能否劳驾证明一下你的结论呢？

能否劳驾证明一下你的结论呢？

回复：回复：does 交换 means send AND receive?

回复：does 交换 means send AND receive?

does 交换 means send AND receive?

动态微博

短信贺年。

回复：高手！[:-Q][:-Q][:-Q]

回复：Yes.

回复：Yes.

高手！[:-Q][:-Q][:-Q]

Yes.

别客气

谢谢，学到东西了。[:-Q][:-Q]

那就只有等谁来证明“yes" 了。

回复：是对LS的答案的反例。

是对LS的答案的反例。

回复：“任意四人”包括 （A, B, C, D) 这四人。

“任意四人”包括 （A, B, C, D) 这四人。

回复：???

???

构不成反例

谢谢，找个反例。[;)][;)]

回复：能否劳驾证明一下你的结论呢？

能否劳驾证明一下你的结论呢？

回复：回复：does 交换 means send AND receive?

回复：does 交换 means send AND receive?

does 交换 means send AND receive?

回复：“任意四人”包括（A, B, C, D) 这四人。

“任意四人”包括（A, B, C, D) 这四人。