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

Anonymous

  • Guest
每周一题: 政治家 (12/6/04 -- 12/12/04)
« Reply #30 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.

Anonymous

  • Guest
每周一题: 政治家 (12/6/04 -- 12/12/04)
« Reply #31 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.

没头脑

  • Newbie
  • *
  • Posts: 8
每周一题: 政治家 (12/6/04 -- 12/12/04)
« Reply #32 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,然后又说矛盾?

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1831
每周一题: 政治家 (12/6/04 -- 12/12/04)
« Reply #33 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.

wwwfun

  • Guest
每周一题: 政治家 (12/6/04 -- 12/12/04)
« Reply #34 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.

fzy

  • Hero Member
  • *****
  • Posts: 520
每周一题: 政治家 (12/6/04 -- 12/12/04)
« Reply #35 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.

wwwfun

  • Guest
每周一题: 政治家 (12/6/04 -- 12/12/04)
« Reply #36 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]

wwwfun

  • Guest
每周一题: 政治家 (12/6/04 -- 12/12/04)
« Reply #37 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.

wwwfun

  • Guest
每周一题: 政治家 (12/6/04 -- 12/12/04)
« Reply #38 on: 十二月 09, 2004, 05:25:33 pm »
Now, I know what is the problem. The proof is not correct.

fzy

  • Hero Member
  • *****
  • Posts: 520
每周一题: 政治家 (12/6/04 -- 12/12/04)
« Reply #39 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.

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1831
每周一题: 政治家 (12/6/04 -- 12/12/04)
« Reply #40 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.

fzy

  • Hero Member
  • *****
  • Posts: 520
每周一题: 政治家 (12/6/04 -- 12/12/04)
« Reply #41 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}?

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1831
每周一题: 政治家 (12/6/04 -- 12/12/04)
« Reply #42 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.

fzy

  • Hero Member
  • *****
  • Posts: 520
每周一题: 政治家 (12/6/04 -- 12/12/04)
« Reply #43 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.

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1831
每周一题: 政治家 (12/6/04 -- 12/12/04)
« Reply #44 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.