脑坛聚餐证明

constant · 发表于 2005-12-9 05:16:46

脑坛有很多人，其中有些人是朋友，有些人不是。是朋友的永远是朋友，不是朋友的永远不是。（别生气，题目要求如此。）现在脑坛决定每周举行一次聚餐。聚餐的地方有两张大桌子，每张都可以坐下所有的人。第一次时每个人随机的选一张桌子坐下，以后每个人都这样决定：如果这次聚餐时自己的朋友在另一桌的比在本桌多，那下一次就坐到另一桌，否则不动。（一样多时也不动。）

证明若干星期只后只剩下两种人：一种人在某一桌坐定，不再移动；另一种人每周换一次桌子，永不停止。

为简单起见，设每人是自己的半个朋友，这样数朋友时就不会有平局。让每个人每周都统计一下自己的朋友坐在两桌的各有多少（自己的半个别忘了)，然后把大的数（记为a)报告给Husonghu。这桌是自己下周要坐的。再把自己上周所坐桌的朋友数(记为b)报告给寒潭清。这两桌可能是一桌，这时a=b，否则a>b。Husonghu和寒潭清把大家报告的数加起来，记为F(t)和G(t)，其中t是时间。我们有F(t) >= G(t)。但F(t)和G(t)实际上是同样的量：都是朋友之间互相影响的总数。F(t)是本周到下周的总数，G(t)是上周到本周的总数，所以F(t-1) = G(t)。（这个方法叫Double counting。）这样我们证明了F(t)是递增函数。但F(t)是有界的，所以若干周后F达到最大值，不再增加。这时对每个人，a和b都相等，也就是所有人下周和上周所坐的桌子都相同。如果本周的桌子也相同，那这个人就不再移动。如果本周桌子不同，那这个人就会每周换一次桌子。

问一下：Double Counting 中文叫什么？

野菜花 · 发表于 2005-12-10 03:47:49

Now I understand, thank you! 方法很妙！

[@};

constant · 发表于 2005-12-10 03:05:27

G(2) isthe number of your friends who sit in week two at the table where you were in week one.

野菜花 · 发表于 2005-12-10 02:04:21

you mean G(2) is for the 1st dinner? but why G(2)=2.5+1.5+0?

constant · 发表于 2005-12-10 01:50:25

G(1) is not defined. G(2) = 2.5 + 1.5 + 0 = 4

野菜花 · 发表于 2005-12-10 01:38:34

I don't understand why F(t-1)=G(t).

I also tried several examples, it was not true, maybe I counted wrong? Could you check the simplest example below for me?

Three people:1, 2, 3, two pairs of friends:(1,2),(1,3)

1st dinner: 1,2 at one table, 3 at another

F(1)=1.5+1.5+1=4

G(1)=1.5+1.5+0.5=3.5

2nd dinner: 1,2,3 all at one table

F(2)=G(2)=2.5+1.5+1.5=5.5

F(1)!=G(2)

constant · 发表于 2005-12-9 21:22:40

Yes, it means no third type exists. It could even be more extreme. Suppose there are only 4 people with the following friendships:

Husonghu，寒潭清，

Husonghu, 野菜花

Jenny, 寒潭清

Jenny，野菜花

If Husonghu and Jenny on one table and 寒潭清 and 野菜花 on the other. Then you four will keep changing tables for ever. But if you all on the same table, then no one moves.

husonghu · 发表于 2005-12-9 06:28:56

"每张都可以坐下所有的人。第一次时每个人随机的选一张桌子坐下，..."

我举个有点极端的例子：脑坛总数有100人，每人至少有20个朋友，第一次随机坐桌子的时候，A桌坐了90人，B桌坐了10人，那从第二次起所有人都坐到了A桌，永远不动了。根本没有每周换一次桌子的人。

是不是两种人不一定同时有，只有一种人也行？即，对每个人来说是非此即彼，但所有的人可都属同一种人？

Did I miss anything?

		自动登录	找回密码
密码			立即注册

动态微博

脑坛聚餐证明

Now I understand, thank you! 方法很妙！[@};-][@};-][@};

回复：回复：回复：回复：脑坛聚餐证明

回复：回复：回复：脑坛聚餐证明

回复：回复：脑坛聚餐证明

回复：脑坛聚餐证明

回复：我连看答案都看得稀哩糊涂的。问个问题.........

我连看答案都看得稀哩糊涂的。问个问题.........