Re: 相識

[cfbbq (CF)]

※ 引述《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
推 hcldesmond:其他的也可以兩兩相識，不過我和你的想法大致一樣
推 dsmwang:有矛盾。八人兩兩相識是符合題目的情況，但你尚未證出這是
→ dsmwang:唯一的情況。
→ dsmwang:任意九人中有五人兩兩相識跟十二人裡至少要有八人兩兩相識
→ dsmwang:並不等價。因為也許還有其他認識的情況是符合題意但是並非
→ dsmwang:至少八人兩兩相識。
→ dsmwang:抱歉我用詞錯誤，並非矛盾，應該說是"不完整"。
→ cfbbq:我上面那個寫法，沒有說兩邊等價說，只是左邊推到右邊。
→ cfbbq:我修改一下第二行好了~
※ 編輯: cfbbq           來自: 140.117.192.182      (05/24 19:36)
推 hcldesmond:想想看兩組6個人兩兩相識的情形...
→ cfbbq:嗯嗯~收到~謝謝囉。
推 dsmwang:你沒懂我的意思，我的意思是題目限定的範圍比你證的範圍還
→ dsmwang:要大，你目前證的結果仍然只在答案二：有可能可以。但你尚
→ dsmwang:未解釋到為何"一定"可以。你假設的只是其中一種符合題目的
→ dsmwang:情況，但你若要用這個證明完成這個題目，還需要證明只有你
→ dsmwang:限定的範圍就能代表題目。
→ dsmwang:好比說，你說xy各挑幾個人，但是我隨便都可以編出有些情況
→ dsmwang:x小於四時仍有五人兩兩相識。因為y只要不認識x的每個人就
→ dsmwang:會違反你的假設。所以y認識三四個x顯然符合題目，但是卻不
→ dsmwang:在你的證明之內。
→ cfbbq:＠＠，我懂了，h大有點到我了。3q