正方形的每个角上有一个开关。你的目的是把四个开关的状态变成一样，即都是开或都是关。但你不知道开关的状态，每次你可以任选一到四个开关，改变它们的状态。(改变之后你还是不知道开关的状态。) 你选定开关后，正方形会旋转一个角度。（旋转的角度你也不知道。）你有没有必胜策略？
现在假设是一个正 n 边形, 对哪些 n 你有必胜策略？ 这道题还有一种形式：目的是把四个开关都打开。我们同时对这两种形式求解。对给定n，称这两种形式的问题为U(n)和S(n)。 定理。U(n)和S(n)有解的充分必要条件是n=2^k。 www.ddhw.com 证明要分成好几步。先定义一个名词：一个解序列是1到n这n个数的一列子集，每个子集是一次选的开关。例如（{1，3}，{1，2}，{1，3}，{1}，{1，3}，{1，2}，{1，3}）就是n=4时的一个解序列。 引理1。如果U(n)有解，S(n)也有解。 证明：设A=(a1,a2,...,am)为U(n)的解序列，及b={1,2,...n}（按全部开关）。则B=(b,a1,b,a2,b,...,b,am,b}为S(n)的解序列。 引理2。如果U(n)有解，U(2n)也有解。 证明：设A=(a1,a2,...,am)为S(n)的解序列，B=(b1,b2,...bk)为U(n)的解序列。对每一个bi，令bi^2为在2n的前半和后半重复bi形成的子集：如bi={1,2,5}, n=6, 则bi^2={1,2,5,7,8,11}。令B^2=(b1^2,b2^2,...,bk^2)。我们证明（B^2,a1,B^2,a2,B^2,...,B^2,an,B^2）为U(2n)的解序列。 www.ddhw.com 首先，如果用A来解U(2n)，则在解的过程中，必有一刻，这2n个开关中，所有相对的两个状态都相同。要证明这一点，考虑相对的两个状态的差。这n个差构成一个S(n)问题。用A来解U(2n)就相当于解这个S(n)问题。所以一定有一刻，这2n个开关中，所有相对的两个状态都相同。 B^2中所有的子集都是对称的。他们对上面A解U(2n)的过程没有影响。设在ai时U(2n)一经完全对称。则在ai之后的B^2就一定能使U(2n)得解。 这两个引理再加上U(4)的例子证明了定理的一半。其实连U(4)都不用，可以从U(2)得到U(4)：U(2)的解为（{1}），由引理1，S(2)的解为({1,2},{1},{1,2})，再由引理2，U(4)的解为（{1，3}，{1，2}，{1，3}，{1}，{1，3}，{1，2}，{1，3}）。 明天接着证另一半。
www.ddhw.com
| 
哈哈哈哈 O(∩_∩)O哈哈~ 好久不来了，不小心看了一眼自己主页，发现自动关联了自己以往发过的帖，点进这个看了一眼，笑个半死。。。敢情我当初还发过这么搞笑的东西啊，我自己完全不记得了 
雷达卡
发表于 2005-11-29 04:34:55
收藏
分享
支持
反对
置顶卡
千斤顶
楼主
