1452人
每個人至少需認識幾個人
才能保證會有5個人他們彼此都互相認識
答案是1090人
請列算式
謝謝
2005-10-22 07:43:00 · 5 個解答 · 發問者 Anonymous in 科學 ➔ 數學
[證明]
(1)認識1089人不能保證會有5個人他們彼此都互相認識
反例:
將所有人編號1--1452號
分成4組
A:1-363
B:364-726
C:727-1089
D:1090-1452
而A組的人認識BCD組的所有人 但是都不認識A組的其他人
而B組的人認識ACD組的所有人 但是都不認識B組的其他人
而C組的人認識ABD組的所有人 但是都不認識C組的其他人
而D組的人認識ABC組的所有人 但是都不認識D組的其他人
所以每個人都洽好認識1089人
任意選出(x1,x2,x3,x4,x5)5個人
由鴿籠原理知道必定有兩個人同ㄧ組
所以那兩人必定不認識
=>不論怎麼選出的5個人必定互相有不認識的兩個人
=>1089還不能保證會有5個人他們彼此都互相認識
--
(2)證明1090可以
若1號...1452號都認識1090人
任意取2個互相認識的人(A,B)
=>A在1--1452號中除了A,B之外
1450人中A還認識了1089人
B也是在剩下的1450人中還認識了1089人
=>起碼有1089+1089-1450=728人是AB都認識的
把這728人的集合令為S1他們都認識AB
從S1中取ㄧ人C
=>C認識AB=>ABC互相認識
因為C不認識的人1452-1090-1(C本身)=361人
=>S1這個集合中C最多不認識361人
=>C起碼認識S1中的728-361-1(C本身)=366人
定義這366人集合為S2=>S2中的人都認識C
因為S1包含S2
=>S2中的每個人都認識ABC
從S2中選一人D
=>D認識ABC
=>ABCD互相認識
因為D不認識的人1452-1090-1(D本身)=361人
=>S2這個集合中D最多不認識361人
=>D起碼認識S2中的365-361-1(D本身)=3人
從這3人中選一個為E
=>E認識D ,又E屬於S2=>E認識ABC
=>ABCDE互相認識
2005-10-26 00:21:31 補充：
題目是
1452人每個人至少需認識幾個人在
[所有的認識情形下]必定[存在5個人互相認識]
你講的第一個敘述違背了後面那個[]題目只要;存在;而不是任5人都彼此認識
你講的第二個敘述違背了前面那個[]
你只舉了一個認識的情形說認識5人就夠了,但你沒說認識5人的話[所有認識情形都會存在5個人互相認識]
2005-10-26 16:54:21 補充：
這樣子證明還是犯了[所有的認識情形下]
因為不能保證是不是所有認識情形都能這樣分成4組然後恰好每個人都認識3組+1
證明不成立[所有的認識情形下]
只需要舉一個例子
但是證明成立卻需要所有情形都考慮下去
所以我才沒有像那樣子證
2005-10-24 19:07:25 · answer #1 · answered by 依鴻 3 · 0⤊ 0⤋
魔鬼解題解得很好!
但若在證明1後面加上若認識1090人時,則必有2人在同一組裡且彼此認識,且認識其他3組的人,故有5人都彼此認識.這樣是否更簡單?請指正!!
2005-10-26 09:01:10 · answer #2 · answered by fumi 6 · 0⤊ 0⤋
看完魔大大的解題後才知道是怎麼一回事！
題目本身有問題，沒有設限。
若單純以題目而言，應該是所有的人都必須認識，因為「任選五人」都必須認識的話就沒有不認識的空間，一定要全認識才行。另一個是任選一人，此人一定有四個與此人互相認識的話，就將所有人分成五個人一組各組互相認識，則任選一人均有五個人互相認識。但是1452無法整除，所以有兩組是六個人，所以這兩組的每個人是：認識五個人。那答案就是五個人。題目應該是：將1452人分成四組，由這四組人中任選一人，此人一定能在這四組中至少也認識一人，則每個人至少要認識多少人？
2005-10-25 17:32:32 · answer #3 · answered by ? 6 · 0⤊ 0⤋
實在是太難了拉...
2005-10-24 18:51:27 · answer #4 · answered by ? 2 · 0⤊ 0⤋
沒人來解題= =
2005-10-24 18:15:47 · answer #5 · answered by Anonymous · 0⤊ 0⤋