作者cfbbq (CF)
看板Inference
标题Re: 相识
时间Sun May 24 13:41:58 2009
※ 引述《Hseuler (蓝色狸猫)》之铭言：
: 在一个12个人组成的群体中
: 任意9个人中都有5个人，他们两两相识
: 请问
: 从这12个人中，是否可以选出6个人，他们俩两相识?
: 1)一定可以 2)不一定 3)绝对不可能
: 谢谢
我觉得是(1)耶，以下是我的想法。
我先证"12人中，任意9人都有5人两两相识 => 12人中，至少8人两两相识"
pf:
利用反证法，假设 "12人中，最多7人两两相识"
此时，这12人中就被分成两群 "两两相识(小於等於7人)"、"其他(大於等於5人)"
我们从 "两两相识" 中挑x人(x<=7)，与 "其他" 中挑y人(y>=5)，总共9人(x+y=9)，
x+y=9 , x<=7 , y>=5 得 x<=4
9人中最多4人两两相识？与已知矛盾，所以 "12人中，至少8人两两相识"
因为 "12人中，至少8人两两相识" ， "所以12人中一定可以选出6个人两两相识" 。
不知道这样子有没有问题，有问题的话，帮我纠正，谢谢。
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.117.192.182
1F：推 hcldesmond:其他的也可以两两相识，不过我和你的想法大致一样 05/24 14:40
2F：推 dsmwang:有矛盾。八人两两相识是符合题目的情况，但你尚未证出这是 05/24 19:19
3F：→ dsmwang:唯一的情况。 05/24 19:19
4F：→ dsmwang:任意九人中有五人两两相识跟十二人里至少要有八人两两相识 05/24 19:19
5F：→ dsmwang:并不等价。因为也许还有其他认识的情况是符合题意但是并非 05/24 19:20
6F：→ dsmwang:至少八人两两相识。 05/24 19:20
7F：→ dsmwang:抱歉我用词错误，并非矛盾，应该说是"不完整"。 05/24 19:21
8F：→ cfbbq:我上面那个写法，没有说两边等价说，只是左边推到右边。 05/24 19:33
9F：→ cfbbq:我修改一下第二行好了~ 05/24 19:35
※ 编辑: cfbbq 来自: 140.117.192.182 (05/24 19:36)
10F：推 hcldesmond:想想看两组6个人两两相识的情形... 05/24 19:39
11F：→ cfbbq:嗯嗯~收到~谢谢罗。 05/24 19:48
12F：推 dsmwang:你没懂我的意思，我的意思是题目限定的范围比你证的范围还 05/24 21:12
13F：→ dsmwang:要大，你目前证的结果仍然只在答案二：有可能可以。但你尚 05/24 21:13
14F：→ dsmwang:未解释到为何"一定"可以。你假设的只是其中一种符合题目的 05/24 21:13
15F：→ dsmwang:情况，但你若要用这个证明完成这个题目，还需要证明只有你 05/24 21:14
16F：→ dsmwang:限定的范围就能代表题目。 05/24 21:14
17F：→ dsmwang:好比说，你说xy各挑几个人，但是我随便都可以编出有些情况 05/24 21:16
18F：→ dsmwang:x小於四时仍有五人两两相识。因为y只要不认识x的每个人就 05/24 21:17
19F：→ dsmwang:会违反你的假设。所以y认识三四个x显然符合题目，但是却不 05/24 21:17
20F：→ dsmwang:在你的证明之内。 05/24 21:17
21F：→ cfbbq:＠＠，我懂了，h大有点到我了。3q 05/24 22:43