2011-04-04 23:24| 
16 Comments | 本文内容遵从 一个公司里有 n 个员工，其中某些员工之间有“好友”的关系（这是一个对称的关系）。每天早晨来到公司，员工们都会从茶和咖啡中选择一样作为早饮。此时，每个员工都会观察自己的朋友们都在喝啥：如果超过一半的人都在喝茶，第二天他自己也会跟着喝茶；如果超过一半的人都在喝咖啡，第二天他自己就会跟着喝咖啡；如果喝茶喝咖啡的人数各占一半（仅当他有偶数个朋友时才会发生这种情况），则第二天他的决策不变，继续喝自己今天喝的东西。
由于 n 个员工一共只能产生 2n 种不同的早饮组合，因此总有一天大家喝的东西会和过去的某一天一模一样，从而产生循环。证明：循环的长度不超过 2 。
我们用一个图论模型来描述这个问题，每个员工都用图里的一个顶点来表示。所不同的是，尽管这是一个无向图（朋友关系是对称的），但在下面的证明中我们仍然使用了有向图的模型。对于两个互为好友的顶点 x 和 y，我们同时添加从 x 到 y 的有向边，以及从 y 到 x 的有向边。
对于每一个有奇数个好友的员工，他的决策都很简单：昨天大多数好友都喝的啥，今天他就喝啥。但是对于有偶数个好友的员工，决策就没有那么容易描述了。妙就妙在这里：我们给所有有偶数个好友的员工添加一个从自己出发指向自己的自环，让他的出度入度也都是奇数。这样一来，当喝两种饮料的好友各占一半时，他自己的决策会打破平局；而当喝两种饮料的好友数量不同（至少相差 2）时，算上自己喝的也不会改变结果。因此，对于有偶数个好友的员工，决策变得和其他员工也一样了：他所指向的顶点昨天喝什么的更多，他今天就喝什么，不必担心有平局现象发生。
如果员工 x 和员工 y 是好朋友，并且第 i 天 x 喝的饮料与第 i + 1 天 y 喝的饮料相同，我们就说第 i 天员工 x 影响了员工 y。注意，那些有自环的人要把自己看作自己的朋友，因此自己影响自己也是要算的。那么在第 i 天，图里一共有多少条“影响边”呢？如果 x 的好友中，第 i+1 天里有 ti+1 个人喝茶，有 ci+1 个人喝咖啡（记住， ti+1 一定不等于 ci+1 ），那么从 x 出发的影响边数量就是 ti+1 或者 ci+1 （取决于第 i 天 x 喝的什么）。遍历所有的 x 求出总和，就是图里总的影响边数量。
在第 i+1 天，图里有多少条影响边呢？我们现在换一个方法，从“被影响”的角度来计算影响边的数量。对于 x 来说，指向他的影响边数目显然是 ti+1 和 ci+1 的较大值，因为按照规则，他在第 i+2 天喝的饮料应该与第 i+1 天多数人喝的一样。遍历所有的 x 求出总和，就是图里总的影响边数量。注意，影响边的数量不可能变少了，因为刚才我们累加的是 ti+1 和 ci+1 之一，但这次我们累加的是 ti+1 和 ci+1 的较大值。
但是图里的影响边数量不可能一直在严格增加，因为它不可能超过图里的总边数。因此，总会有一天，图里的影响边总数和前一天相等。而考虑前面的证明过程，这就意味着，对于每个员工 x 来说，昨天从他出发的影响边数量和今天指向他的影响边数量取的是 ti+1 和 ci+1 中的同一个数，即昨天他影响的那些人，也就是今天影响了他的人。换句话说，昨天他喝的东西，和明天他要喝的东西一样。因此，循环长度不超过 2。