情趣生活

情趣生活 => 灵机一动 => Topic started by: 万精油 on 十二月 06, 2004, 10:37:59 am

Title: 每周一题: 政治家 (12/6/04 -- 12/12/04)
Post by: 万精油 on 十二月 06, 2004, 10:37:59 am
自从开放发贴以来,这里多了不少贴子,为这个论坛增添了许多生气,很令人高兴。但与此同时,也引来了一点问题,有人在这里贴带有很强政治色彩的贴子。政治问题不象数学问题,永远也讨论不清楚。我们不希望这里变成政治讨论的战场。我把它删了。希望大家以后不贴这样的贴子。另外,随着所贴题目的增多,我觉得有必要定一个大概的贴题需知。我刚刚写好一个,请看连接 (http://www.zhipingyou.com/qqsh/index.php?topic=188)。

关于注册问题我以前已经说过。虽然现在不用注册也可以上贴了,但注册还有其它好处。最大的好处就是每次你阅读此论坛,它都能记住哪些贴子你读过,哪些没有读过。任何话题里如果有你没有读过的贴子,它都会显示出来。这样你就不用一个一个的去看有没有新贴。

上周问题 (http://www.zhipingyou.com/qqsh/index.php?topic=172)讨论:

上周问题由IDIOT94解出。主要思路就是如果许多项的平均值大于某数,则这些必然有某一项也大于某数。这种思想说起来简单,但如果能很好的运用,可以解决很多问题。比如以前出过的天平换边的问题也用的是这种思路。

这周的问题比较难,或者说很难。别人给我出这道题时我花了很长时间都没有做出来。后来我的一个学图论的朋友做出来了,但他的证明很长,看起来很辛苦。幸好后来又在别的地方看见一个比较容易懂的证明,所以我就把这道题出出来。虽然它的难度已经超出了灵机一动的范围,但一方面这里的读者中有很多厉害人物,另一方面这道题确实很有趣。如果两天内没有人做出来,我会贴一点提示。

本周题目:政治家

如果一个人数大于等于三的人群满足下面这个条件:[人群中任意两个人都有一个而且只有一个共同的朋友],那么这群人中一定有一个人是所有人的朋友。这个人被称为政治家。注意:朋友是双向的。张三是李四的朋友,则李四也是张三的朋友。
Title: 每周一题: 政治家 (12/6/04 -- 12/12/04)
Post by: fzy on 十二月 07, 2004, 12:24:12 pm
Do we need other conditions on the number of people in the group? If it is even, there cannot be a politician in the group. Or there cannot be a group of an even number of people that satisfies the condition?
Title: 每周一题: 政治家 (12/6/04 -- 12/12/04)
Post by: 万精油 on 十二月 07, 2004, 12:35:35 pm
Yes, to satisfy the condition of the problem, the group can only have odd number of people. It is not a condition, it is part of the result. The final configuration should be a person (the politician) in the center with pairs of people suround him, sort of like a fan. It is easy to see that this configuration satisfy the condition, but hard to prove this is the only possible configuration.
Title: 每周一题: 政治家 (12/6/04 -- 12/12/04)
Post by: idiot94 on 十二月 07, 2004, 12:43:34 pm
Yep, if it is even, there is no such graph. But that does not hurt the original statement.

BTW, while thinking about this problem, I got this little equation and maybe for our discussion's convenience, let me introduce a bit notation:

Let G be a graph satisfying the condition (i.e., for any a, b in G, edge ab exists iff a and b are friends. For any a, b in G, let (a,b):= c in G such that c is the unique friend of both a and b. Denote A={b in G | b is a friend of a} ), n=|G|, for any vi in G, let us denote the degree of vi just by vi itself, then n*(n-1) = sum of {vi*(vi-1)} for all vi in G.

Probably useless, but I just think it is fun.

The other partial simple steps I got:
1) If there exists v in G, with v=2, then statement is true.
2) If there exists v in G with v>(n-1)/2, then there exists u in G with u=2.

But I cannot prove "max degree of v in G <= (n-1)/2  ==> there is u=2 or contradiction".... Still stuck here ..:D  Maybe I am going the wrong way ... so .. just for fun :)
Title: 每周一题: 政治家 (12/6/04 -- 12/12/04)
Post by: fzy on 十二月 07, 2004, 01:15:59 pm
I have these partial results:

