数学游戏07:一种变异的NIM游戏(解答)
(2010-08-26 14:10:18)
标签:
幽魂之家数学逻辑游戏文化 |
分类: 休闲娱乐类 |
《数学逻辑游戏07:一种变异的NIM游戏》中的变异的NIM游戏也是一种有限双人零和(没有平局的)游戏,这种游戏的必胜策略就是逼使对方处于必输的状态。(参见《数学逻辑游戏05:NIM游戏(解答1)》)。
对任意自然数n,归纳定义a(n)、和A(n)如下:
a(0)=0,a(n+1)=不在An中的自然数中的最小数。
An={a(i),a(i)+i|i≤n}
则S={|n是自然数}就是全部必输状态的集合。
证明S是全部必输状态的集合,只需证明:
1. 对于S中的状态,随便怎么拿,得到的状态一定不在S中。
2. 对于不在S中的状态,一定存在一种拿法,使得得到的状态在S中。
(参考《数学逻辑游戏05:NIM游戏(解答3))
1. 设在S中。
1.1 在a(n)中拿t根得到(a(m)=a(n)-t,m不在S中。
1.2 在a(n)+n中拿t根得到,则a(n)+n-t≠aa(n)+n,所以不在S中。
1.3 分别在a(n)和a(n)+n中拿t根得到(a(m)=a(n)-t,m
a(n)+n-t=a(n)+n-(a(n)-a(m))=a(m)+n≠a(m)+m,
所以不在S中。
2. 设(不存在m
2.1 如果y≤a(n),则y=a(m)+m(m在S中。
2.2 如果a(n)
如果n在S中。 如果m在S中。