由单位正方形组成的M*N的矩形棋盘(其中M,N为不超过10的正整数),在棋盘的左下角单位正方形里放有一枚棋子,甲乙两人轮流行棋.规则是:或者向上走任意多格,或者向右走任意多格,但是不能走出

Question

由单位正方形组成的M*N的矩形棋盘(其中M,N为不超过10的正整数),
在棋盘的左下角单位正方形里放有一枚棋子,甲乙两人轮流行棋.规则
是:或者向上走任意多格,或者向右走任意多格,但是不能走出棋盘或者
不走.若规定不能再走者为负(即最先将棋子移至右上角者获胜).那么
能使先行棋的甲有必胜策略的正整数对(M,N)共有多少个?

Answer 1

假设甲先走 乙后走
首先容易知道M=N=1时 甲必败 下面我们归纳证明当M=N时 甲必败
首先M=N=1的情形是显然的
假设M=N《K时,甲必败 则当M=N=K+1时,假设甲第一步往任意一个方向走X步
则乙便往另外一个方向走X步 若X=K+1,易知此时已经走到右上角,所以甲已经败了.否则XN (M