1. Each relation is part of one and only one Triagular Relationship (a, b, c are friends to each other).
2. If there is no politician in a group, the number of people in the group must be 2k*(2k-1) + 1 for some k>=3, and each person must have exactly 2k friends.
3. The relations form (k*(2k-1)+1)*k/3 triagular relationships. This also inplies that k or k-1 must be divisible by 3.

I cannot go any further from here. The smallest group satisfying the condition has 31 people and 31 triagular relationships in it, and that is way beyond my thinking ability.  :cry:  Now I give up and wait for the professor's hint.
Title: 反证法
Post by: 没头脑 on 十二月 07, 2004, 04:50:23 pm
没头脑听说万教授出了道难题,就赶紧来凑热闹。这题确实有点难,费了没头脑
不少时间。现在没头脑来解一下:

设这群人总数为N。因为N有限,所以总能找出一个朋友最多的人,设为a0。a0共
有k个朋友,设为a1,a2,...,ak。显然,a1,a2,...,ak中任意两人的共同朋友是
a0。而因为a0仅有这k个朋友,所以a0和a1,a2,...,ak中任意一人的共同朋友也只
能在这k个人中。因此a1,a2,...,ak中任意一人在这k个人中有且只能有一个朋友,
不然如果a1有两个朋友a2和a3,那么a2和a3就有两个共同朋友a1和a0。这就推出
一个结论,k一定是偶数。

现在假设a0并没有认识所有人,即k<N-1,那么,至少有一个人不在这k+1个人中,
设这个人为b0。b0和a0的共同朋友只能在a1,a2,...,ak中,假设是a1。除此之外,
b0在a1,a2,...,ak中不能再有第二个朋友,因为如果还有个朋友aj的话,a1和aj
就有a0和b0两个共同朋友。由此推出,b0与a1,a2,...,ak中任意一人的共同朋友
只能在a1,a2,...,ak之外。而且,由于a1,a2,...,ak中任意两人已经有共同朋友
a0,因此a1,a2,...,ak中任意两人在a1,a2,...,ak之外不能有共同朋友。从而推
出,b0与a1,a2,...,ak中所有人的共同朋友有k个。加上b0与a1是朋友,因此b0
至少有k+1个朋友,超过a0的朋友数k。这与我们最初的假设矛盾。

由此反证出,k=N-1,而N=k+1为奇数。即朋友数最多的那个人必须认识所有人,
且这群人总数必为奇数。
Title: 每周一题: 政治家 (12/6/04 -- 12/12/04)
Post by: idiot94 on 十二月 07, 2004, 05:00:53 pm
check your number counting again, brother :)
Title: 每周一题: 政治家 (12/6/04 -- 12/12/04)
Post by: 没头脑 on 十二月 07, 2004, 05:05:42 pm
有一点错了,就是如果a1和a2是朋友的话,b0和a2的共同朋友就是a1。这样算
来b0也就k个朋友,差一点。感觉这反证法还是行得通的,容我再想想。
Title: 每周一题: 政治家 (12/6/04 -- 12/12/04)
Post by: visitor on 十二月 07, 2004, 08:35:15 pm
fzy already prove that each person is in one and only one triangle friendships. If it is true, modify your argument as the follows:
b0 and a0 has a common friend in a0, a1, ..., ak. Say he/she is a1.
From fzy's result, b0, a0 and a1 must form a triangle. Then a0 has one more friend b0. This is a contradiction.
Title: 每周一题: 政治家 (12/6/04 -- 12/12/04)
Post by: visitor on 十二月 07, 2004, 08:37:53 pm
One more. fzy, could you give the details of proof of your partial results?
Title: 每周一题: 政治家 (12/6/04 -- 12/12/04)
Post by: fzy on 十二月 07, 2004, 10:04:13 pm
Quote from: visitor
fzy already prove that each person is in one and only one triangle friendships.


I am sorry but I did not prove that each person is in one and only one triagular friendships. What I proved is that each friendship is part of one and only one triangular friendships. A person, as a vertex of the triangle, can belong to multiple traingles. It is quite easy to prove, but does not seem to be very useful by itself.
Title: a solution based on MTL's argument.
Post by: wwwfun on 十二月 08, 2004, 09:46:11 am
MTL's argument almost solves the problem.
Now, I show the contradiction.

All undefined notations are from MTL's post.
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.

In the second part of MTL's argument, if k < n-1, then, there is a b0, b0 will have
k friends as well. Only one of b0's friends is in a0, a1, .... That bring k new members
in the group. Now the contradiction is about the n. We have
2k+1 <= n. But, from the pigeon hole discussion, 2k > n.

