权力游戏之瓦里斯的小老鼠：“八爪蜘蛛”瓦里斯在得知雪诺的真实身份之后，开始密谋推翻女王丹妮莉丝。作为情报总管，他有一只经过训练外号小老鼠的情报网，总共有 1000 人，假设每天他们之中每个人都会把昨天听到的消息告诉给自己认识的人，并且任何消息都将逐渐地为全部的小老鼠知晓。请问如果瓦里斯希望在10 天之内让这个消息让全部1000个小老鼠知晓，最多需要把这个消息同时告诉多少个小老鼠？
- 20个；
- 50个；
- 90个；
- 101个；
。。。。。。
正确答案：3；（解析：由题设得，村里的任何两个老鼠A和Z必有熟人链联系着，即A认识B，B认识C，…，Y认识Z，否则，传给B的消息就不能为Z所知道，与题设矛盾。我们将只考虑这样的熟人链，在链中每个成员只出现一次，如果链中某成员M出现两次，即含有闭合链M一N一…一M，我们可以割断M，N之间的联系，而从原有的整条链中删除N一…一M这一部分，剩下的还有链，那么，从没有闭合链的假设推得，任何两居民A和Z之间有且仅有一条熟人链，因为如果有两条链A一B′一…一Y′一Z和A一B一…一Y—Z，由于熟人关系是对称的，就有闭合链A一B一…一Y一Z—Y一…一B′一A，与假设矛盾，显然，我们只要在没有闭合链的假设下证明题设就够了。
上述联系两个老鼠的熟人链所有成员数目称为这两个老鼠的“距离”，可以选择两个老鼠x和r，他们的距离是最大的，我们研究联系他们的熟人链：X一A1一A2一…一Ak一Y ①
先设k≤l9（即链中不多于21人）。考虑这里适中的一个Am（k是偶数时，m=(1/2)k或(1/2) k 1；k是奇数时，m=（1/2） （k 1），它到链的两端的距离都不超过链长的一半加1，即小于或等于 （k 2） 1≤（1/2）（19 2） 1，取整数得11，于是Am到其他每个老鼠的距离也都不超过11，事实上，设且Am到任一老鼠Z的链是
Am一一B1一B2一…一Bn一Z ②
如果Bl不是Am—l，就是X到Z的链
X一A1一…一Am一Bn一Z ③
如果B1不是Am l，就有Z到Y的链
Z一Bn一…一B1一Am一…一Ak一Y ④
与X到Y的链①即
X—Al一…一A m一…一Ak—Y
比较，它和③不同的只是从Am以后改成②，和④不同的只是从Am以前改成倒过来的②，由于①是最长的链，其中Am到两端的距离都不超过11，所以②的长即A m到Z的距离也不超过11，因此，如果将某一消息告诉A m，那么至迟经过10天，这一消息便为全部老鼠所知晓了。
再设k≥20，这时取A10作为上述的A m，并且把消息告诉它，按上面的论证，A10到其他老鼠Z的链，只要是不经过A11的，它的长不超过11，因此，至迟经过10天，所有这样的Z就都知道消息了，现在把这些Z（至少包括X，A1…A9）和A10分离出来，剩下的老鼠至多只有1000—11人，原来由A10到剩下的每个老鼠的熟人链都经过A11，但不再经过被分出的任何老鼠，因为由A10到分出的每个老鼠已经有不经过A11的链，不可能再有经过A11的链，这就是说，在剩下的老鼠中，由A11到其他每个老鼠都有熟人链，从而把由A11到任何两个老鼠的链在其共有的最后成员处连接起来，就是这两个老鼠之间的链，因此，剩下的老鼠仍可按上述方法处理。
上述方法每进行一次，就可以把消息告诉一个老鼠，使得在10天之内至少有11个人知道这个消息，由于1000=11×89 21，所以至多进行89 1次，就可以选出90个居民，同时告诉他们某一消息，使得经过10天这一消息便为全部老鼠所知晓。）
