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

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1831
每周一题: 政治家 (12/6/04 -- 12/12/04)
« on: 十二月 06, 2004, 10:37:59 am »
自从开放发贴以来,这里多了不少贴子,为这个论坛增添了许多生气,很令人高兴。但与此同时,也引来了一点问题,有人在这里贴带有很强政治色彩的贴子。政治问题不象数学问题,永远也讨论不清楚。我们不希望这里变成政治讨论的战场。我把它删了。希望大家以后不贴这样的贴子。另外,随着所贴题目的增多,我觉得有必要定一个大概的贴题需知。我刚刚写好一个,请看连接

关于注册问题我以前已经说过。虽然现在不用注册也可以上贴了,但注册还有其它好处。最大的好处就是每次你阅读此论坛,它都能记住哪些贴子你读过,哪些没有读过。任何话题里如果有你没有读过的贴子,它都会显示出来。这样你就不用一个一个的去看有没有新贴。

上周问题讨论:

上周问题由IDIOT94解出。主要思路就是如果许多项的平均值大于某数,则这些必然有某一项也大于某数。这种思想说起来简单,但如果能很好的运用,可以解决很多问题。比如以前出过的天平换边的问题也用的是这种思路。

这周的问题比较难,或者说很难。别人给我出这道题时我花了很长时间都没有做出来。后来我的一个学图论的朋友做出来了,但他的证明很长,看起来很辛苦。幸好后来又在别的地方看见一个比较容易懂的证明,所以我就把这道题出出来。虽然它的难度已经超出了灵机一动的范围,但一方面这里的读者中有很多厉害人物,另一方面这道题确实很有趣。如果两天内没有人做出来,我会贴一点提示。

本周题目:政治家

如果一个人数大于等于三的人群满足下面这个条件:[人群中任意两个人都有一个而且只有一个共同的朋友],那么这群人中一定有一个人是所有人的朋友。这个人被称为政治家。注意:朋友是双向的。张三是李四的朋友,则李四也是张三的朋友。
« 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?

万精油

  • Administrator
  • 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 ..:D  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.  :cry:  Now I give up and wait for the professor's hint.

没头脑

  • Newbie
  • *
  • Posts: 8
反证法
« Reply #5 on: 十二月 07, 2004, 04:50:23 pm »
没头脑听说万教授出了道难题,就赶紧来凑热闹。这题确实有点难,费了没头脑
不少时间。现在没头脑来解一下:

设这群人总数为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一定是偶数。

现在假设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之外不能有共同朋友。从而推
出,b0与a1,a2,...,ak中所有人的共同朋友有k个。加上b0与a1是朋友,因此b0
至少有k+1个朋友,超过a0的朋友数k。这与我们最初的假设矛盾。

由此反证出,k=N-1,而N=k+1为奇数。即朋友数最多的那个人必须认识所有人,
且这群人总数必为奇数。

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 »
有一点错了,就是如果a1和a2是朋友的话,b0和a2的共同朋友就是a1。这样算
来b0也就k个朋友,差一点。感觉这反证法还是行得通的,容我再想想。

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.
Now, I show the contradiction.

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

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1831
每周一题: 政治家 (12/6/04 -- 12/12/04)
« Reply #13 on: 十二月 08, 2004, 10:07:41 am »
两天过去了,应该是给提示的时候了。

提示分两部分:
1。如果命题不成立,则所有人的朋友数相同。
2。所有人的朋友数等于2。

第一点好象已经有人证明了。事实上把没头脑关于最大朋友数的证明稍微改一下就可以证明1。如果能证明第二点,所有朋友数等于二,那么这群人最多只能有三个人,命题得证。

这道题的难处在于,在证明1以及其它小定理时,所有的思路都是图论方面的。而要证明2,就必需脑筋急转弯,换到线性代数上去。所以,我再对2的证明给一点提示:主要从连结矩阵上入手。连结矩阵A是N  X  N的一个大矩阵。A(I,J)=1如果I,J是朋友,否则等于0。根据朋友数必需相等的结论写出A的形式,再根据原题的条件写出A^2的形式,然后从特征值上入手推出K=2。

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
就有a0和b0两个共同朋友

and in his follow up:

就是如果a1和a2是朋友的话,b0和a2的共同朋友就是a1。这样算
来b0也就k个朋友

So, in my understanding, b0 do bring k new members in the group.
Could MTL check my argument?