正 n 边形和开关解答（4） - 珍珠湾ART

正 n 边形和开关

正方形的每个角上有一个开关。你的目的是把四个开关的状态变成一样，即都是开或都是关。但你不知道开关的状态，每次你可以任选两个开关，检查并改变它们的状态。（当然也可以不改变。）问题是你选定两个开关后，正方形会旋转一个角度。（旋转的角度你不知道。）你有没有必胜策略？

现在假设是一个正六边形，每次你可以任选四个开关。你有没有必胜策略？

再假设是一个正八边形，每次你可以任选四个开关。你有没有必胜策略？www.ddhw.com

再假设是一个正 n 边形, 设 f(n) 是任选 f(n) 个开关有必胜策略的最小值。上面是说 f(4) <= 2, f(6) <= 4, f(8) <= 4。你能不能猜到 f(n) 的一般表达式？

我们已经看到 f(6) <= 6 * 2/3， f(8) = <8 * 1/2。f(n) 的一般表达式是 f(n) = n * (1 - 1/p)，其中 p 是 n 的最大的素因子。

正八边形和正六边形的方法可以推广到2的任意次幂及不是2的幂的任意正整数，也就是可以用来证明 f(n) <= n * (1 - 1/p)。下面证明 f(n) >= n * (1 - 1/p)。

设 n = p*m。正 n 边形可以分解成 m 个正 p 边形。把初始状态取成至少有一个正 p 边形上的开关状态不完全相同。当你选取少于 n * (1 - 1/p) 个开关时，m 个正 p 边形里至少有一个其中有两个位置你没有选到。因为p是素数，旋转正 n 边形可以使这两个位置的开关状态不同。（这里要用一点p阶循环群的知识。）所以不管怎样都不可能必胜。