By the way two side products are already in MTL's argument:
1. n is odd
2. the graph is of form "FAN", as professor W. mentioned.
Title: 每周一题: 政治家 (12/6/04 -- 12/12/04)
Post by: MrPuzzle on 十二月 08, 2004, 10:05:51 am
deleted
Title: 每周一题: 政治家 (12/6/04 -- 12/12/04)
Post by: 万精油 on 十二月 08, 2004, 10:07:41 am
两天过去了,应该是给提示的时候了。

提示分两部分:
1。如果命题不成立,则所有人的朋友数相同。
2。所有人的朋友数等于2。

第一点好象已经有人证明了。事实上把没头脑关于最大朋友数的证明稍微改一下就可以证明1。如果能证明第二点,所有朋友数等于二,那么这群人最多只能有三个人,命题得证。

这道题的难处在于,在证明1以及其它小定理时,所有的思路都是图论方面的。而要证明2,就必需脑筋急转弯,换到线性代数上去。所以,我再对2的证明给一点提示:主要从连结矩阵上入手。连结矩阵A是N  X  N的一个大矩阵。A(I,J)=1如果I,J是朋友,否则等于0。根据朋友数必需相等的结论写出A的形式,再根据原题的条件写出A^2的形式,然后从特征值上入手推出K=2。
Title: 每周一题: 政治家 (12/6/04 -- 12/12/04)
Post by: wwwfun on 十二月 08, 2004, 01:12:22 pm
MTL proved that:

b0和a0的共同朋友只能在a1,a2,...,ak中,假设是a1。除此之外,
b0在a1,a2,...,ak中不能再有第二个朋友,因为如果还有个朋友aj的话,a1和aj
就有a0和b0两个共同朋友

and in his follow up:

就是如果a1和a2是朋友的话,b0和a2的共同朋友就是a1。这样算
来b0也就k个朋友

So, in my understanding, b0 do bring k new members in the group.
Could MTL check my argument?
Title: a typo
Post by: wwwfun on 十二月 08, 2004, 01:18:01 pm
In my argument, in th contradition, it should be that 2k+1 > n, not 2k>n.
Title: 每周一题: 政治家 (12/6/04 -- 12/12/04)
Post by: 没头脑 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。
Title: 每周一题: 政治家 (12/6/04 -- 12/12/04)
Post by: fzy 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
Title: futher explanation
Post by: wwwfun 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.
Title: 每周一题: 政治家 (12/6/04 -- 12/12/04)
Post by: wwwfun 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.
Title: 每周一题: 政治家 (12/6/04 -- 12/12/04)
Post by: warren 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,矛盾.
Title: 每周一题: 政治家 (12/6/04 -- 12/12/04)
Post by: warren on 十二月 08, 2004, 07:24:18 pm
还有一点漏洞, A的特征根应该是一个+/-sqrt(N+K-1),N-1个+/-sqrt(K-1). A的特征根可以是负数.
Title: 每周一题: 政治家 (12/6/04 -- 12/12/04)
Post by: wwwfun 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.
Title: 每周一题: 政治家 (12/6/04 -- 12/12/04)
Post by: 没头脑 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不妨继续。
Title: 每周一题: 政治家 (12/6/04 -- 12/12/04)
Post by: wwwfun 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.
Title: 每周一题: 政治家 (12/6/04 -- 12/12/04)
Post by: 没头脑 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。
Title: 每周一题: 政治家 (12/6/04 -- 12/12/04)
Post by: fzy 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.
Title: 每周一题: 政治家 (12/6/04 -- 12/12/04)
Post by: wwwfun 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.
Title: 每周一题: 政治家 (12/6/04 -- 12/12/04)
Post by: wwwfun 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".
Title: 每周一题: 政治家 (12/6/04 -- 12/12/04)
Post by: 没头脑 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……
Title: 每周一题: 政治家 (12/6/04 -- 12/12/04)
Post by: Anonymous on 十二月 09, 2004, 11:55:30 am
Try to give a complete proof.

1. Quoted from MTN

设这群人总数为N。因为N有限,所以总能找出一个朋友最多的人,设为a0。a0共
有k个朋友,设为a1,a2,...,ak。显然,a1,a2,...,ak中任意两人的共同朋友是
a0。而因为a0仅有这k个朋友,所以a0和a1,a2,...,ak中任意一人的共同朋友也只
能在这k个人中。因此a1,a2,...,ak中任意一人在这k个人中有且只能有一个朋友,
不然如果a1有两个朋友a2和a3,那么a2和a3就有两个共同朋友a1和a0。这就推出
一个结论,k一定是偶数。

