### Author Topic: 每周一题: 政治家 (12/6/04 -- 12/12/04)  (Read 80150 times)

#### wwwfun

• Guest
##### a typo
« Reply #15 on: 十二月 08, 2004, 01:18:01 pm »
In my argument, in th contradition, it should be that 2k+1 > n, not 2k>n.

#### 没头脑

• Newbie
• Posts: 8
##### 每周一题: 政治家 (12/6/04 -- 12/12/04)
« Reply #16 on: 十二月 08, 2004, 04:03:10 pm »

wwwfun的第一部分：

Each pair has one and only one common friend. There are n(n-1)/2 pigeon
holes, and need to fill out by n person. So, a0 must be selected at least
[n/2] times. The first time of selection gives 2 friend to a0. Each following
time gives at least 1 new friend to a0. Now we have k>=[n/2]+1.

#### fzy

• Hero Member
• Posts: 520
##### 每周一题: 政治家 (12/6/04 -- 12/12/04)
« Reply #17 on: 十二月 08, 2004, 04:24:17 pm »
Quote from: 没头脑

Just  a little further:

From this argument, you have already proved that if a person has K friends, any person who is two steps away from him has at least K friends, and at least K - 1 of them are also two steps away from the original person, which means they all have at least K friends. From here you can then show that every person in the whole group is two steps away from one of these people. So every body has K friends and they are all very happy.

From here it is easy to see my other partial results, but they are not useful according to the professor.

I have not thought about the second part, and probably will not. Linear Algebra is my least favorate class in college and Eigenvalues are my least favorate topic in Linear Algebra, which means I do not remember anything about it.

#### wwwfun

• Guest
##### futher explanation
« Reply #18 on: 十二月 08, 2004, 05:38:55 pm »
Once MTL confirm that b0 bring k new members. My proof is done. Here is the explanation of my first part.

Each pair has a common friend. Call it that each pair creates a C_Position. (I call it pigeon hole in my previous post). There are total
n(n-1)/2 pairs, and n members will be selected into these n(n-1)/2 C_Positions. By pigeon hole principle, k must >=[n/2]. It this clear?

Actually, what I really need is that k >= c and any member is not selected yet will bring m>1 new members!!!  That way, say b0 bring b1,
the b1 will bring c1, repeat it again and again, the number of members involved will increase infinitely.

#### wwwfun

• Guest
##### 每周一题: 政治家 (12/6/04 -- 12/12/04)
« Reply #19 on: 十二月 08, 2004, 06:01:29 pm »
OPPs. The statement: "The first time of selection gives 2 friend to a0. Each following time gives at least 1 new friend to a0" (I only think about
(1, 2), 1, 3) ... and did not take care of (2, 3)). is not correct. Need think about it again. But, intuitively, I believe the direction.

#### warren

• Full Member
• Posts: 148
##### 每周一题: 政治家 (12/6/04 -- 12/12/04)
« Reply #20 on: 十二月 08, 2004, 07:03:08 pm »

1. 设朋友最多的人a0有K个朋友. 如果K=2,很容易证明结论成立. 以下设K>=3.如果K不等于N, 则存在一个b0不是a0的朋友.根据MTN的证明,b0有K个朋友. 由于b0是任意的,因此所有不是a0的朋友的人有K个朋友. 在a0的朋友中,b0只有一个朋友,a1. 其他人都不是b0的朋友,因此这些人都有K个朋友. 在a0的朋友中,a1只与一人是朋友,因此在a0的朋友中有人不是a1的朋友.根据同样的理由,a1有K个朋友. 因此所有人都有K个朋友.

2. 如万教授所提示的,作联系矩阵A. 有上述结论,A的每一行有K个1,其它全是0.
A是对称矩阵,主对角元全为0. 易知AA的主对角元全为K,其它元全为1(因为任意两人有一个共同朋友). AA的特征根为一个N+K-1,N-1个K-1. A的特征根应该是一个sqrt(N+K-1),N-1个sqrt(K-1). 但是容易看出K是A的一个特征根. 而A的特征根之和为0(主对角元全为0),因此其它N-1个特征根全是 -K/(N-1). 于是我们得到下列等式:
K^2/(N-1)^2 = K-1,
N+K-1 = K^2.

#### warren

• Full Member
• Posts: 148
##### 每周一题: 政治家 (12/6/04 -- 12/12/04)
« Reply #21 on: 十二月 08, 2004, 07:24:18 pm »

#### wwwfun

• Guest
##### 每周一题: 政治家 (12/6/04 -- 12/12/04)
« Reply #22 on: 十二月 09, 2004, 12:19:29 am »
Hope this time, I am right. Particularly, MTN, could you
check my argument. Thanks in advance.

