魔方吧·中文魔方俱乐部

标题: 两头取数的问题 [打印本页]

作者: yang_bigarm 时间: 2009-3-31 22:58:44 标题: 两头取数的问题

我的一个同学说我每天发一个题目强度似乎太大了，但是这里高手挺多的，于是我决定再坚持发几个问题。
我收集的此类问题挺多的，但是大部分都能在网上搜到，所以就挑选其中比较不容易搜到的问题来发。

有一串数字长度不定，范围从0-100（其他范围也行）例如

47，30，1，47，2，30，45，7，37，82，9，97，48，32，78，92，74，83

甲乙二人轮流从两端取数，既可以从左边去，也可以从右边去，但是不能取中间的，
（例如甲只能取47或83，如果甲取47，那么乙只能从剩下的数中取30或83），直到整个一串数全部取完，计算甲乙两人所取数之和，总和较大者胜利。
问：1 这个游戏先取的人可以必胜吗？
2 如果有人有必胜的策略，那么怎么样取可以赢得尽可能多？

作者: gejunji 时间: 2009-3-31 23:04:10

这个逻辑和尼姆游戏的逻辑是差不多的

作者: yang_bigarm 时间: 2009-3-31 23:14:39

原帖由 gejunji 于 2009-3-31 23:04 发表
这个逻辑和尼姆游戏的逻辑是差不多的

那么第二问呢？怎么样才能赢得多？你考虑了没？

作者: 金眼睛 时间: 2009-4-1 19:53:21

第一问：不可以必胜。
原因如下：必胜也就意味着甲的和比乙至少大1，假设这样的策略存在，那么对于如下初始数列：
1，*，*，……，*，*，1，甲先取，必取1，然后乙采用甲的必胜策略，则后来乙至少比甲的和多1。
这样，乙至少与甲的和相同，也就是甲不能必胜，这与存在必胜策略相矛盾。

第二问：可以理解成甲怎样才能使自己的收益更多么？呵呵！
这就涉及到什么样的数列让人不好下手的问题了，我感觉是一种平衡的数列，也就是其重心靠近其最大数（或最大数团），这只是个人感觉，没经过严格证明，呵呵！
也就是说，甲即要使自己取的数较大，又要给乙留下一个平衡的数列，要综合考虑，尤其是数列中的数比较少的时候。

作者: kexin_xiao 时间: 2009-4-1 20:46:22 标题: 回复 4# 的帖子

好久不见啊

作者: lulijie 时间: 2009-4-1 20:57:46

4#只能证明对于任何数列，先取方必胜是不可能的。
当若对于偶数长数列，先取方必胜，或必败。
或者对于奇数长数列，先取方必胜，或必败。
金眼睛的反证法并不能证明上述的论断是错误的。

作者: lulijie 时间: 2009-4-1 21:22:53

其实若题目改为先取方是否有策略立于不败之地，倒是值得探讨。
否则的话，若所有的数都相同，先取方不可能必胜。

作者: lulijie 时间: 2009-4-1 23:25:50

我发现先取方立于不败之地也是不保证的。
例如： 1 100 2
上述例子先取方必败。
对于所有的第二项数字特别大，其他各项都很小的情况，大家都不会去取第一项，所有大家从最后面开始取。
最后剩下3个数时，如同我举的例子，先取方必败。
所以对于奇数个数字的排列，第二项数字特别大的情况，先取方必败。
所以先取方立于不败都是不可能的。对于这种情况，先取方最佳的策略就是怎么样才能输的最少？
对于一个数字排列，按照楼主的取法，最后结束时用先取方所有的数的和减去后取方所有数的和得到的数为S。（S也可能是负数）
那么先取方的策略就是如何取才能使得S最大？这样的S肯定存在，但如何找出它来，并不容易。

作者: lulijie 时间: 2009-4-2 14:57:39

按理说谁取到最大的数，（尤其这个数明显大于其他数）谁赢的可能性最大。
如果最大的数不在数列的两头，那么：
偶数长数列，最大数（假如只有1个）一定能被先手方取得。
奇数长数列，最大数一定能被后手方取得。
这个结论是显而易见的。

作者: 骰迷 时间: 2009-4-2 20:20:58

拿到了100，輸掉了十個99，還是輸
奇數長數列和偶數長數列需要不同的處理吧

作者: yang_bigarm 时间: 2009-4-3 20:33:55

哈哈，后出的题目居然被先解决了，先出的还没有人做出第一个问来。
第一问不算难呀。

作者: lulijie 时间: 2009-4-4 02:17:22

甲乙都是最佳取法，结果如下：
把每个数第几步被取走的步数写在每个数的下面：
47， 30，1， 47， 2， 30，45，7， 37，82， 9，97，48，32，78，92，74，83
5， 7， 18，17，16，15，14，13，12，11， 10，9，8， 6， 4， 3， 2， 1
甲尽赚189。

作者: 金眼睛 时间: 2009-4-4 11:52:44

原帖由 kexin_xiao 于 2009-4-1 20:46 发表
好久不见啊

呵呵，欣然好啊，还是那么勤奋，我就不行了，只有休息的时候才能来转转。

这道题第一问很明显吧! 还不用考虑奇数和偶数的问题，虽然偶数时甲可以不输但也不能必胜啊，呵呵！

关键还是比策略，可以用计算机编几套策略，然后让计算机自己对比策略的优劣。

具体的策略还真得费一番脑筋，LZ真是脑细胞第一杀手啊：）

欢迎光临魔方吧·中文魔方俱乐部 (http://bbs.mf8-china.com/)