From now on, let A = (a0, a1, ..., ak).
The structure of A=(a0, a1, ..., ak) is a FAN, mentioned in Professor W's post.

2.  quoted from MTN.

现在假设a0并没有认识所有人,即k<N-1,那么,至少有一个人不在这k+1个人中,
设这个人为b0。b0和a0的共同朋友只能在a1,a2,...,ak中,假设是a1。除此之外,
b0在a1,a2,...,ak中不能再有第二个朋友,因为如果还有个朋友aj的话,a1和aj
就有a0和b0两个共同朋友。由此推出,b0与a1,a2,...,ak中任意一人的共同朋友
只能在a1,a2,...,ak之外。而且,由于a1,a2,...,ak中任意两人已经有共同朋友
a0,因此a1,a2,...,ak中任意两人在a1,a2,...,ak之外不能有共同朋友。

Let f(ai) is the commone friend of b0 and ai. Then, f(ai) is outside A, and ai != aj implies f(ai) != f(aj). Indeed, if bk = f(ai) = f(aj) and ai != aj, then bk and a0 have two friends: ai, and aj, this is a contradiction. Let B=(b0, a1, b2, ..., bk), where bj = f(aj).
All a1, b2, ..., bk are friends of b0. and b2, ..., bk are outside A.
Since inside B, b0 already have k friends, b0 should not have more friend. A conclusion is that any member outside A should have only one friend in A.

3. Here is  the contradiction.
b0 and a1 must have a friend in B, say who is b2. Then from the definition b2 = f(a2). Now b2 is outside A, but have two friends a1 and a2 inside A.
Title: 每周一题: 政治家 (12/6/04 -- 12/12/04)
Post by: Anonymous on 十二月 09, 2004, 12:20:47 pm
Quote from: fzy
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.


这样证明更清楚一些:

I * sqrt(K-1) = K,  I 是整数. K-1必然是完全平方数, 设K-1=M,则有IM=MM+1.
MM+1被M整除,必然有M=1,因此K=2, N=3.
Title: 每周一题: 政治家 (12/6/04 -- 12/12/04)
Post by: 没头脑 on 十二月 09, 2004, 12:24:00 pm
你这里犯的是与wwwfun同样的错误:

Let f(ai) is the commone friend of b0 and ai. Then, f(ai) is outside A, and ai != aj implies f(ai) != f(aj). Indeed, if bk = f(ai) = f(aj) and ai != aj, then bk and a0 have two friends: ai, and aj, this is a contradiction. Let B=(b0, a1, b2, ..., bk), where bj = f(aj).
All a1, b2, ..., bk are friends of b0. and b2, ..., bk are outside A.
Since inside B, b0 already have k friends, b0 should not have more friend. A conclusion is that any member outside A should have only one friend in A.

3. Here is the contradiction.
b0 and a1 must have a friend in B, say who is b2. Then from the definition b2 = f(a2). Now b2 is outside A, but have two friends a1 and a2 inside A.

既然你已知b2在A里有一个朋友a1,而且你已知b2在A里只能有一个朋友,
那么为什么还要塞给他一个朋友a2,然后又说矛盾?
Title: 每周一题: 政治家 (12/6/04 -- 12/12/04)
Post by: 万精油 on 十二月 09, 2004, 12:25:08 pm
Quote
我觉得这道图论题最后用线性代数来解决,虽然简洁了,但是不完美。
我还是想看到有人最后用图论来解决整个问题。


You are not alone. This theorem has been there for a long time, there were several proofs, the eigenvalue approach was given by Paul Erdos. And he thought this was the best proof. (Proof from the BOOK).  Other people feel the same way as you, and continue to look for new proofs. Around 2002, another really elementary proof showed up. This time, instead of eigenvalue of matrix, the proof use number theory. Not fancy number theory, just simple module p arithemetic.  I will give some hint here if people want to try it:

Assume the politician doesn't exist, we already have:

1. Everyone has the same number of friend k.
2. It is easy to show that k is even, and N = k(k-1)+1
3. k-1 is odd, which means k-1 will have an odd prime factor p.

