IBM Ponder This #047 · 2002 年 3 月

本题根据 Sharon Sela 的建议改编。俱乐部有有限名固定成员，每周聚会一次，每人喝茶或咖啡。第一周各自任选；从第二周起，每人选择其朋友中上一周多数人所喝的饮料。若朋友中两种饮料人数相同，就继续喝自己上一周的饮料。所有人依据上一周的状态同时更新。

朋友关系固定、对称，不包括自己，也不要求传递。也就是说，关系可用无自环、无重边的无向图表示。

状态总数有限，且下一状态仅由上一状态决定，所以最终必然进入周期。

1. 证明最终周期只能为 1 或 2。
2. 构造一个有 1000 名成员的俱乐部，使其经过 18 年才进入周期。能持续更久吗？

解答

认真尝试后再打开

待补充。