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

a0。而因为a0仅有这k个朋友，所以a0和a1,a2,...,ak中任意一人的共同朋友也只

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.

b0在a1,a2,...,ak中不能再有第二个朋友，因为如果还有个朋友aj的话，a1和aj

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.

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

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 »

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.

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.

#### 万精油

• 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).

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

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.

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.

BTW professor, if you are against voting in the forum, I will take back the last paragraph.

#### 万精油

• 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}?

#### 万精油

• 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}?

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.