作者k6416337 (とある煞氣の光希)
看板Math
標題Re: [離散]有關幾題鴿籠原理....
時間Wed Mar 24 22:08:09 2010
※ 引述《SUPERTR (日光月影)》之銘言:
: 1.There are 100 people at a party. Each person has an even number (possibly
: zero) of acquaintances. Prove that there are three people at the party with
: the sasne number of acquaintances.
不知道可否這樣解
由結果可知,要利用鴿籠原理,就是假設鴿子為這100人,籠子為熟人的數量
因為是偶數,一個人認識最多可以認識98人,最少0人,所以籠子集合{0,2,4,...,98}共有
50個數字讓一個人挑
每個人都必須裝進這些籠子裡,但是會遇到剛好每個數字都各有兩人
如果沒有"A認識B等同於B認識A"的前提下,結果是做不出來的
假設恰好有2人認識98人,我們假設甲乙,也恰好有2人沒認識半個人,我們假設丙丁
不過這是不可能發生的
這是因為丙丁沒認識半個人,所以甲乙只有100-2=98個人會有認識的網路
扣除自己會有最多97個人可以認識,所以甲乙兩人最多只能認識96人
因此,不可能恰好2人認識98人"且"恰好2人認識0人;也就是說"不是"最多只會有1人有98
個熟人"就是"最多1人沒認識半個人,換句話說就是0跟98這兩個籠子不會同時關住2隻鴿子
因此會有3人剛好同時有相同的熟人數量
: 2.Prove that of any five points chosen within a square of side length 2, there
: are two whose distance apart is at most 2^0.5.
: 3.Prove that in a group of n>1 people there are two who have the same number
: of acquaiotances in the group. (It is assumed that no one is acquainted with
: him or herself.)
: 我想了很久,但還是沒想出解決的辦法
: 如果可以的話,能不能詳述一下作法
: 請大家多多幫忙
: 謝謝了
--
律:知道嗎?聽說我們的歌被海外的電視台所錄用耶!看來我們離武道館不遠了
唯:真的嗎?那真的是太好了,我一直夢想能在武道館彈著吉太,好高興
釉:小唯能高興真的是太好了,呵呵~
澪:拜託!那個明明是盜用不是錄用,你們怎麼還這麼高興?
律、唯、釉:啊?什麼?
輕音部
澪:絕望啦!我對盜用錄用分不清楚的輕音部社員們絕望啦! 邁向武道館之路
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.113.178.13
※ 編輯: k6416337 來自: 140.113.178.13 (03/24 22:09)
推 a88241050 :為啥會有移位碼-.-+ 03/24 22:09
→ k6416337 :我放錯簽名檔 03/24 22:10
推 SUPERTR :我了解你的意思了,這樣看我就懂了,謝謝你了。 03/24 22:18