吴军在《再谈递归原理》一文中提到了一个例子,用来解释递归的思想。该例子是其同事出的一道面试题:现在两个人玩一个游戏,从零开始往上加数,每个人依次在对方的基础上选择加1或者加2,谁正好加到20就算赢,那么怎样玩才能保证赢?
我从数学的角度来思考下这个问题。
在此之前,先介绍模的概念,详细的信息可以上wiki上查询,这里我们可以把模当做求余数, 20 模 3,或20 mod 3或20(mod 3) 就是指20被3反复除之后的余数。比如20 mod 3 = 2, 21 mod 3 = 0 , 3 mod 2 = 1.
由于20(mod 3) = 2 > 0
,所以谁先数数谁就能赢下比赛。策略就是先数2,接下来无论对方往 上加几(记为s),则你只要加3-s
即可。即后继始终保持你俩往上加的数的和为3。这样只需要六轮你就能赢下比赛。
那么是否先数的一定能赢呢?若我们改变最后的终止条件,变成谁加到21谁就赢,那就变成后数的赢了。
由于21(mod 3) = 0
,所以先数的人无论加几(s),后数的人以上述同样的策略加``3-s```就能赢下比赛。
上述的2、20都是具体的数字,我们把它们换成自然数m、n,即游戏变成:现在有两人玩一个游戏,从零开始往上加数,第个人可以选择加1至m中的一个数,谁加到n就算赢,那么怎样玩才能保证赢?
设p = n mod (m+1)
,若p=0
则先数数的人输,反之先数数的人赢。赢的策略就是无论对方加几(记为s),你只要加m+1-s
。
也许你注意到了,虽然每个人加的数会有变化,但这个游戏中有一件事是能做到不变的:无论对方加几,你都有办法使你俩累加的数字和为m+1
。
我们来证明一下。
设对方这次往上加s
,则有1<= s <= m
,若我在此基础上选择加m+1-s
,则我俩这次共往上加了s+m+1-s = m
。
这里还需要证明一个问题:我能保证加m+1-s
?由于1=m+1-m <= m+1-s <= m+1-1=m
,根据游戏规则,我可以选择1至m内的任意自然数,而m+1-s
在这个选择范围内,于是我始终能做到这点。
为什么会想到是m+1
?这也是通过归纳总结出来的,还是以20为例,要想数到20,自己必须数到17,这样与20保持3个距离使对方无论数到而自己再一次数时一定能数到20,所以2+1
是个刚刚合适的距离。
同样要数到17就得数到14、11、8、5、2. 我们能发现始终以3为距离减少直至不能再减,这就是求余或模的概念。
从这个游戏,也说明一个事实,就是看似公平的游戏可能并不公平。比如买彩票,表面上看起来很公平,也有很多人能赚个几百万,但只要知道一点统计学的知识,就能知道只要玩的次数够多,任何一个玩家最后一定会输。
所以为了尽可能避免进入这类看似公平的游戏,多点知识储备还是很有必要的。
网友评论