g****y
发帖数: 323 | 1 国王总是怀疑他的大臣, 因此他让大臣们互相监视. 具体方法如下.
1. 每位大臣只能监视一位, 每位大臣都被监视, 不能监视自己.
2. 然 1 大臣监视 监视 2大臣 的 大臣. 让 2 大臣监视 监视 3大
臣 的大臣. 如此类推, 然最后一位大臣 监视 监视 1大臣 的 大臣.
求证, 国王有奇数(>3)位大臣.(不用归纳法也可以证明.) | J****e
发帖数: 382 | 2 由于每个人都有监视对象, 又同时被监视, 假设这个监视链
是 [a_1,a_2,a_3,a_4,a_5....a_n], 其中a_i各元素没有重复。
如果a_1=1,那么a_3=2, a_5=3,....
依次类推， 只有当n是奇数时1到n才能覆盖全部a_i,否则
到n/2+1步会出现a_1=n/2+1的重复赋值情况, 矛盾!
当然, 假设每人只有一个监视对象.
还有, 为什么不能=3个大臣?
【在 g****y 的大作中提到】
: 国王总是怀疑他的大臣, 因此他让大臣们互相监视. 具体方法如下.
: 1. 每位大臣只能监视一位, 每位大臣都被监视, 不能监视自己.
: 2. 然 1 大臣监视 监视 2大臣 的 大臣. 让 2 大臣监视 监视 3大
: 臣 的大臣. 如此类推, 然最后一位大臣 监视 监视 1大臣 的 大臣.
: 求证, 国王有奇数(>3)位大臣.(不用归纳法也可以证明.)
| J****e
发帖数: 382 | 3
没有矛盾, 我给你几个监视链你可以自己去推广 :)
N:=3 [1,3,2]
N:=5 [1,4,2,5,3]
N:=7 [1,5,2,6,3,7,4]
....
假设是N:=7, 那么第7个人监视监视1号的人, 也就是4号. | g****y
发帖数: 323 | 4 Suppose we have M guys.
Be careful of the narration of the problem. a_1 a_2 ... a_n
means the actual order. a_1 监视 a_2, a_2 监视 a_3, .... a_n
监视 a_1.
For in this problem,
1 大臣 监视 监视 2大臣 的 大臣,
2 大臣 监视 监视 3大臣 的 大臣,
and so on
So if a_1 is 1大臣, then a_3 must be 2大臣, and a_5 must be
3大臣, and so on. Since every unit is unique, so in fact we
can draw a circle and then place the 1, 2, 3 every other
unit. If the a_N then N number is greater than M, then we
just continue counting the positions.
Give you an |
|
