珍珠湾ART

标题: 再来一个正 n 边形和开关解答（1） [打印本页]

作者: constant 时间: 2005-11-29 04:34
标题: 再来一个正 n 边形和开关解答（1）

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

现在假设是一个正 n 边形, 对哪些 n 你有必胜策略？

这道题还有一种形式：目的是把四个开关都打开。我们同时对这两种形式求解。对给定n，称这两种形式的问题为U(n)和S(n)。

定理。U(n)和S(n)有解的充分必要条件是n=2^k。

证明要分成好几步。先定义一个名词：一个解序列是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)的解序列。

首先，如果用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}）。

明天接着证另一半。

作者: constant 时间: 2005-11-30 02:47
标题: 再来一个正 n 边形和开关解答（2）

引理3。如果U(2n)有解，U(n)也有解。

证明：设A=(a1,a2,...,am)为U(2n)的解序列，作B=(b1,b2,...b)如下：对每一个ai，令bi为2n个开关的前半和后半相减形成的子集：如ai={1,2,5,8,9}, n=6, 则bi={1,3,5}（2与8抵消，9变成3）。B即为U(n)的解序列。

引理4。如果n>1是奇数，则U(n)无解。

证明：设A=(a1,a2,...,am)为U(n)的解序列。则对任意ai,必有｛1，...,n}中两个相邻的数都在ai中或都不在ai中。（1和n算相邻。）在ai之前，旋转正n边形使得着两处的开关状态不同，这样n个开关永远不会状态完全相同。

引理3和引理4证明了定理的另一半。

作者: 寒潭清 时间: 2005-11-30 14:48
标题: 辛苦了,得仔细学学[:)][>:D<][@};-][@};-]

辛苦了,得仔细学学

欢迎光临珍珠湾ART (http://zzwav.com/)