# 情趣生活

## 情趣生活 => 灵机一动 => 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

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

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

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

a0，因此a1,a2,...,ak中任意两人在a1,a2,...,ak之外不能有共同朋友。从而推

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

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.

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

１。如果命题不成立，则所有人的朋友数相同。
２。所有人的朋友数等于２。

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

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.

Title: 每周一题: 政治家 (12/6/04 -- 12/12/04)
Post by: fzy 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.  :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.

Title: 每周一题: 政治家 (12/6/04 -- 12/12/04)
Post by: warren on 十二月 08, 2004, 07:24:18 pm

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
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
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不妨继续。
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

Title: 每周一题: 政治家 (12/6/04 -- 12/12/04)
Post by: fzy 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.
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

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的情况。这点需要说明。后面的证明是完全对的，只是没解释清楚，别人理

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

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.
Title: 每周一题: 政治家 (12/6/04 -- 12/12/04)
Post by: Anonymous 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.
Title: 每周一题: 政治家 (12/6/04 -- 12/12/04)
Post by: 没头脑 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.

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

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

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

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.

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.

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: 万精油

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: