一个研究生班里有17人，

野菜花 · 发表于 2006-1-6 14:08:57

一个研究生班里有

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

sean9991 · 发表于 2006-1-6 19:02:34

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.

野菜花 · 发表于 2006-1-7 02:53:10

Excellent!

Archi · 发表于 2006-1-7 09:25:36

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.

野菜花 · 发表于 2006-1-7 14:08:54

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.

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?

Archi · 发表于 2006-1-9 05:54:31

You're right, I misread the question.

		自动登录	找回密码
密码			立即注册

动态微博

一个研究生班里有17人，

回复：一个研究生班里有17人，

Excellent![@};-][@};-]

Another solution

Very creative thinking, but

You're right, I misread the question. [:>]