脑坛聚餐证明 - 珍珠湾ART

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

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

为简单起见，设每人是自己的半个朋友，这样数朋友时就不会有平局。让每个人每周都统计一下自己的朋友坐在两桌的各有多少（自己的半个别忘了)，然后把大的数（记为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 中文叫什么？

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

Husonghu，寒潭清，

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.

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

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

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

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

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