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

#### fzy

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

#### 万精油

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

#### fzy

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

#### 万精油

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

#### fzy

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

#### 万精油

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

#### fzy

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

#### 万精油

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

#### fzy

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

#### 万精油

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

#### fzy

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