趣题, 第8道来了。

newkid

lastwinner 发表于 2012-5-22 16:06
有意思
类似的问题是一堆XX数目的豆子，甲拿X乙拿Y，谁拿最后一个谁就输，问策略应该怎样才能保证不输（ ...

我正要说这个题呢！规则是：
有若干堆石子，每次允许从一堆中取任意个，谁取到最后就算赢（或输）。诀窍是保证剩下的石子的异或为零。
现在是把一个数和它所有因数看成一堆石子，问题是有交叉，看看能否把策略修改适用。

lastwinner

newkid 发表于 2012-5-22 21:29
我正要说这个题呢！规则是：
有若干堆石子，每次允许从一堆中取任意个，谁取到最后就算赢（或输）。诀窍 ...

任意个是有限制的吧？

newkid

lastwinner 发表于 2012-5-22 23:37
任意个是有限制的吧？

没限制，当然也有其他变种的规则。
随便GOOGLE一个：
http://zhidao.baidu.com/question/16279208.html

newkid

正要试图看野花212楼的证明，第一句话就不懂：

14箱，9个箱子分3组，每组都要保证超过2吨，否则剩下的5个箱子就可以拿出3个箱子来分到这三组中还不会超过3吨，那么剩下的2个箱子肯定不超2吨，这样的话4个车就足够。

"每组都要" 的 "否则" 应该是“至少一组不满足"吧？那么就是：否则剩下的5个箱子“至少可以拿出一个”，而不是“就可以拿出3个箱子”。

newkid

套用石子游戏的解法：
先考察两个合数，如果先走除掉公共因子并使得剩下的因数个数相等，就能取胜。
比如9和10，1为公共因数，剩下3,9和2,5,10为非公共因数，所以先手的时候要拿掉1,2


在1-10中，先手要拿掉1,3，剩下状态：
6(2,6)
7(7)
8(2,4,8)
9(9)
10(2,5,10)

所有公共因子(2) 算1个，非公共因子数：
C6=1
C7=1
C8=2
C9=1
C10=2

异或之和加上1等于0，这时处于获胜状态。

newkid

lastwinner 发表于 2012-5-22 12:13
12箱的你能看懂的吧？
不过没关系，你就判断我说的“不能”对不对吧

其实构造5车14箱的例子很容易，因为没有下限，把前面13箱随便一箱拿出0.000001再装一箱不就行了吗？

tree_new_bee

newkid 发表于 2012-5-23 07:44
其实构造5车14箱的例子很容易，因为没有下限，把前面13箱随便一箱拿出0.000001再装一箱不就行了吗？

恩， 你说的对。
是我想错了。我当初想着只有13箱才行，是按照平均分得出的结论。

lastwinner

newkid 发表于 2012-5-22 23:45
没限制，当然也有其他变种的规则。
随便GOOGLE一个：
http://zhidao.baidu.com/question/16279208.html

晕，就你那个肯定有啊，不然我第一次就取n-1个，剩下一个必然是你拿，那你不就输了嘛

lastwinner

newkid 发表于 2012-5-23 01:33
正要试图看野花212楼的证明，第一句话就不懂：

14箱，9个箱子分3组，每组都要保证超过2吨，否则剩下的5个 ...

当时的意思是comb1/comb2/comb3(分别表示3组)若都不超过2吨，那么……
但事实上正如你指出的，不满足“都超过2吨”的，并非就一定是“都不超过2吨”，也可以是只有一组不超过2吨其他两组还超过2吨
我就是这里想错了，所以才得出了错误的结论，5555

newkid

lastwinner 发表于 2012-5-23 11:22
晕，就你那个肯定有啊，不然我第一次就取n-1个，剩下一个必然是你拿，那你不就输了嘛

晕，闹了半天你说的是一堆的情况？
我说的是有多堆，每次只能从一堆中取任意个。
一堆太简单了，限制X则只要凑足X+1即可。
比如总共30, 每次限5, 取到最后一个算赢。则先走的输，后走的每次凑足6, 就能取到最后一个。