灯的Open&Close计数

superacid

设n和k是正整数，k≥n，且k−n是一个偶数。
2n盏灯依次编号为1,2,...,2n，每一盏灯可以Open和Close。开始时，所有的灯都是Close的。
对这些灯可进行操作，每一次操作只改变其中的一盏灯的开关状态(即Open变成Close，Close变成Open)。
考虑长度为k的操作序列，序列中的第i项就是第i次操作时被改变开关状态的那盏灯的编号。

设N是k次操作后使得灯1,2,...,n是Open的，灯n+1,n+2,...,2n 是Close的状态的所有不同的操作序列的个数。
设M是k次操作后使得灯1,2,...,n是Open的，灯n+1,n+2,...,2n 是Close的，但是灯n+1,n+2,...,2n 始终没有被开过的所有不同的操作序列的个数。
求比值N/M。.

[ 本帖最后由 superacid 于 2009-7-10 17:35 编辑 ]

Osullivan

貌似某届IMO试题这是？~~~~~~~~
thinking~~~~~~

suny

我承认我没有把题目看完的耐心和勇气......

lulijie

设N是k次操作后使得灯1,2,...,n是Open的，灯n+1,n+2,...,2n 是Close的状态的所有不同的操作序列的个数。
设M是k次操作后使得灯1,2,...,n是Close的，灯n+1,n+2,...,2n 是Close的，但是灯n+1,n+2,...,2n 始终没有被开过的所有不同的操作序列的个数。

------------------------------
红字部分是不是错了，而应该是Open？
否则，当k为奇数时，M=0。

superacid

确实打错了，谢谢提醒。

lulijie

n=1,k=3
      N=4,M=1   
n=1,k=5
      N=16,M=1
n=1,k=7
      N=64,M=1
    n=1时，有M＝1，N＝M*4^((k-n)/2)=M*2^(k-n)
n=2,k=4
      N=32,M=8
n=2,k=6
      N=512,M=32
......
    n=2时，有N=M*2^(k-n)
-----------------------------------------
所以猜测  N/M = 2^(k-n)