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

#### 万精油

• Hero Member
• Posts: 1831
##### 每周一题: 政治家 (12/6/04 -- 12/12/04)
« on: 十二月 06, 2004, 10:37:59 am »

« Last Edit: 十月 08, 2009, 09:37:41 pm by 万精油 »

#### fzy

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

#### 万精油

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

#### idiot94

• Sr. Member
• Posts: 484
##### 每周一题: 政治家 (12/6/04 -- 12/12/04)
« Reply #3 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 ..  Maybe I am going the wrong way ... so .. just for fun
In general, the men of lower intelligence won out. Afraid of of their own shortcomings ... they boldly moved into action. Their enemies, ...  thought there was no need to take by action what they could win by their brains. Thucydides, History

#### fzy

• Hero Member
• Posts: 520
##### 每周一题: 政治家 (12/6/04 -- 12/12/04)
« Reply #4 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.    Now I give up and wait for the professor's hint.

#### 没头脑

• Newbie
• Posts: 8
##### 反证法
« Reply #5 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之外不能有共同朋友。从而推

#### idiot94

• Sr. Member
• Posts: 484
##### 每周一题: 政治家 (12/6/04 -- 12/12/04)
« Reply #6 on: 十二月 07, 2004, 05:00:53 pm »
check your number counting again, brother
In general, the men of lower intelligence won out. Afraid of of their own shortcomings ... they boldly moved into action. Their enemies, ...  thought there was no need to take by action what they could win by their brains. Thucydides, History

#### 没头脑

• Newbie
• Posts: 8
##### 每周一题: 政治家 (12/6/04 -- 12/12/04)
« Reply #7 on: 十二月 07, 2004, 05:05:42 pm »

#### visitor

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

#### visitor

• Guest
##### 每周一题: 政治家 (12/6/04 -- 12/12/04)
« Reply #9 on: 十二月 07, 2004, 08:37:53 pm »
One more. fzy, could you give the details of proof of your partial results?

#### fzy

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

#### wwwfun

• Guest
##### a solution based on MTL's argument.
« Reply #11 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.

#### MrPuzzle

• Jr. Member
• Posts: 75
##### 每周一题: 政治家 (12/6/04 -- 12/12/04)
« Reply #12 on: 十二月 08, 2004, 10:05:51 am »
deleted

#### 万精油

• Hero Member
• Posts: 1831
##### 每周一题: 政治家 (12/6/04 -- 12/12/04)
« Reply #13 on: 十二月 08, 2004, 10:07:41 am »

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

#### wwwfun

• Guest
##### 每周一题: 政治家 (12/6/04 -- 12/12/04)
« Reply #14 on: 十二月 08, 2004, 01:12:22 pm »
MTL proved that:

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