Author Topic: 每周一题: 政治家 (12/6/04 -- 12/12/04)  (Read 84430 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.

没看明白。第二部分说b0引进k个新成员是对的。但事实上,这k个新成员中
有个b0与a1的共同朋友是与b0对称的,不妨设为b1。这b1也有k个朋友,除
了a1和b0,其余的k-2个是新引进的成员。这样,我们至少已知有3k-1个成员,
而不仅是2k+1。但如果wwwfun的第一部分证明是错的,这些都没用。

有一点,从这里可看出,a0、b0、b1均有k个朋友。但我还是没想出如何改一
下去证明所有人的朋友数均等于k。

fzy

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

有一点,从这里可看出,a0、b0、b1均有k个朋友。但我还是没想出如何改一
下去证明所有人的朋友数均等于k。


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.  :x

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.
解这两个方程得N=3,K=2,矛盾.

warren

  • Full Member
  • ***
  • Posts: 148
每周一题: 政治家 (12/6/04 -- 12/12/04)
« Reply #21 on: 十二月 08, 2004, 07:24:18 pm »
还有一点漏洞, A的特征根应该是一个+/-sqrt(N+K-1),N-1个+/-sqrt(K-1). A的特征根可以是负数.

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
   (a1,... a(i-1), a(i+1), .., ak). Now start with one b0.
   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
(a1,... a(i-1), a(i+1), .., ak). Now start with one b0.
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.

上面这段明显有个错,就是wwwfun没有考虑i=j的情况。事实上在这里,
ai=aj,因此b2还是只有一个朋友在A里,没有推出矛盾。

我觉得这道图论题最后用线性代数来解决,虽然简洁了,但是不完美。
我还是想看到有人最后用图论来解决整个问题。虽然warren已解决了,
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 »
你把ai排除了却没有给出解释。你把一个本不该排除的点排除了,这就已经
错了,那你后面再推出矛盾就很正常了。

我前面帖子里说:

没看明白。第二部分说b0引进k个新成员是对的。但事实上,这k个新成员中
有个b0与a1的共同朋友是与b0对称的,不妨设为b1。这b1也有k个朋友,除
了a1和b0,其余的k-2个是新引进的成员。这样,我们至少已知有3k-1个成员,
而不仅是2k+1。但如果wwwfun的第一部分证明是错的,这些都没用。

你的b2就是我说的b1。

fzy

  • Hero Member
  • *****
  • Posts: 520
每周一题: 政治家 (12/6/04 -- 12/12/04)
« Reply #26 on: 十二月 09, 2004, 10:28:31 am »
Quote from: warren
还有一点漏洞, A的特征根应该是一个+/-sqrt(N+K-1),N-1个+/-sqrt(K-1). A的特征根可以是负数.


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 »
线性代数早忘得差不多了,因此就当warren的第二部分正确。但第一部分是
看明白了的,解得很漂亮,只是有一处不严密:

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的情况。这点需要说明。后面的证明是完全对的,只是没解释清楚,别人理
解起来费劲。既然b0有k个朋友,等同于a0,那么不是他朋友的a0和ai(i!=1)
就等同于b0,也至少有k个朋友(同样也只需考虑朋友数为k的情况)。从而任
意一个不是a1朋友的ai也等同于a0,而a1等同于b0……