作者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