问题描述:
100根火柴,2人轮流取,每人每次只能取1-7根,取走最后一根火柴的人获胜。问有没有一种策略肯定能够获胜?该策略具体:先取or后取,怎么取?
思维过程:
step1:题目问的很明显,所以肯定是有一种方法能够获胜的,因为自己读题时对“先取还是后取”字眼比较关注,且由于先取,不能保证另一方取完后的数量,所以假设为后取(这个假设算是一个坑吧)
step2:问题肯定存在某种规律,我认为是2人每一回合取的火柴数。2人轮流取,后取的肯定能够保证这一轮总数为8,>8的数是不可能的了。
step3:每一回合按照step2中的这样取,最后还剩4根。当时自己怎么都绕不过来这四根应该怎么办,然后就开始动摇是不是不应该每次使得总和为8,如果不保持这个数的话,取的数就会乱套,也不行(PS:愣是没有想到推翻假设)
step4:实在不行了,就开始从结局开始往前推,假设2人都是明白道理的话,最后一局肯定是8根,再往前推一局,推推推……发现不行啊,100根太多了。就以10根为例推,还是有点乱。
step5:最后还是觉得之前保持8根的想法是对的,就从100根倒着减8,减了几次,恍然大悟,可以先取4根,后面就能够保持平衡了……
结果:
先取,第一次取4根,后面只要与另一个人在同一回合相加为8就ok.
(不过刚刚又想到其实后取也是可以的,只要在中途多取几根,多取的总数为4也行,(如果前面的人永远取1根,那第一轮的时候取3根也能凑4)hahha,这个解决方法是刚刚写的时候想到的!)
总结:
要记得自己假设了什么,有时候推翻假设是关键
——————————————————————————————————————————————————————————————
推广:
有两堆水果,数量分别为m,n。2人轮流取,每次只能在一堆水果中取,每次可以取1~这堆水果的总量。取走最后一个水果的人获胜。问:同上。
思维过程:
step1:假设每次都尽可能赢,最后一局的时候,结果为2堆各剩余1个。那么就可以把两堆分成4堆,即两堆中的1个不拿,问题可以转换为谁正好拿完剩余的那些,那么他就是赢的。转化后的问题跟原问题一样了,即两堆中的2个不拿,谁拿完剩余的那些,那么他就是赢家。如果一直往前推的话,到第三次转换的时候就出现问题了,即剩余3个不拿,谁拿完剩余的那些,谁就是赢家(我是到这一步才明白不能递推)。因为他可以直接拿到只剩一个,所以这种每堆只剩3个的情况可以是不存在的。综上,只有两堆都只剩1个,这种情况才是肯定会存在的(在第一句假设上)。(找确定情况)
step2:往后递推的方式不行,就考虑了此题与上一题的区别,很明显的一点就是,拿的个数放宽了,所以每次拿完之后情况复杂,不能看出规律来。
step3:这时候,我采用了特例的方法,假设每次每个人只拿一个,分析先拿和后拿的情况,发现跟m+n的奇偶性有关。但是推翻这个假设又想不通了。又将个数实例化,且去比较小的值,但是情况也是乱七八糟的。然后就放弃这个方法了。
step4:直觉上觉得应该还是应该从后面固定的局面(即两堆各剩下1个)往前推。感觉也是有点漫无目的想。可以说是自己模拟情况,也没有什么进展。
step5:然后在睡觉前又想了一会,又有点跳回到step1中的想法,后来猛然惊醒,忽然想每次只要跟对方拿的一样就行了啊。然后有修正了一下,感觉只要每一回合之后,两堆剩余的个数一样就可以了,只要谁能够在其这一次拿完之后使得两堆剩余一样就可以了。考虑先拿后拿的问题,由于上一题的经验,可以说先后其实是相对的,所以觉得先后无关,但是仔细想想就发现,m≠n是,为了保证能够获胜,先拿使得两堆数量相同,才能自己赢,因为如果后拿,先拿的人知道这个规律,那么你是不可能使得两堆相等的。(感觉“忽然顿悟”这一点实在是难以琢磨,不知道为何自己忽然就知道了,不过现在想想,可能也跟step1中的递推有关系,因为当时就发现如果这样下去,每次两堆剩下的数量都是一样的。这应该也算是线索之一吧)
结果:
先拿,每次拿完之后只要保证两堆数量相等即可。
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
总结:
虽然题目看上去差不多,中间也用了一些相同的办法去做,但是感觉到第一问题还是有迹可循的,第二问题就有点靠联想而不是推理或者是逻辑演练了。
相同点:思路都是从题目中反推出结果成立需要满足的情况,再由这个确定的情况出发,联想或者推理。
不同点:问1规律明显,问2规律不明显(甚至我都觉得自己找不到规律啊)