Now, consider cycles of length p ({v0,v1,v2,...,vp-1,v0} is a cycle of length p if v1 is friend with v0, v2 is friend with v1, ..., v0 is friend with vp-1). We don't assume vi's are different from each other. We also add initial point features to the cycle, i.e. the same cycle with different initial point will be considered differently. {v0,v1,...,vp-1,v0} will be considered as different from {v1,v2,....vp-1,v0,v1}. We call such cycles Sp. How many such cycles are there? i.e. what is |Sp|? It is obvious that |Sp| is divisible by p (since there are p initial conditions).  

Final part: Proof that |Sp| is not divisible by p. This can be proved by considering paths of length p-1.

If none one gets the final part, I will post more tomorrow.
Title: 每周一题: 政治家 (12/6/04 -- 12/12/04)
Post by: wwwfun on 十二月 09, 2004, 12:49:01 pm
The last post is mine, and I forget to put my constant name there.
 
MTN, could you check my proof again.

In my proof, when construct B, I let b2=f(a2). At this moment, I don't know b2 already have friend in A!! Also don't know b0 should have only one friend in A!! So, After B is constructed, I declare that b0 has only one friend in A, because from the construction, only a1 is from A, and the maximal number of friends is k.

I told you that, from the first time I read your post, I strong believe you are almost done. Only thing is that, you try to conclude the contradiction from the maximal number of friends. That is the reason why you consider all f(ai), not exclude a1.

A lot of possible contradiction there. For example, in my last idea, I tried to find contradiction in the size. k>=[n/2] is not correct, but roughly, k>=sqrt(n). You already bring 3k-1 members in. There are 2k-2 are outside A. Treat them as b0, will bring about (2k-2)^2 members in. If is is not enough, for all new member outside A, so again. But, I give up for two reasons. 1. For the send round, third round, need to consider the overlapping, and I did not find the clear way to count the real new members in the second round, third round. 2. I found this proof.
Title: 每周一题: 政治家 (12/6/04 -- 12/12/04)
Post by: fzy on 十二月 09, 2004, 12:53:25 pm
Quote from: 万精油
(Proof from the BOOK).
 

Some explaination about the book:

Paul Erdos is a famous Hungarian mathematician (and very funny one, too). He said God has a book containing the best proof of every single theorem. He refers to it as The Book. The best praise he ever gave to a good proof is "directly from the book".

Quote from: 万精油

Assume the politician doesn't exist, we already have:

1. Everyone has the same number of friend k.
2. It is easy to show that k is even, and N = k(k-1)+1
3. k-1 is odd, which means k-1 will have an odd prime factor p.



Glad to see my partial results useful.
Title: 每周一题: 政治家 (12/6/04 -- 12/12/04)
Post by: wwwfun on 十二月 09, 2004, 01:06:48 pm
Quote
既然你已知b2在A里有一个朋友a1,而且你已知b2在A里只能有一个朋友,
那么为什么还要塞给他一个朋友a2,然后又说矛盾?


When set b2 = f(a2),  even don't know who is b2!!!
Also don't know b0 should only have one friend in A.
[/quote]
Title: 每周一题: 政治家 (12/6/04 -- 12/12/04)
Post by: wwwfun on 十二月 09, 2004, 01:28:49 pm
Now, I am sure my proof works. MTN, Professor W and anybody who is interested, could you check it. The complete self-contained proof is under name 游客 in this page. The proof is very elementory, and would not take you too much time.
Title: 每周一题: 政治家 (12/6/04 -- 12/12/04)
Post by: wwwfun on 十二月 09, 2004, 05:25:33 pm
Now, I know what is the problem. The proof is not correct.
Title: 每周一题: 政治家 (12/6/04 -- 12/12/04)
Post by: fzy on 十二月 09, 2004, 05:31:42 pm
Quote from: 万精油

Final part: Proof that |Sp| is not divisible by p. This can be proved by considering paths of length p-1.



We follow the professors notation for N, K and p: There are N people in the group, each person has K friends, N = K(K-1) + 1, and p is an odd prime number that devides K - 1.

Now consider the paths of length P - 1 (call then (P-1)-paths) from a person to one of his friends. These paths have a 1-1 relationship with the p-cycles. And now we calculate the number of such paths.

Define function F(I) as the number of I-path from a person to himself, and G(I) as the number of I-paths to any other person. We have

F(2) = K
G(2) = 1

and inductively we have for any even number I > 2,

F(I) = F(I-2) * K + (N-1) * G(I-2)
G(I) = F(I-2) + G(I-2) * K + (N-2) * G(I-2) = F(I-2) + (K^2-1) * G(I-2)

Here the three terms F(I-2),  G(I-2) * K, (N-2) * G(I-2) are number of paths that pass through the start point, end point, and any other point at the I-2 step.

