送交者: 只是没想到而已 于 December 05, 2009 15:15:36:
回答: 支一哈！ 由 老六 于 December 05, 2009 08:27:19:
一个（N+1)X(N+1)的ckeckboard可以在一个NXN的ckeckboard的两条相邻的边上各贴上一个NX1的长方形后再加上一个连接这两个长方形的1X1的格子得到。
假设有M个marker放在原来那个NXN的ckeckboard上，并且有H行和L列上的marker数是奇数。 如果M是奇数，则H和L都只能是奇数，反之则都只能是偶数。
在新贴上的那一行上，需要在对应于原来含有偶数个marker的那N-L列的格子上共放上N-L个marker使那原有的N列都含有奇数个marker。 同样，在新贴上的那一列上，需要在对应于原来含有偶数个marker的那N-H列的格子上共放上N-H个marker使那原有的N行都含有奇数个marker。
如果N-H是偶数，则N-L也是偶数，因此还需要在连接那两个长方形的1X1的格子上放一个marker使新添的行和列都含有奇数个marker。
这样，对原来那个NXN的ckeckboard上的任何一种marker的放法，都有一种并且只有一种在新的（N+1)X(N+1)的ckeckboard上全部只含奇数个marker的行或列的放法。
在原来的那个NXN的ckeckboard上，对每一格都可以有两种可能：有marker或是空格。所以，总的放法为2^(NXN)。
对一个8X8的ckeckboard， N=7，所以总的放法确实是2^(7X7)= 2^49