全部版块 我的主页
论坛 提问 悬赏 求职 新闻 读书 功能一区 悬赏大厅
3267 4
2016-12-25
悬赏 40 个论坛币 未解决
Consider 2016 coins, all of which initially showing heads, lying in a straight line on a long table. Two players, Alex and Ben, standing by the same side of the table, play the following game with alternating moves: each "good move" consists of choosing a block of 15 consecutive coins, the leftmost of which showing head, and turning them all over. Alex starts first, and the last player who can make a "good move" wins the game.
a) Will this game always end?
b) Does Alex have a winning strategy, and why?

这道题是英文的,说说我的理解。一共有2016个硬币,甲和乙分别翻硬币。2016个硬币开始默认都是head朝上。甲先翻硬币,规则是:必须连续翻15个硬币(如果是head就会变成tail,如果是tail就会变成head),而且这15个硬币中最左边一定得是head才可以翻。最后一个可以连续翻15个硬币的人赢。
第一问,这个游戏一定会结束吗?
第二问,乙有没有可能赢?策略是什么?
这道题我知道答案,第一问是游戏一定会结束,第二问是乙没有可能赢,因为无论怎么翻,甲都会赢,但是我不会严格的证明。请大家提供证明过程,谢谢。

二维码

扫码加我 拉你入群

请注明:姓名-公司-职位

以便审核进群资格,未注明则拒绝

全部回复
2016-12-28 18:28:07
顶一下
二维码

扫码加我 拉你入群

请注明:姓名-公司-职位

以便审核进群资格,未注明则拒绝

2016-12-29 21:49:23
奥数题。
丫头会做。
二维码

扫码加我 拉你入群

请注明:姓名-公司-职位

以便审核进群资格,未注明则拒绝

2016-12-31 04:53:37
先回答第一个问题,第一个问题很明显如果把H看成1,T看成0,那么可以看做2016位二进制数,这样每个回合这个二进制数必然减小,所以游戏一定结束。
做第二题要注意最右边的14个硬币无论H还是T都是没有用的,所以如果理解这一点就没难度了。
考虑从右往左数第15,30,45。。。。个硬币(间隔15),应该是134个硬币
如果这134个硬币有偶数个朝上就是先手必败
如果这134个硬币有奇数个朝上就是先手必胜
原因很简单,因为如果一开始是每次轮到你的时候这134个硬币的奇偶性和上一次轮到你的时候是不变的(因为每轮都改变这134个的奇偶性)。而如果最左边的2002个硬币都是反面(偶数),那么无论最后14个怎么样,你都是必败的。而且游戏到最后一轮的时候一定是最左边的2002个都是反面(不然你总能找到连续15个去翻)。
二维码

扫码加我 拉你入群

请注明:姓名-公司-职位

以便审核进群资格,未注明则拒绝

2017-1-1 17:17:36
楼上正解,好厉害
二维码

扫码加我 拉你入群

请注明:姓名-公司-职位

以便审核进群资格,未注明则拒绝

相关推荐
栏目导航
热门文章
推荐文章

说点什么

分享

扫码加好友,拉您进群
各岗位、行业、专业交流群