魔方吧·中文魔方俱乐部

标题: 灯的Open&Close计数 [打印本页]

作者: superacid 时间: 2009-7-10 12:05:10 标题: 灯的Open&Close计数

设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 时间: 2009-7-10 12:16:30

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

作者: suny 时间: 2009-7-10 13:47:57

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

作者: lulijie 时间: 2009-7-10 16:41:47

设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 时间: 2009-7-10 17:34:58 标题: 回复 4# 的帖子

确实打错了，谢谢提醒。

作者: lulijie 时间: 2009-7-12 10:52:18

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)

附件: DD.JPG (2009-7-12 10:52:18, 26.25 KB) / 下载次数 8
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=NTg4NTJ8MDgyNWI0YTN8MTcxNTc5MTcyNnwwfDA%3D

欢迎光临魔方吧·中文魔方俱乐部 (http://bbs.mf8-china.com/)