Start from MTN's argument.
1. Have A = (a0, a1, a2, ..., ak)
2. A form a FAN centered at a0. that means there are k/2 triangle
a0aiaj, each ai (i>0) is in one and only in one triangle.
Generally, very remember c0, who has k friends c1, c2, ...,
ck, also forms a FAN, centered at c0.
2. For any b0 is not in A, we have a new group B=
(b0, ai, b2, ..., bk) such that ai = intersection of A and
B. From construction, each bi is the common friend of b0 and
aj for some j > 1. and (b2, ..., bk) can be 1-1 mapped to
Suppose b0 ai and b2 form a triangle in B.
b2 is the common friend of b0 and aj. Now, b2 has two friends
in A, ai and aj. This is a contradiction. Because b2 is a
member not in A, the k-FAN centered at b2 should have only one
common member with A.

#### 没头脑

• Newbie
• Posts: 8
##### 每周一题: 政治家 (12/6/04 -- 12/12/04)
« Reply #23 on: 十二月 09, 2004, 09:50:33 am »
wwwfun说：

2. For any b0 is not in A, we have a new group B=
(b0, ai, b2, ..., bk) such that ai = intersection of A and
B. From construction, each bi is the common friend of b0 and
aj for some j > 1. and (b2, ..., bk) can be 1-1 mapped to
Suppose b0 ai and b2 form a triangle in B.
b2 is the common friend of b0 and aj. Now, b2 has two friends
in A, ai and aj. This is a contradiction. Because b2 is a
member not in A, the k-FAN centered at b2 should have only one
common member with A.

ai=aj，因此b2还是只有一个朋友在A里，没有推出矛盾。

wwwfun不妨继续。

#### wwwfun

• Guest
##### 每周一题: 政治家 (12/6/04 -- 12/12/04)
« Reply #24 on: 十二月 09, 2004, 10:08:53 am »
In my constuction of B, ai is the common friend of b0 and a0, and b2, ..., bk is the common friend of b0 and (a1, a2, ..., a(i-1), a(i+1), ...).  ai is excluded in the construction.

#### 没头脑

• Newbie
• Posts: 8
##### 每周一题: 政治家 (12/6/04 -- 12/12/04)
« Reply #25 on: 十二月 09, 2004, 10:20:40 am »

#### fzy

• Hero Member
• Posts: 520
##### 每周一题: 政治家 (12/6/04 -- 12/12/04)
« Reply #26 on: 十二月 09, 2004, 10:28:31 am »
Quote from: warren

To plug this hole:

We know I * sqrt(K-1) = K, where I is an integer <= N - 1. If sqrt(K-1) is irrational, this cannot be true. If sqrt(K-1) is rational, then sqrt(K-1) < I <= sqrt(K-1) + 1. This then forces K - 1 = 1.

#### wwwfun

• Guest
##### 每周一题: 政治家 (12/6/04 -- 12/12/04)
« Reply #27 on: 十二月 09, 2004, 10:45:43 am »
The details of construction B.
B has memebers: b0, ai, b2, ...., bk, where ai is the common friend of b0 and a0. b2, ..., bk are common friend of b0 and a1, ..., ak, excluding ai. let f(ai) is common friend of b0 and ai, only need to prove that f(ai) is different from f(aj) if i is not equal to j. Indeed if f(ai) = f(aj) = bk. Then a0 is common friend of both ai, bk and aj, bk. So, B is constructed and B contains k+1 members including b0.

I don't understand what it means: I exclude a memeber, who I should not exclude. My purpose is to contruct the k-subgruph centered at b0, and only need select what I need.

#### wwwfun

• Guest
##### 每周一题: 政治家 (12/6/04 -- 12/12/04)
« Reply #28 on: 十二月 09, 2004, 11:17:54 am »
OPPs. The sentence "Then a0 is common friend of both ai, bk and aj, bk" should be "Then both ai and aj are common friend of a0 and bk".

#### 没头脑

• Newbie
• Posts: 8
##### 每周一题: 政治家 (12/6/04 -- 12/12/04)
« Reply #29 on: 十二月 09, 2004, 11:43:29 am »

1. 设朋友最多的人a0有K个朋友. 如果K=2,很容易证明结论成立. 以下设K>=3.如果K不等于N, 则存在一个b0不是a0的朋友.根据MTN的证明,b0有K个朋友. 由于b0是任意的,因此所有不是a0的朋友的人有K个朋友. 在a0的朋友中,b0只有一个朋友,a1. 其他人都不是b0的朋友,因此这些人都有K个朋友. 在a0的朋友中,a1只与一人是朋友,因此在a0的朋友中有人不是a1的朋友.根据同样的理由,a1有K个朋友. 因此所有人都有K个朋友.

b0是至少有k个朋友。如果b0的朋友数大于k，得证，因此只需考虑朋友数等于
k的情况。这点需要说明。后面的证明是完全对的，只是没解释清楚，别人理