珍珠湾ART

标题: 一个研究生班里有17人， [打印本页]

---

作者: 野 菜 花    时间: 2006-1-6 14:08
标题: 一个研究生班里有17人，

一个研究生班里有

17人，其中每个人都有4个朋友，证明存在两个互相不是朋友的人也没有共同的朋友。

www.ddhw.com

 

---

作者: sean9991    时间: 2006-1-6 19:02
标题: 回复：一个研究生班里有17人，

Let’s prove by contradiction.  www.ddhw.com Suppose the argument is not true, then for any two students, either they are friends or they have a common friend.  Consider any person, say A.  He/she has exactly 4 friends.  Let’s call them B1, B2, B3, and B4.  www.ddhw.com   Now, the remaining 17 – (4 + 1) = 12 students can’t be A’s friend directly, so they have to know A through Bi’s.   www.ddhw.com Since each Bi can have three friends besides A, we are sure that www.ddhw.com Bi and Bj are not friends, for i ≠ j, and i, j in {1, 2, 3, 4}.  Bi and Bj have only one common friend A, for i ≠ j, and i, j in {1, 2, 3, 4}.    Both have to be true in order to get the 12 extra students in.  www.ddhw.com Let Bi’s friends be A, Ci1, Ci2, Ci3, and let Si be the set of {Ci1, Ci2, Ci3}, for i in {1, 2, 3, 4}.  Consider Ci1 and B2’s common friend, he/she has to be someone from S2.  Therefore, any member in S1 will have exactly one friend from each of S2, S3, and S4.  www.ddhw.com  www.ddhw.com Let’s assume C11 and C21 are friend, we claim C12 and C21 can’t be friend.  For otherwise, either C22 or C33 can’t have a common friend with B1 (only one of them can be friend of C13).  Therefore, members in 4 sets of Si’s can be partitioned into 3 equivalent classes of mutual friends.   Just as above, if C11 and C21 are friend, C12 and C21 can’t be friend.  By the argument of equivalent classes above, they have no common friend. www.ddhw.com

---

作者: 野 菜 花    时间: 2006-1-7 02:53
标题: Excellent![@};-][@};-]

  Excellent!

---

作者: Archi    时间: 2006-1-7 09:25
标题: Another solution

Use pigeonhole principle. Represent each person as a point; if two points have friendship, connect them with red line, otherwise blue line. 1) There are totally 17*4/2=34 red lines. 2) There are totally (17 choose 3)=680 distinct triangles possibly formed by 17 points. Each triangle side is at most shared by 15 triangles. Since 34*15 < 680, there are triangles with all blue sides. QED.www.ddhw.com

---

作者: 野 菜 花    时间: 2006-1-7 14:08
标题: Very creative thinking, but

we have to prove that there exists a blue edge AB provided that there is no  point C such that both AC and BC are red.www.ddhw.com   It seems to me that you have proved that there are many blue triangles, you still need disprove that all blue edges are also shared by other triangles with two red edges. Am I right? www.ddhw.com

---

作者: Archi    时间: 2006-1-9 05:54
标题: You're right, I misread the question. [:>]

  You're right, I misread the question.

---

欢迎光临 珍珠湾ART (http://zzwav.com/)

Powered by Discuz! X3