零和一的游戏(谷歌访谈)

Question

不久前我在谷歌的采访中被问到这个问题,到目前为止,我没有找到一个好的答案:这是一个双人游戏,给你一串零和一个.在每个回合中,玩家可以选择1(或彼此相邻的多个1)并将其/它们更改为0/0.将最后1个(或1个组)更改为0/0的玩家是游戏的赢家.

例如从0101110开始.第一个玩家有7个可能的动作:

1. 0 1 01110 - > 0 0 01110(第二名球员可以获胜)
2. 010 1 110 - > 010 0 110(第二名球员可以获胜)
3. 0101 1 10 - > 0101 0 10(第二名球员可以获胜)
4. 01011 1 0 - > 01011 0 0(第二名球员可以获胜)
5. 010 11 10 - > 010 00 10(第一名球员可以获胜)
6. 0101 11 0 - > 0101 00 0(第一名球员可以获胜)
7. 010 111 0 - > 010 000 0(第二名球员可以获胜)

目标是如果你先开始就弄清楚是否有一个成功的策略.我们假设这两位球员都是优秀的球员(这意味着他们不会犯错误!)

更新: 这个游戏与Nim(https://en.wikipedia.org/wiki/Nim)略有不同,对于Nim来说,每个回合的堆数(或堆数)都保持不变,而在每一个回合你都可以改变堆数.例如,如果我们最初做0101 1 10 - > 0101 0 10,我们有两个大小为1和3的桩,但在移动之后我们将有3桩,大小为1.

Answer 1

令nim[n]为 1 序列的个数n。那么我们有如下的递推关系：

nim[n] = mex{nim[i] xor nim[j]: i, j >= 0, i + j < n}

（有关一般理论，请参阅斯普拉格-格伦迪定理。）

从这个递推关系中，你可以尝试计算数列的前几项nim，你会发现似乎是这样nim[n] = n。

那么就可以很容易地推导出一个证明，我将把这个证明留给你。

因此，一系列n连续的序列实际上相当于一个大小为 的 Nim 堆n。现在可以轻松找到任何游戏的结果。

例如，如果我们有0101110，那么它相当于两堆 Nim，大小分别为1和3。因此，总人数等于1 xor 3 = 2，它不为零，因此第一个玩家获胜。

另一个例子，如果我们有1110011111000111111，那么总数量等于3 xor 5 xor 6 = 0，所以第一个玩家输了。

编辑：关于你关于桩变化的问题，这里有一些更多的解释。

虽然桩数会发生变化，但关键点如下：

• 如果某个状态的数字为零，则任何有效的移动都必须将其更改为非零数字状态。
• 如果状态具有非零数，则必须存在有效​​的移动，将其更改为零数状态。

因此，对于胜利者来说，策略是给对手留下零数状态。

示例：让我们从序列 开始1110011111000111111，我简称为3, 5, 6。

如果第一个玩家将 和 替换6为2和3，则第二个玩家面临的状态3, 5, 1, 4为 nimber 3 xor 5 xor 2 xor 3 = 7。为了保持其零位数，第二个玩家替换了5，2留下第一个玩家3, 2, 2, 3，其同样具有零位数。

该过程继续进行，直到第一个玩家没有有效的移动。