Note that p devides K-1 and N-1 , but not K. So inductively we see that p does not devide F(I) and G(I) for any I.

The number of total p-cycles now is N * K * G(p-1). And we see that p does not devide this number, and it contradicts to what the professor showed. :D

Finally, assuming that this solution and the one by eigenvlues are the best two, let's vote which one should go to The Book. I vote for this one.  8)

BTW professor, if you are against voting in the forum, I will take back the last paragraph.
Title: 每周一题: 政治家 (12/6/04 -- 12/12/04)
Post by: 万精油 on 十二月 09, 2004, 08:16:59 pm
Quote
Now consider the paths of length P - 1 (call then (P-1)-paths) from a person to one of his friends. These paths have a 1-1 relationship with the p-cycles. And now we calculate the number of such paths.


(p-1) path does not have a 1-1 relationship with the p-cycles. There's a relationship, but not 1-1.

I don't mind voting. I like this one too.
Title: 每周一题: 政治家 (12/6/04 -- 12/12/04)
Post by: fzy on 十二月 10, 2004, 10:37:24 am
Quote from: 万精油

(p-1) path does not have a 1-1 relationship with the p-cycles. There's a relationship, but not 1-1.



I did not get it, professor. We are talking about (p-1) path from a person to one of his friends. Certianly the relation is established by {v0,v1,v2,...,vp-1,v0} -> {v0,v1,v2,...,vp-1}?
Title: 每周一题: 政治家 (12/6/04 -- 12/12/04)
Post by: 万精油 on 十二月 10, 2004, 10:47:56 am
Quote
I did not get it, professor. We are talking about (p-1) path from a person to one of his friends. Certianly the relation is established by {v0,v1,v2,...,vp-1,v0} -> {v0,v1,v2,...,vp-1}?


Two comments:

1. When I talked about p-1 path, I meant a friend path that involves p-1 people. v1 knows v2 knows v3,....,knows vp-1. Your p-1 path involves p people since you have an extra v0.

2. {v0,v1,v2,...,vp-1,v0} -> {v0,v1,v2,...,vp-1}, the reverse will only be true if vp-1 is friend with v0. There are many other vp-1 who's not friends with v0, that's why I said it is not a 1-1 relation.
Title: 每周一题: 政治家 (12/6/04 -- 12/12/04)
Post by: fzy on 十二月 10, 2004, 11:05:33 am
Quote from: 万精油


1. When I talked about p-1 path, I meant a friend path that involves p-1 people. v1 knows v2 knows v3,....,knows vp-1. Your p-1 path involves p people since you have an extra v0.


I was talking about paths with length p - 1. It will involve p nodes.

Quote from: 万精油

2. {v0,v1,v2,...,vp-1,v0} -> {v0,v1,v2,...,vp-1}, the reverse will only be true if vp-1 is friend with v0. There are many other vp-1 who's not friends with v0, that's why I said it is not a 1-1 relation.


The set of all p cycles and the set of all (p-1) paths from a person to one of his friends have a 1-1 relationship. And that is what I used in the argument.
Title: 每周一题: 政治家 (12/6/04 -- 12/12/04)
Post by: 万精油 on 十二月 10, 2004, 12:15:04 pm
Quote
The set of all p cycles and the set of all (p-1) paths from a person to one of his friends have a 1-1 relationship. And that is what I used in the argument.


May be you have different definition of 1-1 relation. Usually, when we say set A and B have a 1-1 relation, it means for each member of A there's a member in B corresponds to it. And,  for each member of B there's a member of A corresponds to it.  From your {v0,v1,v2,...,vp-1,v0} -> {v0,v1,v2,...,vp-1} map, I can see p-cycle to p-1 path correspondance, but I cannot see a p-1 path to p-cycle correspondance, since if vp-1 is not a friend of v0, then, {v0,v1,v2,...,vp-1,v0} is not a cycle.  May be I misunderstand your definition, please explain.
Title: 每周一题: 政治家 (12/6/04 -- 12/12/04)
Post by: fzy on 十二月 10, 2004, 12:48:06 pm
Quote

The set of all p cycles and the set of all (p-1) paths from a person to one of his friends have a 1-1 relationship.


This is the definition. The set under consideration is not all (p-1) paths. It is the (p-1) paths that go from one person to one of his friends.
Title: 每周一题: 政治家 (12/6/04 -- 12/12/04)
Post by: 万精油 on 十二月 10, 2004, 01:05:06 pm
Quote
This is the definition. The set under consideration is not all (p-1) paths. It is the (p-1) paths that go from one person to one of his friends.


Obviously, we have definition misunderstanding, let's all be more precise:

My definition: a cycle of length p is a set with p elements {v0,v1,v2,...,vp-1} such that v1 is friend with v0, v2 is friend with v1, ..., vp-1 is friend with vp-2,  v0 is friend with vp-1. The set Sp is the collection of all such p-cycles. Note, different starting point corresponds to different p-cycle. Also note, v0,v1,...,vp-1 don't have to be different from each other. e.g. if v0 and v1 are friends, we can have {v0,v1,v0,v1,v0,v1,....}

A path of length p-1 is a set with p-1 elements {v0,v2,...,vp-2} such that v1 is friend with v0, v2 is friend with v1, ..., vp-2 is friend with vp-3. Lp-1 is the set of all such p-1 paths. Again, v0,v1,...don't have to be different.

What's your definition?
Title: 每周一题: 政治家 (12/6/04 -- 12/12/04)
Post by: fzy on 十二月 10, 2004, 01:23:40 pm
Quote from: 万精油


Obviously, we have definition misunderstanding, let's all be more precise:

My definition: a cycle of length p is a set with p elements {v0,v1,v2,...,vp-1} such that v1 is friend with v0, v2 is friend with v1, ..., vp-1 is friend with vp-2,  v0 is friend with vp-1. The set Sp is the collection of all such p-cycles. Note, different starting point corresponds to different p-cycle. Also note, v0,v1,...,vp-1 don't have to be different from each other. e.g. if v0 and v1 are friends, we can have {v0,v1,v0,v1,v0,v1,....}

A path of length p-1 is a set with p-1 elements {v0,v2,...,vp-2} such that v1 is friend with v0, v2 is friend with v1, ..., vp-2 is friend with vp-3. Lp-1 is the set of all such p-1 paths. Again, v0,v1,...don't have to be different.

What's your definition?


My definition of p-cycle is the same as yours. My definition of (p-1) path goes one step further than yours. I consider the number of the steps, not nodes. {v0,v1} is a 1-path, while {v0,v1,v0} is a 2-cycle.

My proof might be a little different from what you have in mind. But I do not see a hole in it.
Title: 每周一题: 政治家 (12/6/04 -- 12/12/04)
Post by: 万精油 on 十二月 10, 2004, 01:52:49 pm
I see what's the problem now. We have the same definition for p-cycle and p-path (other than the length), but your set of p-path is not all the p-path, just the p-path that leads to a friend, which is equivalent of a p-cycle. I was confused because in your prove you use other paths such as G(I). Now, I understand what you are trying to do. Please explain the following equation

Quote
F(I) = F(I-2) * K + (N-1) * G(I-2)


In particular, the (N-1)*G(I-2) part.
Title: 每周一题: 政治家 (12/6/04 -- 12/12/04)
Post by: fzy on 十二月 10, 2004, 02:01:27 pm
Quote from: 万精油
Please explain the following equation

Quote
F(I) = F(I-2) * K + (N-1) * G(I-2)


In particular, the (N-1)*G(I-2) part.


It is probably more clear to write it as

F(I) = F(I-2) * F(2) + (N-1) * G(I-2) * G(2)

The two terms represent numbers of I-cycles that go through the start point or any other point at the (I-2) step.
Title: 每周一题: 政治家 (12/6/04 -- 12/12/04)
Post by: 万精油 on 十二月 10, 2004, 02:33:28 pm
I am more interested in where the N-1 come from. Do you mean for every element in G(I-2) you can generate N-1 element in F(I)? Is G(I) the number of I-path from one element to anther element, or the sum of such paths?
Title: 每周一题: 政治家 (12/6/04 -- 12/12/04)
Post by: fzy on 十二月 10, 2004, 02:58:55 pm
Quote from: 万精油
Is G(I) the number of I-path from one element to anther element, or the sum of such paths?


F(I) is the number of I-path from one person to himself, ie number of I-cycles starting from that one person. G(I) is the number of I-paths from one person to another (different) person.

Quote from: 万精油

I am more interested in where the N-1 come from.


Because there are N-1 "other persons" in the group. For example:

F(2) = K, G(2) = 1, F(4) = K^2 + (N-1), G(4) = K + K + (N-2).
Title: 每周一题: 政治家 (12/6/04 -- 12/12/04)
Post by: 万精油 on 十二月 10, 2004, 05:32:25 pm
I have been in and out of meeting all day today, post a messag during the break, didn't really put too much thought on what I was posting, sorry everyone. Now I have more time to think about your proof (more time was spent on understanding the definition of various terms :)), I think I unstand your proof now.  Very good, Job well done.

  Two more comments, the first one is minor, just my opinion, the second one is actually important for the proof.

1. Your proof requires F(I) and G(I) to be independant of the starting and ending point. Although it can be derived from the induction formula, it is better to point out in the proof.

2. There's another reason for using a prime factor p, not just to do p-module arithematic, but to make sure there's no smaller cycles in the p-cycle (otherwise, there will be repeated counting in Sp).

I will post the proof I know later when I get home.
Title: 每周一题: 政治家 (12/6/04 -- 12/12/04)
Post by: fzy on 十二月 10, 2004, 05:57:01 pm
Quote from: 万精油

1. Your proof requires F(I) and G(I) to be independant of the starting and ending point. Although it can be derived from the induction formula, it is better to point out in the proof.


Yes, it should be mentioned in the proof.

Quote from: 万精油

2. There's another reason for using a prime factor p, not just to do p-module arithematic, but to make sure there's no smaller cycles in the p-cycle (otherwise, there will be repeated counting in Sp).



I actually do not need p to be prime. Only p need to be odd. It is needed to show that p devides |Sp| as you pointed out. I did not mention it because I think readers of this forum are able to see it.
Title: 每周一题: 政治家 (12/6/04 -- 12/12/04)
Post by: 万精油 on 十二月 10, 2004, 10:59:10 pm
Ok, here's the proof that I know (not by me).

First, let's get the definition clear.

My definition: a cycle of length p is a set with p elements {v0,v1,v2,...,vp-1} such that v1 is friend with v0, v2 is friend with v1, ..., vp-1 is friend with vp-2, v0 is friend with vp-1. The set Sp is the collection of all such p-cycles. Note, different starting point corresponds to different p-cycle. Also note, v0,v1,...,vp-1 don't have to be different from each other. e.g. if v0 and v1 are friends, we can have {v0,v1,v0,v1,v0,v1,....}

A path of length p-1 is a set with p-1 elements {v0,v2,...,v(p-2)} such that v1 is friend with v0, v2 is friend with v1, ..., v(p-2) is friend with v(p-3). L is the set of all such p-1 paths. Again, v0,v1,...don't have to be different. Also note that my p-1 path is one element shorter than fzy's p-1 path.

Our previous result shows that if there's no politician, then, everyone has k friends. and k is even. Also, N = k(k-1)+1. Since k is even, k-1 is odd, and there's an odd prime factor of k-1. We pick one of such odd prime factor and denote it with p.

Now, the proof:

It is obvious that |Sp| is divisible by p, since every cycle can have p different starting point: {v0,v1,v2,...,v(p-1),v0},{v1,v2,...,v(p-1),v0,v1}, etc.

Now, we will show |Sp| is not divisible by p.

Consider the set L. It is obviously that there are N*k^(p-2) such p-1 paths.  There are N choices for the starting point, after that, each next one has k choices, thus, total of N*k^(p-2). There are two kinds of p-1 path in L. One kind is v(p-2)=v0, the other kind is v(p-2) != v0. We denote the set of the first kind as L1, the set of the second kind as L2.  There's a correspondance between L and Sp. Every Sp can be gotten by adding an element to a p-1 path. For any p-1 path in L1, there are k different ways to get to a p cycle. For any p-1 path in L2, there is one unique way to get to a p cycle, since v(p-2) and v0 can only have a unique friend. Thus,

|Sp| = k*L1 + L2 = (k-1)*L1 + L1 + L2 = (k-1)*L1 + N*k^(p-2), we know that N = 1(mod k-1),  k = 1(mod k-1), thus, the second term above cannot be divisible by p, thus, |Sp| cannot be divisible by p. QED.

Notice that once we get the definitions clear, the actual proof is very straight forward,  I like this approach very much.
Title: 每周一题: 政治家 (12/6/04 -- 12/12/04)
Post by: fzy on 十二月 12, 2004, 12:21:11 pm
Quote from: 万精油

|Sp| = k*L1 + L2 = (k-1)*L1 + L1 + L2 = (k-1)*L1 + N*k^(p-2)


Nice.  8) Now I vote for this proof to go to The Book. I don't know if it matters, though. It looks like God is a dictator.  :twisted: